关于java:JDK源码分析LinkedList

28次阅读

共计 4370 个字符,预计需要花费 11 分钟才能阅读完成。

1. 概述

相较于 ArrayList,LinkedList 在平时应用少一些。

LinkedList 外部是一个双向链表,并且实现了 List 接口和 Deque 接口,因而它也具备 List 的操作以及双端队列和栈的性质。双向链表的构造如下:

前文剖析了 Queue 和 Deque 接口,正是因为 LinkedList 实现了 Deque 接口。LinkedList 的继承构造如下:

2. 代码剖析

2.1 结点类 Node

查看 LinkedList 的源码可发现它外部有个嵌套类 Node,代码如下:

private static class Node<E> {
    E item; // 存储的数据
    Node<E> next; // 后继结点
    Node<E> prev; // 前驱结点
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList 是双向链表的实现,而该 Node 类则是链表的结点。

此外,LinkedList 还有几个成员变量如下:

// list 的长度
transient int size = 0;

// 链表头结点
transient Node<E> first;

// 链表尾结点
transient Node<E> last;

2.2 结构器

LinkedList 有两个结构器,如下:

public LinkedList() {}

public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

PS: 因为链表的容量能够始终减少,因而没有指定容量的结构器。

其中第一个为无参结构器;第二个为应用指定的汇合结构,并调用 addAll(),持续跟进该办法,代码如下:

public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);
    // 将汇合元素转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    // 获取以后链表的前驱和后继结点
    Node<E> pred, succ;
    if (index == size) { // 尾结点的前驱和后继结点
        succ = null;
        pred = last;
    } else { // 若非尾结点,获取指定地位的结点
        succ = node(index);
        pred = succ.prev;
    }
    // 循环将数组中的元素插入到链表
    for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    // 若插入到开端,则数组中的最初一个元素就是尾结点
    if (succ == null) {last = pred;} else {
        // 若插入到指定地位,将数组中最初一个元素与下一个地位关联起来
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;
    modCount++;
    return true;
}

其中 node(index) 办法为获取指定地位的结点,代码如下:

Node<E> node(int index) {// assert isElementIndex(index);
    // 若下标在前一半,则从前往后遍历;否则从后往前遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

该办法通过遍历链表获取指定的元素。

值得注意的是,该办法并非间接从头到尾遍历整个链表,而是先判断下标的地位,若在前一半则从前往后遍历;否则就从后往前遍历。这样能缩小遍历结点的个数。

PS: 前文「数据结构与算法笔记(一)」对链表进行过剖析,因为其内存空间非间断,因而不反对随机拜访(下标拜访)。所以,查问某个结点是通过遍历整个链表来实现的。

与此同时,get(index) 办法外部也是这样实现的:

public E get(int index) {checkElementIndex(index);
    return node(index).item;
}

2.3 罕用办法

之前剖析 Queue 和 Deque 的时候提到:Queue 中的办法在 Deque 中都有对应的。上面简略剖析 LinkedList 中一些罕用的办法。

新增结点办法:add(), addLast(), offerLast()

public boolean offerLast(E e) {addLast(e);
    return true;
}

public void addLast(E e) {linkLast(e);
}

public boolean add(E e) {linkLast(e);
    return true;
}

能够看到他们都是调用了同一个办法 linkLast(e) 实现的,如下:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    // 若链表为空,则新结点为头结点
    if (l == null)
        first = newNode;
    // 若链表不为空,将新结点插入到链表尾部
    else
        l.next = newNode;
    size++;
    modCount++;
}

该操作就是将指定的结点增加到链表开端。

删除结点办法:poll(), pollFirst(), removeFirst()

public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
 
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

能够看到这三个办法都是调用 unlinkFirst() 办法实现的,其代码如下:

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

该办法的操作就是从链表头部移除一个结点。

向单链表插入和删除结点的操作示意图如下(双链表比这里多了前驱结点):

栈的入栈(push)和出栈(pop)操作:

public void push(E e) {addFirst(e);
}

public E pop() {return removeFirst();
}

能够看到这两个办法间接调用了双端队列的实现办法。即,该栈是一个「链式栈」。

3. 线程安全性

线程平安的概念不再赘述。剖析以下场景:

若有线程 T1 对 LinkedList 进行遍历,同时线程 T2 对其进行结构性批改。

对 LinkedList 的遍历是通过 listIterator(index) 办法实现的,如下:

public ListIterator<E> listIterator(int index) {checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        // 初始化时二者是相等的
        private int expectedModCount = modCount;

        ListItr(int index) {// assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public E next() {checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public void remove() {checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        // ...
        
        // 是否有其余线程对以后对象进行构造批改
        final void checkForComodification() {if (modCount != expectedModCount)
                throw new ConcurrentModificationException();}
}

该类的 next(), add(e) 等办法在执行时会检测 modCount 与创立时是否统一(checkForComodification() 办法),从而判断是否有其余线程对该对象进行了构造批改,若有则抛出 ConcurrentModificationException 异样。

因而,LinkedList 是线程不平安的。

4. 小结

  1. LinkedList 外部是「双向链表」,同时实现了 List 接口和 Deque 接口,因而也具备 List、双端队列和栈的性质;
  2. 线程不平安。

相干浏览:JDK 源码 -Queue, Deque

正文完
 0