共计 9366 个字符，预计需要花费 24 分钟才能阅读完成。
linkedlist,LinkedList 遍历,linkedlist 实现,linkedlist 和 arraylist 区别,linkedlist 线程平安,linkedlist 源码
微信关注【面试情报局】咱们一起干翻面试官。
1. 前言
明天咱们要钻研的汇合是 LinkedList，在咱们学习LinkedList 之前，咱们先看看 LinkedList 的相干面试题。
1.
LinkedList的构造。
2.LinkedList插入元素的具体过程。
3.LinkedList和ArrayList的区别。
4.……
这些面试题都是考查咱们对链表这种构造是否有理解，是否有看过相干源码实现；只有看过源码，这些问题答复起来很是轻松；废话不多说，让咱们一起来看看 LinkedList 的源码实现。
2. 概述
LinkedList 底层实现是一个双向链表，这种构造非常适合队列 (先入先出) 和栈 (先入后出) 的操作；并且他实现了 List 和Deque接口，所以它不仅有列表的操作还有队列相干的操作；其实现的队列和栈的出队入队，出栈入栈操作工夫复杂度均为O(1)，如下是其构造示意图：
3. 类图
AbstractSequentialList抽象类，提供了 List 接口的相干实现和迭代逻辑的实现，不过对LinkedList意义不大，因为LinkedList大量重写了其中的实现List接口，定义了数组的增删改查迭代遍历等相干操作。Cloneable接口，反对LinkedList克隆Serializabel接口，反对LinkedList序列化与反序列化Deque接口，定义了队列两端插入和删除元素的相干操作。
4. 属性
首先让咱们看看源码中的定义：
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{// 链表大小(贮存元素的个数)
transient int size = 0;
// 头结点
transient Node<E> first;
// 尾结点
transient Node<E> last;
// 贮存元素的类(节点)
private static class Node<E> {
// 理论贮存的元素
E item;
// next 节点
Node<E> next;
// prev 节点
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 该属性是通过继承 AbstractList 得来, 列表批改的次数(版本号)
protected transient int modCount = 0;
}Node是链表中贮存数据的节点，他有三个属性item（存储元素），next（指向下一个节点），prev（指向上一个节点）。size双向链表的节点个数。first双向链表头，头节点的prev指向null。last双向链表尾，尾节点的next指向null。modCount版本号，记录批改次数。
5. 罕用办法
5-1. 新增
LinkedList的新增分三类：首节点新增，指定索引节点新增，尾节点新增。首先，看看对 List\` 接口实现的新增：
// 将指定的元素追加到此列表的开端。此办法等效于 addLast（E）。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++;
}
如图咱们能够晓得，在向开端增加元素时先预存了 last 节点，而后结构新节点 newNode 并连贯到以后尾节点，而后在更新 newNode 节点为 last 节点，最初在将节点连贯实现。
指定索引节点新增：
// 将指定的元素插入此列表中的指定地位。将以后在该地位的元素（如果有）和任何后续元素右移（将其索引加一）。public void add(int index, E element) {checkPositionIndex(index);
// 小优化
if (index == size)
linkLast(element);
else
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;
}
}
// 在非 null 节点 succ 之前插入元素 e
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;
// 判断 succ 是否为头节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
如图咱们能够晓得，在指定索引地位增加元素时有 5 步：
- 通过
node(int index)办法找到指定索引节点succ - 先预存指定索引节点
succ的prev节点为pred - 构建新节点
newNode并连贯指定索引节点succ的prev节点和指定索引节点succ - 将指定索引节点
succ的prev指向newNode节点 - 将预存的
prev节点pred的next节点指向newNode节点
通过源码咱们还能够晓得，node(int 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;
}
}它通过 一次二分的形式，定位了索引在前半段还是后半段，缩小了一半的查问工夫，进步了查问效率。
上面是增加汇合到链表的办法，插入方式和下面根本类似。
// 将指定汇合中的所有元素追加到此列表的开端，依照指定汇合的迭代器返回它们的程序。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;
// 贮存上一位元素和以后 index 地位的元素
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;
}LinkedList不仅实现了 List 接口，还实现了 Deque 接口，上面看看 Deque 接口的实现：
// 将指定的元素插入此列表的结尾。public void addFirst(E e) {linkFirst(e);
}
// 将元素增加到列表头
private void linkFirst(E e) {
// 预存头结点
final Node<E> f = first;
// 结构新节点
final Node<E> newNode = new Node<>(null, e, f);
// 新节点降级为头节点
first = newNode;
// 将新节点和链表链接
// 判断是否为第一个插入的节点
if (f == null)
last = newNode;
else
f.prev = newNode;
size++; // 链表大小加一
modCount++; // 版本号加一
}
// 将指定的元素追加到此列表的开端。此办法等效于 add（E）。public void addLast(E e) {linkLast(e);
}
// 将元素增加到列表尾
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 boolean offer(E e) {return add(e); // add(E e)->linkLast(E e)
}
// 将指定的元素插入此列表的后面。public boolean offerFirst(E e) {addFirst(e); // addFirst(E e)->linkFirst(E e)
return true;
}
// 将指定的元素插入此列表的开端。public boolean offerLast(E e) {addLast(e); // addLast(E e)->linkLast(E e)
return true;
}
// 将元素压入此列表示意的堆栈。换句话说，将元素插入此列表的后面。此办法等效于 addFirst（E）。public void push(E e) {addFirst(e); // addFirst(E e)->linkFirst(E e)
}通过源码咱们发现 LinkedList 实现 Deque 接口的插入最终都是调用 linkFirst(E e) 和linkLast(E e)，其插入过程在源码中以具体正文。
5-2. 删除
首先咱们看看 LinkedList 对List接口的实现：对指定元素对象删除和对指定节点删除
// 如果存在指定元素，则从该列表中删除该元素的第一次呈现。// 如果此列表不蕴含该元素，则它放弃不变。// 如果此列表蕴含指定的元素，则返回 true。public boolean remove(Object o) {if (o == null) { // 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)) { // 自定义元素对象，留神重写 equals
unlink(x);
return true;
}
}
}
return false;
}
// 勾销链接 x 节点
E unlink(Node<E> x) {
// assert x != null;
// 预存 x 节点 Item
final E element = x.item;
// 预存 x 节点下一位节点
final Node<E> next = x.next;
// 预存 x 节点上一位节点
final Node<E> prev = x.prev;
// x 的上一位节点链接 x 的下一位节点
if (prev == null) {first = next;} else {
prev.next = next;
x.prev = null;
}
// x 的下一位节点链接 x 的上一位节点
if (next == null) {last = prev;} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
// 删除此列表中指定地位的元素。将所有后续元素向左挪动（从其索引中减去一个）。返回从列表中删除的元素。public E remove(int index) {checkElementIndex(index);
return unlink(node(index));
}通过源码发现，最终删除都是通过 unlink(Node<E> x) 来实现，过程如下图：
咱们再来看看 LinkedList 对Deque接口的实现:
// 检索并删除此列表的头（第一个元素）。public E remove() {return removeFirst(); // -> unlinkFirst(f)
}
// 从此列表中删除并返回第一个元素。public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 勾销链接非空的第一个节点 f
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
// 预存 first 节点的 Item
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;
}
// 从此列表中删除并返回最初一个元素。public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// 勾销链接非空的最初一个节点 l
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
// 预存 last 节点 Item
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;
}
// 检索并删除此列表的第一个元素，如果此列表为空，则返回 null。public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
// 检索并删除此列表的最初一个元素，如果此列表为空，则返回 null。public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
// 检索并删除此列表的头（第一个元素）。public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}从源码中咱们能够晓得 LinkedList 对Deque的删除实现, 最终都都是调用的 unlinkFirst(Node<E> f) 和unlinkLast(Node<E> l)，其移除过程在源码中有具体正文。
5-3. 批改
老规矩，还是先看看源码实现：
// 用指定的元素替换此列表中指定地位的元素。public E set(int index, E element) {checkElementIndex(index);
// 返回指定元素索引处的（非空）节点。Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}LinkedList实现的批改过程非常简略：
- 首先查看索引是否非法
>=0&&<size。 - 其次通过
node(int index)找到要批改的节点。 - 最初批改
item，返回旧值。
5-4. 查问
LinkedList对 List 接口的查问实现包含：通过索引查问和通过元素查问(从前往后和从后往前)
// 返回此列表中指定地位的元素。public E get(int index) {checkElementIndex(index);
return node(index).item;
}
// 如果此列表蕴含指定的元素，则返回 true。// 更正式地说，当且仅当此列表蕴含至多一个元素（e == null？e == null：o.equals（e））时，返回 true。public boolean contains(Object o) {return indexOf(o) != -1;
}
// 返回指定元素在此列表中首次呈现的索引；如果此列表不蕴含该元素，则返回 -1。// 更正式地，返回最低索引 i，使其（o == null？get（i）== null：o.equals（get（i）））;
// 如果没有这样的索引，则返回 -1。public int indexOf(Object o) {
int index = 0;
if (o == null) {for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)
return index;
index++;
}
} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}
// 返回指定元素在此列表中最初一次呈现的索引；如果此列表不蕴含该元素，则返回 -1。public int lastIndexOf(Object o) {
int index = size;
if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}LinkedList对 Deque 接口的查问实现：
// 检索但不删除此列表的头（第一个元素）public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 检索但不删除此列表的第一个元素，如果此列表为空，则返回 null。public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
// 检索但不删除此列表的最初一个元素，如果此列表为空，则返回 null。public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}6. 总结
从源码中咱们能够看出链表实现队列和栈十分有劣势，只须要对表头和表尾进行操作既可。而且 LinkedList 的属性刚好保留了头和尾的援用，所以整个操作都是 O(1) 的工夫复杂度。
当初咱们在来看看最开始的面试题:
1.
LinkedList的构造。
2.LinkedList插入元素的具体过程。
3.LinkedList和ArrayList的区别。
通过源码的学习 1,2 两个题目能够很轻松的答复，咱们重点钻研第 3 个问题：LinkedList和 ArrayList 的区别。
通过上一篇《咱们一起学汇合》-ArrayList文章的学习，咱们能够晓得 ArrayList 底层是基于数组实现的反对动静扩容的一种数据结构
，他随机拜访快，随机插入和删除慢 (因为会挪动元素) 和LinkedList的区别有：
- 构造不同：
ArrayList是基于数组，LinkedList是基于节点Node - 效率不同：
ArrayList随机拜访比LinkedList效率高，因为LinkedList必须每次从头遍历查找 - 贮存不同：
ArrayList须要大量的间断贮存空间，并且在间断扩容后会产生较多存碎片，而LinkedList不须要间断的贮存空间，这意味着它能够应用更多内存，但它贮存每个元素耗费的内存也更多，因为他必须放弃每个节点的prev和next援用。
从实践上讲 ArrayList 删除一个元素的效率是比 LinkedList 低，应为 ArrayList 删除一个不是开端的元素会产生元素拷贝，而 LinkedList 删除一个元素只是批改前后节点的援用。
从实践上讲是这样，但在理论中，因为古代计算机体系结构的缘故 (cpu 缓存)，在简直所有可能的用例中，ArrayList 的效率都将大大提高。次要是 LinkedList 的节点随机散布在整个内存中。RAM（“随机拜访内存”）并不是真正随机的，须要获取内存块以进行缓存。此操作须要工夫，并且当此类获取频繁产生时缓存中的内存页面须要始终替换 -> 缓存未命中 -> 缓存效率不高。 ArrayList元素存储在间断内存中，这更利于缓存。这也正是古代 CPU 体系结构正在优化的内容。
集体认为 ArrayList 和LinkedList的选用是一个简单的问题，须要依据不同的场景和思考后能力决定。集体偏向在个别状况下优先应用ArrayList。
参考文章：
https://stackoverflow.com/que…
https://stackoverflow.com/que…