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之前插入元素evoid 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);}
// 取消链接非空的第一个节点fprivate 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);}// 取消链接非空的最后一个节点lprivate 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实现的修改过程十分简单：
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/questions/322715/when-to-use-linkedlist-over-arraylist-in-java/24607151#24607151
https://stackoverflow.com/questions/11667955/difference-between-arraylist-and-linkedlist
微信关注【面试情报局】我们一起干翻面试官。
评论