-
linkedList大多数时候被归类为List，但是更多的时候是被用于实现队列
-
本人就经常这样去定义一个队列，在有幸面试别人时，还问别人如何去new一个队列
Queue
queue = new linkedList<>(); -
因为，不懂为什么几乎能找到的资料都是这样定义队列的，希望面试者能给自己讲讲
面试别人是相互学习的过程
-
除此之外，自己还在学习linkedList的过程中发现，相比直接使用Stack类实现栈，更建议通过linkedList实现栈
# 不建议这样实现栈 Stack
stack = new Stack<>(); # 建议这样 linkedList stringStack = new linkedList<>();
linkedList的类注释，提供了以下信息
- linkedList是一个双向链表，实现了List 和Deque 接口，允许null值
- 基于双向链表，所有的操作都可以从头部或尾部进行：索引列表中的元素，可以从头部或尾部开始查找，这取决于索引距离哪端更近
- linkedList不是线程安全的，多线程访问时，可以通过Collections.synchronizedList()转为线程安全的list
- 可以通过iterator ()或listIterator()创建fail-fast 迭代器，一旦创建好迭代器，除非使用迭代器自身的remove或add方法，其他任何修改结构的方法，都将触发迭代器抛出ConcurrentModificationException 异常
总结：
- linkedList是双向链表，实现了List 和 Deque接口，允许null值
- 实现Deque接口，意味着linkedList除了可以实现list，还可以实现队列、双向队列和栈
- 非线程安全
- 使用fail-fast机制的迭代器
-
linkedList类的声明如下：
public class linkedList
extends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable -
类图如下图所示：继承了AbstractSequentialList抽象类，实现了List、Deque、Cloneable和Serializable接口
-
AbstractSequentialList抽象类
- 在了解AbstractList抽象类时，曾提到： AbstractList 是随机访问的数据结构，要想支持顺序访问应该使用 AbstractSequentialList
- AbstractSequentialList 对List 接口进行了骨架级实现，可以最小化实现一个支持顺序访问的数据结构（如，链表）所需的工作量
-
List接口：不允许重复元素的集合，允许null值
-
Deque接口：支持在两端插入或删除元素的线性集合，是double ended queue的简写，即双端队列。
-
Cloneable接口：表示linkedList 支持clone() 方法
-
Serializable接口：表示linkedList 支持序列化和反序列化
总结：
- 通过类图可知，linkedList是支持顺序访问的list，还可以用于实现队列、双向队列和栈
- 支持clone、序列化和反序列化
-
Deque接口非常有趣
- 继承Queue 接口，支持队列的添加、删除、peek操作
- 新增了双向队列所特有的、针对头部或尾部的方法（xxxFirst、xxxLast）
- 支持栈的push、pop、peek操作，甚至在类注释中大胆发言：
- This interface should be used in preference to the legacy Stack class
- 应该优先于遗留的Stack类使用
-
双向队列特有的方法
基于头部的操作 基于尾部的操作 抛出异常 返回特殊值 抛出异常 返回特殊值 添加 addFirst(e) offerFirst(e) addLast(e) offerLast(e) 删除 removeFirst() pollFirst() removeLast() pollLast() examine （查找） getFirst() peekFirst() getLast() peekLast() -
队列方法与双向队列方法的联系：
- 添加操作都是基于尾部，删除、examine操作都是基于头部，符合FIFO特性
- 此时，可以将队列想象成水管，尾部灌水、头部出水
Queue Method Deque的对等方法 add(e) addLast(e) offer(e) offerLast(e) remove() removeFirst() poll() pollFirst() element() getFirst() peek() peekFirst() -
栈方法与双向队列方法的联系：所有的操作都是基于头部的
Stack Method Deque的对等方法 push(e) addFirst(e) pop() removeFirst() peek() peekFirst() -
参考文档：Java集合框架（六）Deque接口
-
linkedList作为双向链表，首先链表节点应该有next和prev 引用才能构成双向链表
- 其构造方法只有一个，必须传入前驱节点、val、后继节点
private static class Node
{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } -
linkedList实现了Deque，存在基于头部或尾部的操作，应该同时拥有head 和tail 引用
- 双向队列的方法，都是基于First和Last做后缀，区分在哪一端做操作
- 因此，双向链表中，头尾不再叫做 head 、tail，而是叫做fisrt、last
- size
transient int size = 0; // 节点个数 // 指向链表的第一个节点，即链表头部 transient Node
first; // 指向链表的最后一个节点，即链表尾部 transient Node last; -
因此，linkedList的示意图如下
-
linkedList的构造函数如下：
- 十分简单，要么构造一个空的linkedList，要么基于现有的集合创建linkedList
// 默认构造函数，创建一个空的linkedList public linkedList() {} // 基于现有的集合创建linkedList public linkedList(Collection c) { this(); addAll(c); }
- 之前，学习linkedHashMap时，曾提到链表的特性：
- 支持快速的插入或删除元素：只需更新节点间的引用，而无需移动元素
- 考虑到linkedList同时实现了List 和 Deque接口，本博客将关注Deque的操作方法。
- 学习的过程中，我们可以体会到List / Queue接口中的方法与Deque方法的联系
-
addFirst 方法是基于双向链表头部的操作，代码如下
public void addFirst(E e) { linkFirst(e); } -
具体实现依靠linkFirst()方法完成
private void linkFirst(E e) { final Nodef = first; final Node newNode = new Node<>(null, e, f); // 创建一个新的头节点，其后继节点为原头结点 first = newNode; if (f == null) // 链表中只有一个节点 last = newNode; else // 更新原头结点的prev引用 f.prev = newNode; size++; modCount++; } -
示意图如下：
-
addLast 方法是基于双向链表尾部的操作，代码如下
public void addLast(E e) { linkLast(e); } -
具体实现依靠linkLast()方法
void linkLast(E e) { final Nodel = last; final Node newNode = new Node<>(l, e, null); // 新建尾节点 last = newNode; if (l == null) // 只有一个节点，尾结点也是头结点 first = newNode; else // 更新原尾结点的next引用 l.next = newNode; size++; modCount++; } -
示意图如下：
-
addFirst 和addLast 是抛出异常的方法，还有对应的返回特殊值的方法 offerFirst 和 offerLast
-
其实，都是同样的实现，只是增加了返回值
public boolean offerFirst(E e) { addFirst(e); return true; } public boolean offerLast(E e) { addLast(e); return true; } -
根据之前对Deque的学习，Queue中add、offer 方法，对应Deque中针对尾部的添加操作 —— Queue是尾部插入
public boolean add(E e) { linkLast(e); return true; } public boolean offer(E e) { return add(e); }
-
双向链表，获取头部或尾部节点，十分方便：直接获取first或last引用指向的节点即可
-
以抛出异常的examine方法为例，代码如下
public E getFirst() { final Nodef = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node l = last; if (l == null) throw new NoSuchElementException(); return l.item; } -
Queue的element() 和 peek()方法，Stack的peek()方法是从头部获取元素
public E element() { return getFirst(); } public E peek() { final Nodef = first; return (f == null) ? null : f.item; }
-
linkedList中，基于List接口的get方法是根据索引获取元素
- index是否越界检测：index >= 0 && index < size
- 通过 node() 方法获取index对应的节点
public E get(int index) { checkElementIndex(index); // 校验index是否越界 return node(index).item; // 根据索引获取节点，从而获取值 } -
在学习linkedList的类注释时，有这样一句话：索引元素时，可以从尾部或头部查找，这取决于索引距离哪端更近
-
node() 方法就是如此：通过index < (size >> 1)，决定从头部还是从尾部查找
Node
node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { // 索引在前半部分，从头部查找 Node x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 索引在后半部分，从尾部查找 Node x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
-
indexOf() ：元素在list中第一次出现的位置；lastIndexOf()：元素在list中最后一次出现的位置
-
linkedList和其他List一样：
- indexOf()则从头部开始寻找，lastIndexOf()则从尾部开始寻找，找到第一个匹配的位置就立即停止；
- 否则，返回-1
-
lastIndexOf()方法为例，展示其查找过程
public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Nodex = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
removeFirst()方法
-
为例，删除头部节点只需要断开头部节点与后继节点的连接、更新first引用即可
public E removeFirst() { final Nodef = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } -
依靠unlinkFirst()方法断开头结点与链表的连接
- 巧妙之处： 删除头节点，不只是将头结点从链表中断开，还节点中指向item引用置为null。这样gc时，可以更快地回收item
private E unlinkFirst(Node
f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; f.item = null; f.next = null; // 帮助gc first = next; if (next == null) // 无后继节点，说明本身就是尾结点 last = null; else // 后继节点成为新头节点，prev为null next.prev = null; size--; modCount++; return element; }
pollLast()方法
-
删除尾节点只需要断开尾结点与前驱节点的连接，更新last引用即可
public E pollLast() { final Nodel = last; return (l == null) ? null : unlinkLast(l); } -
依靠unlinkFirst()方法断开尾结点与链表连接
private E unlinkLast(Node
l) { // assert l == last && l != null; final E element = l.item; final Node prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) // 前驱节点为null，本身就是头结点 first = null; else // 前驱节点成为新的尾结点 prev.next = null; size--; modCount++; return element; } -
Queue的remove、poll方法，以及Stack的poll方法，都是基于头部的删除操作
public E remove() { return removeFirst(); } public E poll() { final Nodef = first; return (f == null) ? null : unlinkFirst(f); }
删除指定索引对应的元素
-
基于List接口的remove方法，要么根据索引删除元素，要么根据value删除第一个匹配的元素
-
根据索引删除元素：
- 通过node()方法，根据index找到对应的节点
- 依靠unlink()方法实现对应节点的删除
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } -
unlink()方法代码如下：
E unlink(Node
x) { // assert x != null; final E element = x.item; final Node next = x.next; final Node 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; } -
以删除中间节点为例，示意图如下
- 步骤1：前驱节点指向后继节点
- 步骤2：断开待删除节点与前驱节点的关联
- 步骤3：后继节点指向前驱节点
- 步骤4：断开待删除节点与后继节点的关联
删除指定元素
- remove(Object o)方法的代码如下
- 主要思想：从前往后遍历节点，找到匹配节点，通过unlink()实现删除
- 其中，节点的匹配（即节点值item的匹配），分为null值和普通值两种情况进行匹配
public boolean remove(Object o) { if (o == null) { for (Nodex = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; }
-
修改元素的值十分简单：
- 检查索引是否越界；未越界，则根据索引找到对应的节点
- 更新节点值item为指定值，并返回oldValue
public E set(int index, E element) { checkElementIndex(index); Nodex = node(index); E oldVal = x.item; x.item = element; return oldVal; }
-
linkedList的类注释中，有提到可以通过iterator()或listIterator()创建fail-fast迭代器
-
最开始，误理解成：和ArrayList一样，linkedList中包含Iterator和ListIterator两种迭代器
-
学习基于迭代器的遍历时，发现怎么没有Iterator迭代器，只有ListIterator迭代器 藍
-
甚至，连创建Iterator迭代器的iterator() 方法都没有
-
但是，却能调用iterator() 方法，通过debug确认访问的是从父类AbstractSequentialList 继承来的iterator() 方法
public static void main(String[] args) throws ParseException { linkedListstringStack = new linkedList<>(); Iterator iterator = stringStack.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); } } -
AbstractSequentialList 的iterator() 方法，代码如下：
- 实际调用listIterator() 方法，即最终创建的是 ListIterator，而非Iterator
- linkedList的ListIterator类为ListItr，
public Iterator
iterator() { return listIterator(); } -
基于Iterator迭代器的所有操作，实际都是基于ListIterator的操作，通过debug可以证明
-
使用ArrayList时，我们经常通过索引遍历元素，而非通过for-each或迭代器
public static void main(String[] args) throws ParseException { ArrayListarrayList = new ArrayList<>(); arrayList.add(1); arrayList.add(2); for (int i = 0; i < arrayList.size(); i++) { System.out.println(arrayList.get(i)); } } -
从未有人说过，这样遍历性能低下，不建议这样遍历的话
- 因为，ArrayList是一个动态数组，支持随机访问
- 通过索引获取元素的时间复杂度为 O ( 1 ) O(1) O(1)
- 遍历整个list，也就是$O(n)$
-
如果，使用linkedList这样遍历，别人会对你说NO的
- 究其原因，还是因为linkedList是双向链表，只能顺序访问，不支持随机访问
- 其get by index的方法非常笨拙，每次会从头部或尾部开始查找元素，获取单个元素的时间复杂度不再是 O ( 1 ) O(1) O(1)
- 整体的时间复杂度，可能为 O ( n 2 ) O(n^2) O(n2)
- get by index的具体代码，可以查看上文
-
因此，遍历linkedList中的元素，建议使用for-each或迭代器
疑问：迭代器的效率就很高吗？
- ListItr 的核心代码如下：
- 可以从某个位置开始创建迭代器，而非一定要从头部开始创建迭代器
- 一旦通过node()方法，找到起始节点，后续的节点遍历就是 O ( 1 ) O(1) O(1)的时间复杂度
private class ListItr implements ListIterator
{ private Node lastReturned; private Node next; // 记录待访问的节点 private int nextIndex; // 记录待访问的节点索引 private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } }
-
leet-code：232. 用栈实现队列
-
刚学习了linkedList，这里就使用linkedList实现队列
class MyQueue { linkedListqueue; public MyQueue() { queue = new linkedList<>(); } public void push(int x) { queue.add(x); } public int pop() { return queue.poll(); } public int peek() { return queue.peek(); } public boolean empty() { return queue.isEmpty(); } }
-
leet-code：225. 用队列实现栈
-
刚学习了linkedList，这里就使用linkedList实现栈
class MyStack { linkedListstack; public MyStack() { stack = new linkedList<>(); } public void push(int x) { stack.push(x); } public int pop() { return stack.pop(); } public int top() { return stack.peek(); } public boolean empty() { return stack.isEmpty(); } }
linkedList的多样性
- 实现了List接口，是支持顺序访问的list，很少将linkedList当做数组使用
- 实现了Deque接口，同时支持队列、双向队列和堆栈
- 基于双向链表以支持双向队列，其操作均支持基于头部（xxxFirst）和尾部（xxxLast）的操作
- 队列操作与双向队列操作的对应关系（尾进头出）、栈操作与双向队列操作的对应关系（头进头出）
linkedList与ArrayList的异同
-
相同点
- 实现了List接口，允许null元素
- 非线程安全
- 使用fail-fast迭代器
-
不同点：
- linkList基于双向链表，支持顺序访问；ArrayList基于动态数组，支持随机访问，访问效率更高
- 随之而来，linkedList插入或删除元素的效率更高，只需要更该节点间的引用，而ArrayList需要移动元素
- 二者都是容量可增长的list，但底层原理不同：一个通过增加节点实现，一个通过扩容实现 (虽然不是重点，但需要注意)
参考文档
- linkedList 源码分析(JDK 1.8) （还是大佬图文并茂的博客，点出了get by index的遍历效率低下）
- JDK1.8源码(六)——java.util.linkedList 类 （有两种遍历的性能差异比较）
- JDK1.8 linkedList详解（全面、详尽）
- Java集合框架之linkedList详解（数据结构图参考）
