LinkedList底层实现

一、什么是LinkedList

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

根据源码我们可以看出：

• ①LinkedList继承了AbstractSequentialList，即按次序的List，也就是说不像ArrayList一样具有随机访问元素的能力，也就是说LinkedList支持按顺序访问列表中元素的操作。
• ②实现了List接口，可进行列表相关操作
• ③实现了Deque接口，可以将LinkedList当作双端队列进行使用
• ④实现Clonalbe接口，即覆盖了clone()方法，可以进行克隆操作
• ⑤实现了java.io.Serializable接口，可以进行序列化，即支持网络传输

LinkedList的本质是双向链表，与 ArrayList 相比，LinkedList 的增加和删除对操作效率更高，而查找和修改的操作效率较低。

二、LinkedList的创建

1、成员变量及数据结构

①transient int size = 0; //LinkedList存放元素个数

②first是双向链表的表头，last指向双向链表的最后一个元素

transient Node first;

transient Node last;

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

存放数据元素，prev指向上一个节点，next指向下一个节点，item为元素值

2、first和last为什么要用transist修饰？

在ArrayList中存放元素的数据结构elementData使用transisit修饰是为了节省空间，防止扩容后数组中的空数据也被序列化。

而LinkedList使用transist修饰是因为LinkedList中使用双向链表保存数据，结点中保存前驱和后继的引用。但是序列化之后前序结点和后继结点的地址都变了，所以我们应该将数据传输过去再在另一边链接为新的链表。

LinkedList的序列化与反序列化方法：

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();

    // Write out size
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

@SuppressWarnings("unchecked")
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
    s.defaultReadObject();

    // Read in size
    int size = s.readInt();

    // Read in all elements in the proper order.
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject());
}
           

3、LinkedList的创建

LinkedList list = new LinkedList(); // 普通创建方法

或者

LinkedList list = new LinkedList(Collection<? extends E> c); // 使用集合创建链表

使用集合创建链表步骤

• ①调用addAll( c )方法，而addAll( c )底层调用重写方法addAll(size, c)

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

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

• ②addAll方法首先通过checkPositionIndex(index);判断index是否越界，如果越界报越界异常。
• ③如果Collection为空直接return false
• ④如果Collection不为空，定义两个指针pred,和succ；如果index等于size，那么说明是在链表末尾插入Collection，使得pred指向last
• ⑤如果index不等于size，那么一定小于size，使用node(index)方法获得index处的node，是pred指向该node的上一个节点
• ⑥遍历Collection中的元素，将元素一个个插入进LinkedList中。

  

• ⑦最后，若succ为空，说明是在链表尾部插入的，更新last，若不为空，则是在链表中间插入的，执行操作，补全链表

  

三、LinkedList集合的各种插入删除操作

在前面我们说过，LinkedList可以当作队列也能作为栈，所以linkedList中有许多插入删除的方法。

链表尾部插入数据操作：add()、addLast()、offer()、offerLast()

链表头部插入数据操作：addFirst()、offerFirst()、push()

删除并返回链表尾部的数据：removeLast()

删除并返回链表头部的数据：poll()、remove()、removeFirst()、pop()

获取第一个元素的值：element()、getFirst()、peek()、peekFirst()

获取最后一个元素的值：getLast()、peekLast()

在任意位置插入数据：add(int index, E element)

删除任意位置数据：remove(int index)

特别注意，作为如果使用linkedList作为栈，那么以链表头部作为栈进出的位置。

四、LinkedList的遍历

在ArrayList中已经讲过，LinkedList不支持快速随机访问，所以遍历时采用迭代器遍历更快一些

要理解这个，首先要明白linkedList是一个链表，不支持随机访问，所以linkedList要得到一个元素，即get(i)的时间复杂度时o(n),所以使用一下的遍历方式，时间复杂度就会变为o(n^2)了

for (int i=0; i<size; i++) {
    list.get(i);        
}
           

而我们可以看到linkedList实现的iterator迭代器就是一个一个从first开始遍历到index大于size为止，所以获取数据的时间复杂度为o(1)

所以使用LinkedList遍历推荐使用iterator迭代器

List<Integer> list = new LinkedList<>();
Iterator iterator = list.iterator();
while(iterator.hasNext()) {
    iterator.next();
}