jdk源码追踪-LinkedList

末蓝、 2022-02-26 10:54 282阅读 0赞

关于List接口的类结构和AbstractList的讲解，可以看看上一篇文章[jdk源码追踪-ArrayList][jdk_-ArrayList]。

#### AbstractSequentialList ####

AbstractSequentialList使用迭代器来实现`get(int index)`, `remove(int index)`, `add(int index, E e)`基本算法。迭代器是实际调用抽象方法`listIterator`，需要子类实现，是LinkedList的父类。由于它对于index元素的操作都是通过迭代器的next循环实现，所以效率比起`ArrayList`的数组直接操作下标元素的方式慢很多。

\#\#\#\#LinkedList

LinkedList继承AbstractSequentialList，ListedList实现的数据结构是标准的双向链表，有两个属性first和last两个Node类型的属性。LinkedList实现或重写的有

1.  链表存储结构
2.  get(int index)，
3.  add(T t)，
4.  add(T t, int index)，
5.  remove(int index)，
6.  它实现了list迭代器，list迭代器是迭代器的具体实现。

LinkedList的存储数据结构

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzQxMDU_size_16_color_FFFFFF_t_70]

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
    	//transient 变量修饰符，用transient关键字标记的成员变量不参与序列化过程
        transient int size = 0;
        //头节点
        transient Node<E> first;
        //尾节点
        transient Node<E> last;
    
        public 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;
            }
        }
    }

`get(int index)`方法采用的是二分再遍历的查找，如果index小于`size/2`时，从头正序遍历，否则，反序遍历到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;
        }
    }

`add(T t)`，`add(T t, int index))`，`remove(int index)`都采用的十分标准的链表插入，删除实现。

//add(T t, int index))调用
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
    
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
    
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
    
        x.item = null;
        size--;
        modCount++;
        return element;
    }

remove时会把remove的那个节点的前驱，后驱，item都设空，目的是为了GC。

它自己实现了list迭代器，list迭代器是它的父类`AbstractSequentialList`用来实现迭代器的。为什么要实现这个迭代器？`AbstractList`中list迭代器的实现是通过`get(int index)`和记录当前`index`来实现，对于链表来说，每次的`next()`，都意味着从头遍历到当前节点，这么做效率肯定很慢。LinkedList的实现是保存上传返回结点`lastReturned`和下一个结点`next`。`next()`执行时，将`next`的引用赋给`lastReturned`，`next.next`赋给`next`返回`lastReturned`的数据。

private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned;
        private Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;
    
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
    
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
    }

[jdk_-ArrayList]: https://blog.csdn.net/luo4105/article/details/88896296
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1bzQxMDU_size_16_color_FFFFFF_t_70]: /images/20220226/503ffad9a6f949f7a702e3bdf037bd19.png