数据结构线性结构篇—链表

一、前言

在前面两章我们讲解了动态数组、栈和队列的讲解，这些底层都是依托静态数组，靠 resize解决固定容量问题的，之前虽然用户看到的是动态数组，但是依+ ? S然使用的是静态数组，他是依靠 resize 这个方法解决 固定容量问题 ，但是我们今天要讲解的 链表 不一样，链表是我们数据结构学习的一个重点，也有可能是一个难点，为什么链表这么重要呢?因为他是最简单的也是 真正的动态数据结构。

二、为什么链表很重要

• 链表是一个真正的动态数据结构
• 最简单的动态数据结构
• 更深入的理解引用(或者指针)
• 更深入的理解递归
• 辅助组成其他数据结构

更深入{ ` m的理解引用(或者指H ^ r = N \ Q A –针)：和内存相关，虽然_ z s Z E A在 java 中大家` j ( = &不用手动的管理内存，但是对 链表 这种数据结构，更加深入的理解，可以帮助大家对引用、指针、甚至计算机系统中和内存管理相关的很多话题，有更加深入的认识。

更深入的理解递归：链表 本来也是有他非常清晰的递归结构的，、由e 3 8 q k于 链表 这种数据结构是 数据结构，我们可以更加 深入理解递归，对于递归这种深入理– Y V x U解是不可获取的。

链表 本身也是c 4 T H . Q x具有功能性：辅助组成其他数据结构(hashMap 、N \ & s l栈和队列)

三、什么是链表

链表 是一种数据结构，在内存中通过 节点记录内存地址 而相互链接形成一条链的储存方式。相比数组而言，链表在内存中不需要连续的区域，只需要每一个节点都能够 记录下一个节点 的 内存地址 ，通过 引用 进行查找，这样的特点也就造就了 链表 增删操作时间消耗很小，而查找遍历时间消耗很大的特点。

我们日常在 Java 中使用的 LinkedList 即为 双向链表。而在链表是由其基本组成单元节点 (Node) 来实现的% ) N C ^ M u & 1。我们在日常中见到的链表大部分都是 单链表和双链表

单元节点 (Node)：

classNode{
Ee;
Nodenext;
}

e 就是@ | f链表元素

next 指的是当前节点的下一个节点

对于 链表 来说它就像我们的火车一样，每一个节点其实就是一节车厢，我们在车厢中存储真正X t – L O J ( 8 h的数据，而车厢和车厢之间还要进行连接，让我们数据是整合在一起@ 5 ;的，用户可以方便的在所有的数据上进行查询或其他操作，那么 数据和数据连接 就是由这个 next 来完成的

当然 链表 不能无穷无尽，如果一个节点的 n; l G E # 8 , {ext 是 Null 了，就说明这个节点是最后一个O F u ~ = $ h节点了，这就是 链表

如下图所示(单链表)：

链表的优点：真正的B & p = t s P s动态，不需要处理固定容量的问题链表的缺点：丧失了随机访问的C – f能力

在数组中：每一个索引，直接从数组中拿出索引V h S W , s ]对应的元素，这是因为从底层机制上，数组A V 2 R T U X n i所开辟的空间，在内存里是连续分布的，所以我们可以直接可以去找这个数组的偏移，直接计算出这个数据所存储的内存地址，可以直接使用。

链W \ l 1 v N W表：而链0 \ 2 o 8 ? Z (表是靠 Next 一层一层连接的，需要借助这个 Next 一点一点的去找我们需要取出来的元素。

四、创建我们自己c ! ( N L n 4的p m f ; h \ `链表

4.1 链表基本结构

/**
*底t Q ? p 6层链表的内部F k Z = m * V ;类
*@param<E>
*/
publicclassLinkedList<E>{

//设计私有的内部类，对于用户来说不需要知道链表6 [ C 6底层实现，
//不需要知道node这个节点，对用户屏蔽编码实现的底层实现
privateclassNode{
publicEe;
publicNodenext;//public可以在LinkedList随意操作

publiQ , % U 7 ! h w OcNode(Ee,Nodenext){
this.e=e| a E ( b k ] y;
this.next=next;
}

publicNode(Ee){
this(e,^ Y 6 ) d L Jnull);
}

publicNode(){
this(null,null);
}

@Overridh r 6 o r 3 O 0 He
publicStringtoString(){
returne.toString();
}
}
}

内部类NodeY r q ,：设计私有的内部类，对于用户来说不需要知道链表底层实现，不需要知道node这个节点，对用户屏蔽编码实现的底层实现e：元素next：指向Node的一个引用

4.2 添加元素

之前我们讲的是如何在数组中添加元素，我们在数组尾添加元素是非常方便的，因为对于数组来说是顺序排放的，有意思的是对于链表来说，恰恰相反，在链表头添加4 [ u 2 , ? + h D元素是非常方便的，其实这样非常好理解，对于数组来说我们有 size 这个变量，它直接指向了数组中最后一个元素下一个位置，也就是下一个待添加元素的位置，所以直接添加就非常容易，因为有 size 这个变量，在跟踪数组的尾巴，而对于链表来说我们设立了链表的一个头 head ，而没有变量来跟踪链表的尾巴,所以我们在链表头添加元素是非常方便的，最关键的就是 node.next = head 和 head = node，如下图所示：

4.2.1 链表头添加元素

代码实现：

//在链表头中添加元素e
publicvoidaddFirst` N | J ( \ s(Ee){
//方式一
//Nodenode=newNode(e);
//node.next=head;
//head=node;
//方式二
head=newNode(e,head);
size++;
}

4.2.2 链表中间% l v { z E 5添加元素

我们需要在索引为2的地方添加元素 666，我们只需要找到 元素666要 插入x G 0之W @ a @ ( N前的节点(1) ，我们管它叫 prev，然后把 之前节点D ` S 0的(^ s G 01) next 指向 666，然后在将 666的这个 节点指O K 7 / P P ; I向之前节点(1Q F i 4 r *) 的 之8 x ! 6 &后的节点(2) ，就完成了整个插入了，其中关键代码就是 node.next=prev.next和prev.next=node;，其中关键：我们要找到Q 2 9 P添加节点的前一个节点 。

代码实现：

//在链表的index(0-based)$ b P ; b ; z o t位置添加新的元素e
publicvoidadd(intindex,Ev ` U Je){
if(index<0||index>size)
thrownewIllegalArgumentException("Addfailed.Illegalindex.");

if(index==0)
addFirst(e);
else{
Nodeprev=head;
for(inti=0;i<index-1;i++){//将prev放入下一个节点，直到移动到index-1
prev=prev.next;

//方* ; w H | J B式一
//Nodenode=newNode(e);
//node.next=prev.next;
//prev.next=node;

//方式二
prb { p E = 4 $ C nev.next=newNode(e,prev.next);
size++;
}
}
}

//在链表末尾添加新的元素e
publicvoidaddLast(Ee){
add(size,e);
}

4.2.3 添加操作时间复杂度

4.3 为链表设计虚拟头结点

上面我们介绍了7 ! 6 M链表的添加操作，那么我们在添加的时候遇到了一个问题，就是在链表任意一Y k + ) H f n g 6个地方的时候，添加一个元素，在链表头添加一个元素，和在链表其他地方添加元素，逻辑上会有差别，为什么在链表头添加元素会比较特殊呢，因为j I k U我们在链表添加元素的过程，要找到待添加的 之前$ i .的一个节点，但是由于对于链表头没有之前的一个节点，不过我们可以自己创建一个头结点，这个头节点就是 虚拟头结点，这个节点对于用户G m p \来说是不存在， 用户也不会感知到这个节点的存在，我们y f Q D s u ~是屏蔽了这个节点的存在，如下图所示：

代码实现：

privateNoded# 7 j ; S m l xummyHead;
intsize;

publicLinket 3 &dList(){
dummyP 4 4 l / : B 1 AHead=newNode(nR c ) K cull,null);x z 6 Q
size=0;
}


//获取链表中的元素个数
publicintgetSize(){
reo ! 7 Y P ^ d 8turnsize;
}

//返回链表是否为空
publicbog c d f EoleanisEmpt\ C N p x Ty(){
returnsize==0;
}
//在链表的index(0-based)位置添加新的元素e
publicvoidaddi \ W A X .(intindP c b % ] M . Qex,Ee){

if(index<0||index>size)
thrownewIllegalArgumentException("AddfailedP W K.Illegalinq { l w Idex.");

Nodeprev=dummyHead;
for? G y % ! =(inti=0;i<index;i++)
prev=prev.next;

prev.next=newNode(e,prev.next);
size++;
}S = l I K , # d j

//在链表头中添加元素e
pub@ d P [ c 3 klicvoidaddFirst(Ee){
add(0,e);
}

//在链表末尾添加新T O &的元素e
publicvoidaddLast(Ee){
add(size,e);
}

4.4 链表元素 get、set、是否存在操作

//在链表的index(0-based0 ( - 9 \ g 5 w)位置添加新的元素e
publicEget(i O V J O Iintinde{ I X q Yx){
if(index<0||index>size)
thrownewIllegalArgumentException("Getfailed.Illegalindex.");

Nodecur=dummyHead.next;
for(inti=0;i<index;i++)
cur=cur.next;

returncur.e;
}

//获得链表Z + H 1 y {的第一个元素
publicEgetFirst(){
returnget(0);
}

//获取链表的最后一个元素e , ?
publicEgetLast(){
returnget(size-1);
}

//在链表的index(0-based)位置添加新的元素e
publicvoidsk y { / & B oet(intindex,Ee){
if(index<0||index>size)
thrownewIg q 0 P D Z Z r allegalArgumentException("Setfailed.Illegalindex.");

Nodecur=dummyHead.nex? P A 4 c rt;
for(inti=0;i<index;i++)
cur=cur.next;

cur.e=e;
}

//查找链表中是否有元素d 6 W 6 r Ne
publicboolea\ h U 5 O uncontains(Ee){
Nodecur=D ; w v = 6 !dummyHead.next;
whil1 1 ne(cur!=null){
if(cur.e.equals(e))
returntruO a - | B X *e;
cur=cur.next;
}
returnfalT ` z Tse;
}

4.5.1 修改和查找操作时间复杂度

4.5 删除链表元素

加入我们想要删除索引为 (2) 位置的元素，我们需要找到s ! g G 1 – ? 待删除节点之前的一个位置，也就是(1) ，我们用 prev 表示，找到这个节点之后，那么 (2) 就是我们需要删除的索引了 我们叫 delNode，如下图所示：

代码实现：

//从链表中u v n k o ^ 7删除Index(G * l -0-based)位置的元素，返回删除的元素
publicEremove(intindex){
if(index&i t xlt;0||i, v a ^ ;ndex>size)
thrownewIllegalArgumenm % b [tException("Removefailed.Illegalindex.");

Nodeu O * T W #prev=dummyHead;
for(inti=0;i<index;i++)
prev=prf ] ; R [ev.next;

NoderetNg n + F C Code=prev.next;
prev.next=retNode.next;
retNode.next=null;

size--;

returnrx * m g yetNode.e;

}

//从链表中删除第一个位置的元素
publicEred X n 7 \ 2moveFirst(){
returnremove(0);
}

//从链表中删除最后一个位置的元素
publicEremoveLast(){
returnremove(size-1);
}

4.5.1 删除操作时间复杂度

4.6 完整代码

/**
*底层链表的内部类
*@param<E>
*/
publicclassLink; ` CedList<E>{

privateclassNode{
publicER 9 8 M l / oe;
publicNodenext;//public可以在LinkedList随意操作

publicNode(Ee,Nodenext){
this.e=e;
this.next=next;
}

publicNode(Ee){
thR \ $ ) l C $ ~is(e,null)x u V K };
}

publicNode(){
this(null,null);
}

@Override
publicStrin: c l z ~ j \ / +gtoString(){
returne.toString();
}
}


privateNodedummyHead;
intsize;

publicLinkedList(){
dummyHead=newNode(null,4 . ; = Znull);
size=0;
}


//获取链表中的元素个数
publicintgetS+ ` R Y @ KizJ Y u ] | 9 ie(){
returnsize;
}

//返回链表是否为空
publicbooleanis; @ 9 ~ J ,Empty(){
returnsize==0;
}




//在链表头中添加元素e
publicvoidaddFirst(Ee){
//方式一
//Nodenode=newNode(e);
//node.next=head;
//head=? z d * 7 nnode;
//方式二
add(0,e);
}

//在链[ G _ C #表的indT ; | Pex(0-based)位置添加新的元素e
publicvoidadd(intindex,Ee){

if(index<0||index>size)
throwne1 ] ZwIllegalArgumen~ Y G s x S s 2tException("Addfailed.Illegalindex.");

Nodeprev=dummyHead;
for(inti=0;i&V [ h & 2 { 6 F wlt;index;i++)
pre- # *v=prev.next;

prev.next=newNode(e,prev.next);
size++;
}

//在链表末尾添加新的元素e
publicvoidaddLast(Ee){
add(size,e);
}

//在链表的index(0-2 . Vbased)位置添加新的元素e
publicEget(intindex){
i= 0 1 N a U y ? .f(index<0||index>size)
thrownewIllegalArgumentEm 2 l 5 +xceptio4 x 8 4 * OnJ 8 N S \("Getfailed.Illegalindex\ b \ \ u u.");

Nodecur=dummyHead.next;
for(inti=0;i<index;i++)
cur=cur.nexM s u B c S P @t;

returncur.e;
}

//获得链表的第一个元素
publicEgetFiru 3 _ 6 Xst(){
returnget(0);a S H ? Z ]
}

//获取链表的最后一个元素
publicEgetLast(){
returnget(size-1);
}

//在链表的index(0-based)位置6 4 = )添加新的5 b w : g ` 3 Q [元素e
publicvoidset(intindex,Ee){
if(index<0||index>size)
thrownewIllegalArgumentException("Setfailed.Illegalindex.");

NodecuI 7 $ d 4 j k O Er=dummyHead.next% b F = ? K;
for(inti=0;i<index;i++)
cur=cur.next;

cur.e=e;
}

//查找链表中是否有元素e
publicbooleanQ j n q [ ` ( - Yc7 ~ # F m 5 R !ontains(c A Q f [ , l 9 IEe){
Nodecur=dummyHead.next;
while(cur!=null){
if(cur.e.equals(e))
returntrux ~ ) ? w _ } Ve;
cur=cur.next;
}
returnfalse;
}


//从链表中删除Index(C 8 , P 7 .0-based)位置的元素，返回删除的元素
publicEremove(intindex){
if(index<f q 9;0||index>size)
throB o w = _ 4 rwnewIllegalArgumentException("RemoN ^ Z G Uvefailed.Illegalindex.");

Nod4 h 3eprev=dum{ w N QmyHead;
for(inti=0;i<index;i++)
prev=prev.next;

NoderetNode=prev.nextN | , y \ f;
p\ m Q o 3 [ Hrev.next=retNode.next;
retNode.next=null;

size--;

returnretNode.e;

}

//从链表中删除第一个位置的W \ R c M元素
publicEremoveFirst(){
returnremove(0);
}

//从链表中删除最后一个位置的元素\ k M K } M J e o
publicEremoveLast()Q o f Z .{
returnremr ] t # I c @ aove(size-1);
}

@Override
publicStringtoString(){

StringBuilderres=newStringBuilder();
for(j t fNodecur=dummyHead.next;cur!=null;cur=cur.next)
res.append(cur+"->");

res.append("Null");
returnres.toString();
}

}p P m =

4.2.7 结果测试：

publicstaticvoidmain& 6 # `(String[]args){
LinkedList<Integer>linkedList=, ] /newL@ c o y ~ HinkedList<>();
//添加元素0-4
for(inti=0;i<5;i++){
linkedList.addFirst(i);
System.out.println(linkedList);
}

//添加第二个b } t N t . /元素添加666
linkF * C , + k ; medList.add(2,666);
System.out.println(linkedL5 n -ist);

//删除第二个元素666
linkedList.remove(2);
System.out.println(linkedList);

//删除第一个元素
linkedList.removeN 7 B ] \First();
System.out.println(linkedList);

/y $ 2 6/删除最后一个元素
linkedList.removeM n Q 5 a u 5 g #La9 Z vst();
System.out.println(linkedList);
}

打印结果：

0->Null
1->0-&g= o i r T i / ,t;Null
2->1-^ B @ ] & V O I E>0->Null
3->2->1->0->Null
4->3->2-&gC A [ | *t;1-/ X + e>0->Null
4->3->666->2->1->0->Null
4->3->2->1->0->Null
3->2->1->0->Null
3->2->1->Null

四、链表时间复杂度分析

对于增u { P s I d q Z加和删除来说，如果是对链表头进行操作，那么就是 O(1) 级别的复杂度，对于查询来说，也是一样

五、链表s m W 8应用

5.1 使用栈实现链表

5.1.1 接口类E Z x：

/**
*@program:Data-Structures
*@ClassNameStack
*@desw j r = t 2cription:
*@author:lyy
*@create:201I } J / h C i +9-11-2021:51
*@Version1.0
**/
publicin8 # = ) qterfaceStack<E>{

intgetSize();
booleanisEmpty();
voidpush(Ee);
Epop();
Epeek();

}

5.1.2 实现类：

importcom.lyy.d^ D $ W { W h V {atasty.Mystack.Stack;

//链表栈实现
publicclassLinkedListStack<E>implementsStack<E>{

privateLinkedList1<E>list;

publicLinkedListSta` A / ) V } X 6ck(){
list=newLinkedList1<>();
}


@Override
publicintgetSize(){
returnlist.getSize();
}

@Override
publiJ N ] M E : e H {cbooleanisEmpty(){
returnlist.isEmpty();
}

@Override
publicvoidpusj Y Z q ! 1h(Ee){
list.addFirst(e, e v S % l I S a);
}

@Override
publicEpop(){
returnlist$ 2 n.rj r ` \ u 5 3 E qemoveFirst();
}

@Override
puS t 0 L & eblicEpeek(){
returnlist.getFirstk [ % X C();
}

@Override
publicStringtoString(){

StringBuildev $ y J 0rres=newStringBuilder();
res.append("Stack：top");
res.append(list);
returnres.e t d z m a qtoString();
}


}

5.1.3 运行结果：

public% c o # a U Tstat% I W X t \ G [ Hicvoidmain(Strie ~ E } l 7 :ng[]args){
LinkedListStack<: R ( q W L c 5;Integer>stack=newL$ X ] ^inkeV h z E ? GdListSta4 j \ _ Gck<>();
for(inti=0;i<5;i++){
stack.push(i);
System.out.println(stackA 5 `);
}
stE | | ? ; Oack.pop()C # 9 S;
System.out.println(stack);


}

5.1.O I k 84 结果打印：V a h O b \ H

Stack：top0->Null
Stack：top1->0->Null
Stack：top2J U U p Z 7 g : e->1->0->Null
Stack：top3->2->1->0->Null
Sx A 0tack：top4->3->2->1->0->Null
Stack：top3->2->1->0->Null

5.2 使用链表实现队列

5.2.1 接口类

/**
*@program:Data-Structures
*@ClassNameQueue
*@description:
*@author:lyy
*@create:2019-11-2121:54
*@Version1.0
**/
publicinterfaceQueue<E>{

intgetSize();
booleanisEm ~ 4 8 Q . z gmpty();
voidenqueue(Ee);
Edequeue();
EgetFrontd k t $();


}

5.m , z a2.2 实现类

publicclassLinkedListQueue&l1 C [ J { c h kt;E>implementsQueue<E>{

//设计私有的内部类，对于用户来说不需要知B S K d \ [ s :道链表底层实现，
//不需要知道node这个节p e 0点，对用户屏蔽编码实现的底层实] * z t ( ]现
privateclassNode{
publicEe;
publicNodenext;//public可以在LinkedList随意操作

publicNode(EeI ( v,Nodenext){
this.e=e;
this.next=next;
}

publicNode(Ee){
this(e,null);
}

publicNode(){
this(nuP r Q f d O B 7ll,null);
}

@O7 ? X A q ( yverride
publicStringtoString(){
ret{ m GuY 9 N c Q Qrne.toString();
}
}

privateNodehead,tail;
privateintsize;

publicLinkedListQueue(){
head=null;
tail=null;
size=0;
}


@% # x @ E A IOverride
publicintgetSize(){
returnsize;
}

@Override
publi- j ScbooleanisEmpty(){
returnsize==0;
}

@Override
publicvoidenqueue(Ee){
if(tai4 L [ R - rl==null){
tail=newNode(e);
head=tail;F R e W o w -
}else{
tail.next=newNode(e);
tail=tail.next;
}
size++;
}

@Override
publicEdequeue(){
if(isEmpty())
thrownewIllegalArgumentException("Cannotdequeuefromanemptyqueue.");

NoderetNode=head;
head=head.next;
retNode.next=null;
if(head==null)
tail=null;

size--;

returnretNode.e;
}

@Override
publicEgetFront(){
if(isEmpty())
thrownewIllegalArgumentExH S k % Uception("queu~ 8 U } ; x {eisempty.");

returnhead.e;
}

@Overridez X ~ \ O q [ N
publicStringtoString(){
StringB? ? { ~ $uilderres=newStrinq { s k 1gBuilder();
res.append("Queue：front");

N} a & 0 q W k r aodecur=head;
while(cur!=null){
res.append(cur+"->");
cur=cur.next;
}
res.append("Nulltail");
returnres.toString();
}
}

5.2.2 测试类

publicstaticvoidmain(String[]args){
Li{ d $nkedListQueue<Integer>queue=newLinkedListQueue<>();
for(inti=0;i<10;i++){
queu` ? 0 Qe.enqueue(i);
Sq v k E 9 . 7 o #ystem.out.println(queue);

if(i%3==2){
queue.dequeue();
System.out.println(queue);
}
}
}

打印结果：

Queue| ^ ~ m . ) 2 =：fro3 g j $ , O %nti D L a ? ( [ ?0->Nulltail
Queue：front0->1->Nulltail
Queue：front0->1->2->Nulltail
Queue：front1->2->3 C | 3 LNulltail
Queue：front1->8 m ] F * \ +;2->3->Nulltail
Queue^ T : A ` H X：front1->2->3->4->Nulltail
Queue：front1->2->3->4->5->, [ U;Nulltail
Queue：front2->z # 5 #3->4->5F V _ ^ m D->Nulltail
Queue：fru % vont2->3-&g@ = \ c *t;4->5->6->Nulltail
Queue：front2->3->4->5->6->7->Nulltail
Queue：front2->3->4->5->6->7->8->Nulltai7 [ ) D ^ M 0l
Queue：front3->4->5->6->7->8->? ` E K ENulltail
Qz ( | xueue：front3->4->5->6->7->8->9->Nulltail

六、更多链表结构

6.1 双链表4 , / 6

代码：

classNode{
Ee;
Nodenext,prev;
}

6.1 循环列表

代码：

classNode{
Ee;
Nodenext,prev;
}

在jav@ { L w : K La中，LinkedList 底层使( x 5 + C I h用的就是 循环链表，也就是循环双向链表，到这里我0 n Y x 7 _ O 2 @们链表就讲解完成了。

2512141116@qq.com

链接