深入学习Java集合类源码之LinkedList

一.简介：

• LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于 双向链表 实现的。
• LinkedList可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 是非同步的

二.源码分析：

1.继承关系

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
           

• 继承于AbstractSequentialList的双向链表。
• 实现 List 接口，能对它进行队列操作
• 实现 Deque 接口，即能将LinkedList当作双端队列使用。
• 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
• 实现java.io.Serializable接口，这意味着LinkedList支持序列化

2.两种构造方法：

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

构造方法比较简单，就是把集合元素全加到list中

3.查找方法

LinkedList 底层基于链表结构，无法向 ArrayList 那样随机访问指定位置的元素

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;
        }
    }
           

可以看出，LinkedList查找元素包含一个判断：如果index在前一半，就从头开始遍历，否则就从末尾开始遍历。

4.插入方法

add 方法有两个方法，一个是直接插入队尾，一个是插入指定位置

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

这个方法调用的就是Deque接口的add方法

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++;
    }
           

下面看第二个方法：插入指定位置

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
           

如果我们插入的位置还是链表尾部，那么还是会调用 linkLast 方法。否则调用 node 方法取出插入位置的节点，否则调用 linkBefore 方法插入。

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++;
    }
           

这个插入跟链表的插入类似，首先拿到前一个节点，然后让前一个指向新节点，让succ也就是原来的那个节点成为新节点的后继节点

5.删除方法

删除节点有两个方法，第一个是移除特定的元素，第二个是移除某个位置的元素。

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
           

这个方法的逻辑是从头到尾遍历找到要删除的节点然后调用unlink方法

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;
    }
           

删除操作也跟链表类似，找到前一个结点，然后让前一个结点指向目标结点的后一个结点

总结：

• 底层基于双向链表实现，修改速度快，读取速度慢
• 非线程安全。
• LinkedList 没有容量限制，所以也没有扩容机制