一起探秘,不可不知双向链表底层原理
双向链表与数据结构
引言
在上小节中
我们分析了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 linkedList = new LinkedList();
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
1.3.1 链表成员变量与内部类
我们先来定义几个叫法,后面会用到它
文章图片
transient int size = 0;
//元素个数
transient Node first;
//头结点引用(查询时获取)
transient Node last;
//尾节点引用(查询时获取)private static class Node { //链表节点元素,封装了真实数据,同时加入了前后指针
E item;
//元素,这是放入的真实数据
Node next;
//下一个节点,指针也是Node类型
Node prev;
//上一个节点//构造器,前、值、后,很清晰
Node(Node prev, E element, Node 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 :【 0001111(pred) (index)2222(succ) 33333 …… 】
Node 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 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 l = last;
//取出当前最后一个节点
final Node 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 node(int index) {
// 这里有一个讨巧的设计!很灵活的应用了我们的first和lastif (index < (size >> 1)) { // index如果小于链表长度的1/2 (size右移1就是除以2)
Node x = first;
for (int i = 0;
i < index;
i++) //从链表头开始移动 index 次
x = x.next;
//依次往后指
return x;
//循环完后,就找到了index位置的node,返回即可
} else { //否则,说明index在链表的后半截,我们从链表尾部倒着往前找
Node x = last;
for (int i = size - 1;
i > index;
i--) //一直循环,直到index位置
x = x.prev;
return x;
//抓到后返回,完工!
}
}
//画图展示
void linkBefore(E e, Node succ) { //找到之后,也就是这里的succ,我们就开始在它前面插入新元素
// assert succ != null;
final Node pred = succ.prev;
//上个节点
final Node 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 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 x = first;
x != null;
x = x.next) {//从fist顺着链表往后找
if (x.item == null) { //发现就干掉
unlink(x);
//重点!干掉元素调用的其实是unlink方法
return true;
}
}
} else {
for (Node 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 x) {
// assert x != null;
final E element = x.item;
//元素
final Node next = x.next;
//下个节点
final Node 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;
//已删除元素
}
本文由传智教育博学谷 - 狂野架构师教研团队发布,转载请注明出处!
【一起探秘,不可不知双向链表底层原理】如果本文对您有帮助,欢迎关注和点赞;如果您有任何建议也可留言评论或私信,您的支持是我坚持创作的动力
推荐阅读
- 一起聊聊Java中13种锁的实现方式
- 陪伴,与孩子一起成长是最好的早教(一)
- 经典《亮剑》,欢迎你我一起评
- 中烹协悬赏30万+大奖,鱼你在一起寻找民间酸菜鱼大师,免费报名参赛!
- 新特性解读 | MySQL 8.0 GIPK 不可见主键
- 和什么人在一起,真的很重要
- 20190309日记
- 投稿|在朋克之都,你永远不可能低下高昂的头
- 最美的不是下雨天,而是和你一起躲过的屋檐
- 2017我们一起征文|做最好的自己