小知识,大挑战!本文正在参与“程序员必备小知识”创作活动
一、前言
今天花哥继续和大家一块学习源码,之前我们一起学习了ArrayList的底层实现,那今天就来图解LinkedList的实现原理。
注意:本文基于JDK1.8
二、课前准备
说到LinkedList,我相信掘金等级一级以上的小伙伴都能蹦出来很多词,像双向链表、有序集合、增删快查询慢等等,毕竟这也是面试高频题,背了n遍了,那接下来的问题是,什么是双向链表呢?为什么增删快查询慢?增删是怎么实现的?迭代方法是什么?......。
面对这一连串的问题,今天花哥就带小伙伴们走一遭,看完就肯定学会了。
-
什么是链表?
这是今天的第一个问题,要首先知道什么是链表,我们先从简单的单向链表来看,看下面这个优秀的图示,秒懂。
从图中可以看出,每个链表由一个个节点组成,节点我们称为Node,单向链表的Node结构除了用有存储自身内容的data外,还有next,代表后一个节点的位置(引用)。
-
什么是双向链表
双向链表也是由一个个Node组成,每个Node的结构由prev、data、next组成,相较于单向链表,双向链表中多了一个用于指向上一个节点的prev,首先简单说一下图中各个属性的作用:
- prev:存储上一个节点的引用;
- data:存储当前节点的具体内容;
- next:存储下一个节点的引用;
- First:双向链表的头节点,他的上一个节点是null;
- Last:双向链表尾结点,他的下一个节点时null;
值得注意的是,如果链表中没有存储数据,那它的First和Last为同一个,并且它的prev和next都是null。
接下来看一下LinkedList代码中Node的代码实现:
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
复制代码
三、LinkedList源码分析
铺垫了这么多,接下来就正式分析LinkedList的源码部分,主要是探讨一下链表新增删除查询的实现原理。
-
尾部增加节点(linkLast)
LinkedList的新增方式有两种,头部增加和尾部增加,我们常用的add实际采用的是尾部增加方式,看下面这段源码解析:
/**
*尾部增加节点
*/
void linkLast(E e) {
//暂存尾节点
final Node<E> l = last;
//创建新节点:新建节点的prev为l(当前尾结点),next为null
final Node<E> newNode = new Node<>(l, e, null);
//将新建节点更新为尾节点
last = newNode;
//判断链表中是否存在数据,l即尾结点,尾结点若为null,则链表就是空
if (l == null)
//若不存在,将头节点指向新增节点
first = newNode;
else
//若存在,将原尾结点的next指向新建节点
l.next = newNode;
//更新链表大小和版本
size++;
modCount++;
}
复制代码
可以将上述代码用图示展示:
- 首先,创建一个节点Node4,并将当前节点更新为尾结点
- 如果链表不为null时,将当前链表尾结点Node3中next引用指向当前节点
- 若链表为空,则将当前节点设置为头节点,链表结构如下图
-
头部增加节点(linkFirst)
头部增加的方式基本和上述方法一致,只是新建节点追加到链表头部。
/**
* 头部增加节点
*/
private void linkFirst(E e) {
//暂存头节点
final Node<E> f = first;
//创建新节点,next指向头节点
final Node<E> newNode = new Node<>(null, e, f);
//新建节点设置为头节点
first = newNode;
//判断链表是否为空
if (f == null)
//链表为空,尾结点设置为当前节点
last = newNode;
else
//链表不为空,原头节点的prev指向新建节点
f.prev = newNode;
//更新链表大小和版本
size++;
modCount++;
}
复制代码
-
头部删除节点(unlinkFirst)
删除节点同样也是有两种方式,先说一下尾部删除,我们常用的remove方法就是通过头部删除,先看下源码:
/**
* 头部删除节点
* f:头节点
*/
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
//将头节点指向null,帮助GC回收
f.item = null;
f.next = null;
//将下一个节点设置为头节点
first = next;
//若下一个节点为空,则设置尾结点为null,否则将下一个节点的prev置空
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
//返回被删除节点内容
return element;
}
复制代码
继续用老套路,使用图示的方式看一下这个过程实现:
- 将头节点的data、next都指向null,方便GC回收资源
- 如果当前链表不止一个元素,就会将原头节点(Node1)中next指向的节点(Node2)设置为头节点,并将Node2中prev置空,至此完成全部的删除过程
- 如果链表仅包含当前这一个节点,就会将尾结点直接设置为null
-
尾部删除节点(unlinkLast)
尾部删除和上述方法几乎一致,代码简单介绍一下即可。
/**
* 尾部删除节点
* l:尾结点
*/
private E unlinkLast(Node<E> l) {
final E element = l.item;
//暂存尾结点的上一个节点地址
final Node<E> prev = l.prev;
l.item = null;
l.prev = null;
//将上一个节点设置为尾结点
last = prev;
//若上一个节点为空,则设置头结点为null,否则将上一个节点的next置空
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
复制代码
-
查找指定节点
LinkedList使用二分法来查找数据,首先判断目标节点所处的位置,是前半部分还是后半部分,然后通过遍历最终查找到目标节点,从而提高查询效率。
Node<E> node(int index) {
//size >> 1 :右移1位,相当于size除以2
//先使用二分法,判断目标节点在哪一半
if (index < (size >> 1)) {
Node<E> x = first;
//从头节点开始遍历,直至目标节点的前一个node时停止
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
//从尾结点向前遍历,直至目标节点的后一个node时停止
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
复制代码
四、总结
LinkedList底层由双向链表结构,可以被当做堆栈、队列来操作,适用于快速插入、删除的场景,同时它也是面试高频题,通过本文的学习,相信小伙伴也会有所收获的。
近期评论