LinkedList 顾名思义其本质是一个链表,具体来说是一个双向链表,同时还有2个指针分别对应链表的头和尾。
源码还是跟 ArrayList 一样,从我们常用的代码出发:
List<String> a = new LinkedList<>(); a.add("sidfate"); 复制代码
进入初始化源码:
// LinkedList 长度 transient int size = 0; // 指向头结点 transient Node<E> first; // 指向尾节点 transient Node<E> last; public LinkedList() { } 复制代码
可以看到默认的构造函数空空如也,需要注意的是链表是以 Node 为基础连接起来的,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; } } 复制代码
Node 结构也很简单,prev 和 next 说明它是一个双向的链表,保存前后 Node 的指针。接下来进入 add 的过程:
public boolean add(E e) { linkLast(e); return true; } 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++; } 复制代码
简单来说,添加一个元素就是往链表尾插入一个新的 Node。那么如果是往链表中插入一个元素呢:
public void add(int index, E element) { // 检查index合法性 checkPositionIndex(index); if (index == size) // 如果index就是尾部则直接添加 linkLast(element); else // 在 index 所在的 Node 前插入 linkBefore(element, 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; } } 复制代码
node 函数用来查找对应 index 的 Node 节点,比较有意思的是 2 将遍历降低成了链表长度的一半:
双向链表的优势就凸显出来的,相对而言插入的效率比 ArrayList 高,毕竟 ArrayList 需要拷贝 index 后的数组。但是查询效率就低了,ArrayList 根据下标能直接取出元素,而且因为是数组所以内存空间上是连续的,不像 LinkedList是根据指针串联,内存地址上可能是不连续的。
LinkedList 的还有个优势时它既能当队列也能当栈来使用。