2019年一文读懂LinkedList

LinkedList

LinkedList一、简介1.1 源码分析1.2 注意1.3 使用建议 二、特点2.1 初始化 LinkedList 时采用懒加载模式2.2 保存了链表的头尾元素的引用，通过每个元素头尾引用将数据串行2.3 添加数据2.4 删除元素2.5 查找元素 三、常见问题3.1 与 ArrayList 相比较

---

一、简介

LinkedList 底层的数据结构是 “双向链表”，它的每个节点都拥有指向前后节点的引用，故不需要扩容机制。它也是有序可重复、线程不安全的集合，可存入多个 null对象，但与 ArrayList 相比，它的随机访问效率更低。

​

1.1 源码分析

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

从源码分析，LinkedList 继承于 AbstractSequentialList（AbstractList 的子类），实现了 List，Deque，Cloneable，Serializable 接口：

实现 List，并继承 AbstractSequentialList，获得集合接口 List 的基础功能；实现 Deque（双向队列），也就允许在集合两端进行数据的插入和删除操作；实现 Cloneable，重写 clone，实现克隆功能；实现 Serializable，可被序列化。

​

1.2 注意

LinkedList 在 jdk1.7 之前是环形链表，在 jdk1.7 之后优化为直线型链表。

​

1.3 使用建议

当需要运行在低版本的 jdk 环境下，并且集合中对访问元素数据速度要求不高，但对插入和删除元素速度要求较高时，建议使用 LinkedList。当经常进行头部插入和删除操作时，建议使用 LinkedList。

​

二、特点

2.1 初始化 LinkedList 时采用懒加载模式

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

​

2.2 保存了链表的头尾元素的引用，通过每个元素头尾引用将数据串行

transient Node<E> first; transient Node<E> last; private static class Node<E> { E item; Node<E> next; Node<E> prev; }

​

2.3 添加数据

LinkedList 的添加方式主要有2种：一是直接在尾部添加元素；二是在指定位置添加元素。内部主要调用 linkLast 和 linkBefore 存储元素。

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

​

2.4 删除元素

LinkedList 的删除方式主要有4种：一是移除第一个元素；二是移除最后一个元素，三是移除指定位置元素；四是移除指定元素。内部主要调用 unlinkFirst，unlinkLast 和 unlink 删除元素。

private E unlinkFirst(Node<E> f) { 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; } private E unlinkLast(Node<E> l) { final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } 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; }

​

2.5 查找元素

LinkedList 采用二分法去加速一次读取指定位置的元素

Node<E> node(int 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; } }

node(index) 中根据指定位置去选择从前遍历还是从后遍历整个集合，也可以间接说明，LinkedList 在随机获取元素时性能很低，每次都得从头或者从尾遍依次历半个集合。

​

三、常见问题

3.1 与 ArrayList 相比较

新增性能比较

在新增操作时，ArrayList 效率不如 LinkedList，因为 ArrayList 底层是数组实现，在动态扩容时，性能有所损耗，而 LinkedList 不存在数组扩容机制，所以LinkedList 效率更高。

实际比较发现：

随着 JDK 版本的更新，优化了底层函数 System.arraycopy 的性能，以至于ArrayList 的扩容性能得到提升。在对于均为尾部插入数据时，ArrayList 性能更优。参考：https://www.jianshu.com/p/63b01b6379fb

元素获取比较

由于LinkedList是链表结构，没有角标的概念，没有实现 RandomAccess 接口，不具备随机元素访问功能，遍历查找可能要遍历半个集合，效率较低。