共计 6470 个字符，预计需要花费 17 分钟才能阅读完成。
双向链表与数据结构
引言
在上大节中
咱们剖析了 ArrayList 的底层实现，晓得了 ArrayList 底层是基于数组实现的，因而具备查找批改快而插入、删除慢的特点
本章咱们介绍的 LinkedList 是 List 接口的另一种实现
它的底层是基于双向链表实现的
因而它具备插入、删除快而查找批改慢的特点什么是 LinkedList
LinkList 是一个双向链表（双链表）；它是链表的一种，也是最常见的数据结构，其外部数据呈线性排列，属于线性表构造.
它的每个数据结点中都有两个指针，别离指向间接后继和间接前驱。所以，从双向链表中的任意一个结点开始，都能够很不便地拜访它的前驱结点和后继结点，所以是双向链表.
LinkList 特点：
链表: 劣势：不是间断的内存，轻易插入（前、两头、尾部）插入 O(1) 劣势：查问慢 O(N)
线程不平安的，容许为 null，容许反复元素
蓝色示意；可随便插入、删除
查问循环循环链表
总结
双链表的节点既有指向下一个节节点的指针，也有指向上一个结点的指针（双向读）
所谓指针，就是指向其余节点的一个对象的援用（说白了就是定义了两个成员变量）
双向链表线程不平安的，容许为 null，容许反复元素
查问 O(n)
插入删除 O(1)
1.2 双向链表继承关系
LinkedList 是一个继承于 AbstractSequentialList 的双向链表。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，能将 LinkedList 当作 双端队列（double ended queue）应用。
LinkedList 实现了 Cloneable 接口，即笼罩了函数 clone()，能克隆。
LinkedList 实现 java.io.Serializable 接口，这意味着 LinkedList 反对序列化，能通过序列化去传输。
1.3 双向链表源码深度分析
案例代码
com.llist.LList
package com.llist;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
public class LList {public static void main(String[] args) {LinkedList<String> linkedList = new LinkedList<String>();
linkedList.add("100");// 尾插, 等价于 linkedList.addLast()
linkedList.add("200");
linkedList.add("300");
//******* 两头插入 linkedList..add(3,"700")*************
linkedList.add("400");
linkedList.add("500");
linkedList.add("600");
System.out.println(linkedList);
linkedList.add(3,"700");// 两头插入
System.out.println(linkedList);
//******* 批改 ***************************************
linkedList.set(3,"700000000");
System.out.println(linkedList);
//******* 查问 ***************************************
System.out.println(linkedList.getFirst());// 头查
System.out.println(linkedList.getLast());// 尾查
// for(int s=0;s<linkedList.size();s++){// System.out.println(linkedList.get(s));// 随机插
// }
//******* 移除 ***************************************
LinkedList<String> linkedListRemove = new LinkedList<String>();
linkedListRemove.add("100");
linkedListRemove.add("200");
linkedListRemove.add("300");
linkedListRemove.remove(1);// 指定移除
linkedListRemove.removeAll(linkedList);// 也调用下面的 unlink 办法；LinkedList.ListItr.remove
}
}
1.3.1 链表成员变量与外部类
咱们先来定义几个叫法，前面会用到它
transient int size = 0;// 元素个数
transient Node<E> first;// 头结点援用（查问时获取）transient Node<E> last;// 尾节点援用（查问时获取）private static class Node<E> { // 链表节点元素，封装了实在数据，同时退出了前后指针
E item;// 元素，这是放入的实在数据
Node<E> next;// 下一个节点，指针也是 Node 类型
Node<E> prev;// 上一个节点
// 结构器，前、值、后，很清晰
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;// 新元素
this.next = next;// 下个节点
this.prev = prev;// 上个节点
}
}1.3.2 双向链表结构器
无参结构器: 没有做任何事件
public LinkedList() { // 无参结构器}有参结构器：传入内部汇合的结构器
public LinkedList(Collection<? extends E> c) {this();
addAll(c);
}机密就藏在 addAll 上（重点，画图展现）
public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index); // 边界判断
Object[] a = c.toArray(); // 不论你传啥类型，对立转成数组
int numNew = a.length; // 须要新插入的个数
if (numNew == 0)
return false;
// 两个指针，这俩示意你要插入点的前后两个节点。咱们称之为前置 node 和后置 node
// 比方你的 index=2：【000 1111（pred）（index）2222（succ）33333 ……】Node<E> pred, succ;
if (index == size) { // 上面就要定位到这俩指针的地位
succ = null; // 如果指定的 index 和尾部相等，很显然后置是没有的
pred = last; // 前置就是最初一个元素 last
} else {succ = node(index); // 否则的话，后置就是以后 index 地位的 node，这个办法上面有具体介绍先不论它
pred = succ.prev; // 前置就是以后 index 地位的 prev，很好了解
}
for (Object o : a) { // 开始循环遍历插入元素
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); // 定义个新节点，包装以后元素
if (pred == null) // 如果前置为空，留神什么时候才为空？只有头插或以后 list 没有元素的时候
first = newNode; // 阐明是第一次放入元素，将 first 指向以后元素，竣工
else
pred.next = newNode; // 否则的话，前置 node 的后指针指向以后元素（接上了）pred = newNode; // 让前置指针后移，指向刚新建的 node，为下一次循环做筹备
} // 顺次循环，往上接，接完后，pred 就是最初一个插入的元素
// 全副循环接完当前，再来解决新接链条的后指针
if (succ == null) { // 如果后置是 nul 的话，阐明咱们始终在尾部插入
last = pred; // 将 last 指向最初一个插入的元素即可，它就是尾巴
} else {
pred.next = succ; // 否则的话，最初一个插入的 next 指向原来插入前的后置
succ.prev = pred; // 后置的前指针指向最初插入的元素，这两步是一对操作缺一不可
} // 到此为止，截断的后半截链条也对接上了。size += numNew; // 最初不要遗记，元素数量减少
modCount++; // 操作计数器减少
return true;
}1.3.3 链表插入（重点）
1）双向链表尾插法
1、add(E e)，
2、addLast；
调用的办法都一样（linkLast）
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); // 创立一个新节点，留神其前驱节点为 l
last = newNode;// 尾指针指向新节点
if (l == null)// 如果原来的尾巴节点为空，则示意链表为空，则将 first 节点也赋值为 newNode
first = newNode;
else
l.next = newNode; // 否则的话，将原尾巴节点的后指针指向新节点，形成双向环
size++;// 计数
modCount++; // 计数
}论断：默认 add 就是尾插法，追加到尾部
2）双向链表两头插入
指标：将 700 插入到 400 的地位
插入前
插入后的
双向链表两头插入 add(int index, E element)
// 自定义插入
linkedList.add(3,"700");源码如下
public void add(int index, E element) {checkPositionIndex(index);// 越界查看
if (index == size)// 如果 index 就是指向的尾部，天然调尾插即可
linkLast(element);
else
linkBefore(element, node(index));// 否则的话，找到 index 地位的 node，插队到它后面去
} /**
* 那它怎么找的呢？看以下办法（画图展现）*/
Node<E> node(int index) {
// 这里有一个讨巧的设计！很灵便的利用了咱们的 first 和 last
if (index < (size >> 1)) { // index 如果小于链表长度的 1 /2（size 右移 1 就是除以 2）Node<E> x = first;
for (int i = 0; i < index; i++) // 从链表头开始挪动 index 次
x = x.next; // 顺次往后指
return x; // 循环完后，就找到了 index 地位的 node，返回即可
} else { // 否则，阐明 index 在链表的后半截，咱们从链表尾部倒着往前找
Node<E> x = last;
for (int i = size - 1; i > index; i--) // 始终循环，直到 index 地位
x = x.prev;
return x; // 抓到后返回，竣工！}
} // 画图展现
void linkBefore(E e, Node<E> succ) { // 找到之后，也就是这里的 succ，咱们就开始在它后面插入新元素
// assert succ != null;
final Node<E> pred = succ.prev;// 上个节点
final Node<E> newNode = new Node<>(pred, e, succ);// 构建新的双向节点
succ.prev = newNode;// 批改后置节点的前指针
if (pred == null) // 如果前驱节点为空，链表为空
first = newNode; // 那么以后插入的就是头节点
else
pred.next = newNode;// 否则批改前置的后指针，指向新节点，双向链表对接胜利！size++;// 个数加 1
modCount++;// 批改次数加 1
}1.3.4 双向链表批改办法
非常简单！
找到包装值的 node，批改掉外面的属性即可
public E set(int index, E element) {checkElementIndex(index);// 越界查看
Node<E> x = node(index);// 通过链表索引找到 node
E oldVal = x.item;// 获取原始值
x.item = element;// 新值赋值
return oldVal;// 返回老值
}1.3.5 双向链表查询方法
简略！
get(int index)：依照下标获取元素；通用办法
getFirst()：获取第一个元素；特有办法，间接拿指针就是
getLast()：获取最初一个元素；特有办法，同样间接拿指针
public E get(int index) {checkElementIndex(index);// 越界查看
return node(index).item;// 找到原始数组对应 index 的 node
}System.out.println(linkedList.getFirst());// 头查System.out.println(linkedList.getLast());// 尾查1.3.6 双向链表删除办法
remove(E e)：移除指定元素；通用办法
removeAll(Collection<?> c) 移除指定汇合的元素; 也调用的 unlink 办法
两步走：1 找，2 删
public boolean remove(Object o) {if (o == null) { // 如果要移除 null 元素
for (Node<E> x = first; x != null; x = x.next) { // 从 fist 顺着链表往后找
if (x.item == null) { // 发现就干掉
unlink(x); // 重点！干掉元素调用的其实是 unlink 办法
return true;
}
}
} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item)) { // 如果不是移除 null 的话，路子一个样，无非就是 == 换成 equals 判断
unlink(x);
return true;
}
}
}
return false;
} /**
* 画图展现：将要移除的 Node，比方【100】【200】【300】*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;// 元素
final Node<E> next = x.next;// 下个节点
final Node<E> prev = x.prev;// 上个节点
if (prev == null) {first = next;// 上个为空，阐明以后要移除的就是头节点，将 fist 指针指向后置，我被移除后它降级为头了} else {
prev.next = next; // 否则，前置的后指针指向后置
x.prev = null; // 以后节点的前指针切断！}
if (next == null) {last = prev;// 后置为空阐明以后要移除的是尾节点，我被移除后，我的前置成为尾巴} else {
next.prev = prev; // 否则，后置的前指针指向前置节点
x.next = null; // 以后节点的后指针切断！} // 到这里前后指针就理清了，该断的断了，该接的接了
x.item = null;// 把以后元素改成 null，交给垃圾回收
size--;// 链表大小减一
modCount++;// 批改次数加一
return element; // 已删除元素
}本文由传智教育博学谷 – 狂野架构师教研团队公布，转载请注明出处！
如果本文对您有帮忙，欢送关注和点赞；如果您有任何倡议也可留言评论或私信，您的反对是我保持创作的能源
正文完