简介
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 将遍历降低成了链表长度的一半：
如果 index 在头和中点之间，那么就从头开始遍历到中点。
如果 index 在中点和尾之间，那么就从尾开始遍历到中点。
双向链表的优势就凸显出来的，相对而言插入的效率比 ArrayList 高，毕竟 ArrayList 需要拷贝 index 后的数组。但是查询效率就低了，ArrayList 根据下标能直接取出元素，而且因为是数组所以内存空间上是连续的，不像 LinkedList是根据指针串联，内存地址上可能是不连续的。
LinkedList 的还有个优势时它既能当队列也能当栈来使用。
最后：
上面都是自己整理好的！我就把资料贡献出来给有需要的人！顺便求一波关注，哈哈~各位小伙伴关注我后私信【Java】就可以免费领取哒
作者：sidfate
链接：https://juejin.im/post/5e50d7805188254945386262
网友评论