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

链表是我们数据结构学习的一个重点,也有可能是一个难点,为什么链表这么重要呢?因为他是最简单的也是 真正

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

一、前言

在前面两章我们讲解了动态数组、栈和队列的讲解,这些底层都是依托静态数组,靠 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):

  1. classNode{
  2. Ee;
  3. Nodenext;
  4. }

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 4p m f ; h \ `链表

4.1 链表基本结构

  1. /**
  2. *底t Q ? p 6层链表的内部F k Z = m * V ;
  3. *@param<E>
  4. */
  5. publicclassLinkedList<E>{
  6. //设计私有的内部类,对于用户来说不需要知道链表6 [ C 6底层实现,
  7. //不需要知道node这个节点,对用户屏蔽编码实现的底层实现
  8. privateclassNode{
  9. publicEe;
  10. publicNodenext;//public可以在LinkedList随意操作
  11. publiQ , % U 7 ! h w OcNode(Ee,Nodenext){
  12. this.e=e| a E ( b k ] y;
  13. this.next=next;
  14. }
  15. publicNode(Ee){
  16. this(e,^ Y 6 ) d L Jnull);
  17. }
  18. publicNode(){
  19. this(null,null);
  20. }
  21. @Overridh r 6 o r 3 O 0 He
  22. publicStringtoString(){
  23. returne.toString();
  24. }
  25. }
  26. }

内部类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 链表头添加元素

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

代码实现:

  1. //在链表头中添加元素e
  2. publicvoidaddFirst` N | J ( \ s(Ee){
  3. //方式一
  4. //Nodenode=newNode(e);
  5. //node.next=head;
  6. //head=node;
  7. //方式二
  8. head=newNode(e,head);
  9. size++;
  10. }

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

我们需要在索引为2的地方添加元素 666,我们只需要找到 元素666要 插入x G 0W @ 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添加节点的前一个节点 。

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

代码实现:

  1. //在链表的index(0-based)$ b P ; b ; z o t位置添加新的元素e
  2. publicvoidadd(intindex,Ev ` U Je){
  3. if(index<0||index>size)
  4. thrownewIllegalArgumentException("Addfailed.Illegalindex.");
  5. if(index==0)
  6. addFirst(e);
  7. else{
  8. Nodeprev=head;
  9. for(inti=0;i<index-1;i++){//将prev放入下一个节点,直到移动到index-1
  10. prev=prev.next;
  11. //方* ; w H | J B式一
  12. //Nodenode=newNode(e);
  13. //node.next=prev.next;
  14. //prev.next=node;
  15. //方式二
  16. prb { p E = 4 $ C nev.next=newNode(e,prev.next);
  17. size++;
  18. }
  19. }
  20. }
  21. //在链表末尾添加新的元素e
  22. publicvoidaddLast(Ee){
  23. add(size,e);
  24. }

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 ~是屏蔽了这个节点的存在,如下图所示:

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

代码实现:

  1. privateNoded# 7 j ; S m l xummyHead;
  2. intsize;
  3. publicLinket 3 &dList(){
  4. dummyP 4 4 l / : B 1 AHead=newNode(nR c ) K cull,null);x z 6 Q
  5. size=0;
  6. }
  7. //获取链表中的元素个数
  8. publicintgetSize(){
  9. reo ! 7 Y P ^ d 8turnsize;
  10. }
  11. //返回链表是否为空
  12. publicbog c d f EoleanisEmpt\ C N p x Ty(){
  13. returnsize==0;
  14. }
  15. //在链表的index(0-based)位置添加新的元素e
  16. publicvoidaddi \ W A X .(intindP c b % ] M . Qex,Ee){
  17. if(index<0||index>size)
  18. thrownewIllegalArgumentException("AddfailedP W K.Illegalinq { l w Idex.");
  19. Nodeprev=dummyHead;
  20. for? G y % ! =(inti=0;i<index;i++)
  21. prev=prev.next;
  22. prev.next=newNode(e,prev.next);
  23. size++;
  24. }S = l I K , # d j
  25. //在链表头中添加元素e
  26. pub@ d P [ c 3 klicvoidaddFirst(Ee){
  27. add(0,e);
  28. }
  29. //在链表末尾添加新T O &的元素e
  30. publicvoidaddLast(Ee){
  31. add(size,e);
  32. }

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

  1. //在链表的index(0-based0 ( - 9 \ g 5 w)位置添加新的元素e
  2. publicEget(i O V J O Iintinde{ I X q Yx){
  3. if(index<0||index>size)
  4. thrownewIllegalArgumentException("Getfailed.Illegalindex.");
  5. Nodecur=dummyHead.next;
  6. for(inti=0;i<index;i++)
  7. cur=cur.next;
  8. returncur.e;
  9. }
  10. //获得链表Z + H 1 y {的第一个元素
  11. publicEgetFirst(){
  12. returnget(0);
  13. }
  14. //获取链表的最后一个元素e , ?
  15. publicEgetLast(){
  16. returnget(size-1);
  17. }
  18. //在链表的index(0-based)位置添加新的元素e
  19. publicvoidsk y { / & B oet(intindex,Ee){
  20. if(index<0||index>size)
  21. thrownewIg q 0 P D Z Z r allegalArgumentException("Setfailed.Illegalindex.");
  22. Nodecur=dummyHead.nex? P A 4 c rt;
  23. for(inti=0;i<index;i++)
  24. cur=cur.next;
  25. cur.e=e;
  26. }
  27. //查找链表中是否有元素d 6 W 6 r Ne
  28. publicboolea\ h U 5 O uncontains(Ee){
  29. Nodecur=D ; w v = 6 !dummyHead.next;
  30. whil1 1 ne(cur!=null){
  31. if(cur.e.equals(e))
  32. returntruO a - | B X *e;
  33. cur=cur.next;
  34. }
  35. returnfalT ` z Tse;
  36. }

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

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

4.5 删除链表元素

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

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

代码实现:

  1. //从链表中u v n k o ^ 7删除Index(G * l -0-based)位置的元素,返回删除的元素
  2. publicEremove(intindex){
  3. if(index&i t xlt;0||i, v a ^ ;ndex>size)
  4. thrownewIllegalArgumenm % b [tException("Removefailed.Illegalindex.");
  5. Nodeu O * T W #prev=dummyHead;
  6. for(inti=0;i<index;i++)
  7. prev=prf ] ; R [ev.next;
  8. NoderetNg n + F C Code=prev.next;
  9. prev.next=retNode.next;
  10. retNode.next=null;
  11. size--;
  12. returnrx * m g yetNode.e;
  13. }
  14. //从链表中删除第一个位置的元素
  15. publicEred X n 7 \ 2moveFirst(){
  16. returnremove(0);
  17. }
  18. //从链表中删除最后一个位置的元素
  19. publicEremoveLast(){
  20. returnremove(size-1);
  21. }

4.5.1 删除操作时间复杂度

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

4.6 完整代码

  1. /**
  2. *底层链表的内部类
  3. *@param<E>
  4. */
  5. publicclassLink; ` CedList<E>{
  6. privateclassNode{
  7. publicER 9 8 M l / oe;
  8. publicNodenext;//public可以在LinkedList随意操作
  9. publicNode(Ee,Nodenext){
  10. this.e=e;
  11. this.next=next;
  12. }
  13. publicNode(Ee){
  14. thR \ $ ) l C $ ~is(e,null)x u V K };
  15. }
  16. publicNode(){
  17. this(null,null);
  18. }
  19. @Override
  20. publicStrin: c l z ~ j \ / +gtoString(){
  21. returne.toString();
  22. }
  23. }
  24. privateNodedummyHead;
  25. intsize;
  26. publicLinkedList(){
  27. dummyHead=newNode(null,4 . ; = Znull);
  28. size=0;
  29. }
  30. //获取链表中的元素个数
  31. publicintgetS+ ` R Y @ KizJ Y u ] | 9 ie(){
  32. returnsize;
  33. }
  34. //返回链表是否为空
  35. publicbooleanis; @ 9 ~ J ,Empty(){
  36. returnsize==0;
  37. }
  38. //在链表头中添加元素e
  39. publicvoidaddFirst(Ee){
  40. //方式一
  41. //Nodenode=newNode(e);
  42. //node.next=head;
  43. //head=? z d * 7 nnode;
  44. //方式二
  45. add(0,e);
  46. }
  47. //在链[ G _ C #表的indT ; | Pex(0-based)位置添加新的元素e
  48. publicvoidadd(intindex,Ee){
  49. if(index<0||index>size)
  50. throwne1 ] ZwIllegalArgumen~ Y G s x S s 2tException("Addfailed.Illegalindex.");
  51. Nodeprev=dummyHead;
  52. for(inti=0;i&V [ h & 2 { 6 F wlt;index;i++)
  53. pre- # *v=prev.next;
  54. prev.next=newNode(e,prev.next);
  55. size++;
  56. }
  57. //在链表末尾添加新的元素e
  58. publicvoidaddLast(Ee){
  59. add(size,e);
  60. }
  61. //在链表的index(0-2 . Vbased)位置添加新的元素e
  62. publicEget(intindex){
  63. i= 0 1 N a U y ? .f(index<0||index>size)
  64. thrownewIllegalArgumentEm 2 l 5 +xceptio4 x 8 4 * OnJ 8 N S \("Getfailed.Illegalindex\ b \ \ u u.");
  65. Nodecur=dummyHead.next;
  66. for(inti=0;i<index;i++)
  67. cur=cur.nexM s u B c S P @t;
  68. returncur.e;
  69. }
  70. //获得链表的第一个元素
  71. publicEgetFiru 3 _ 6 Xst(){
  72. returnget(0);a S H ? Z ]
  73. }
  74. //获取链表的最后一个元素
  75. publicEgetLast(){
  76. returnget(size-1);
  77. }
  78. //在链表的index(0-based)位置6 4 = )添加新的5 b w : g ` 3 Q [元素e
  79. publicvoidset(intindex,Ee){
  80. if(index<0||index>size)
  81. thrownewIllegalArgumentException("Setfailed.Illegalindex.");
  82. NodecuI 7 $ d 4 j k O Er=dummyHead.next% b F = ? K;
  83. for(inti=0;i<index;i++)
  84. cur=cur.next;
  85. cur.e=e;
  86. }
  87. //查找链表中是否有元素e
  88. publicbooleanQ j n q [ ` ( - Yc7 ~ # F m 5 R !ontains(c A Q f [ , l 9 IEe){
  89. Nodecur=dummyHead.next;
  90. while(cur!=null){
  91. if(cur.e.equals(e))
  92. returntrux ~ ) ? w _ } Ve;
  93. cur=cur.next;
  94. }
  95. returnfalse;
  96. }
  97. //从链表中删除Index(C 8 , P 7 .0-based)位置的元素,返回删除的元素
  98. publicEremove(intindex){
  99. if(index<f q 9;0||index>size)
  100. throB o w = _ 4 rwnewIllegalArgumentException("RemoN ^ Z G Uvefailed.Illegalindex.");
  101. Nod4 h 3eprev=dum{ w N QmyHead;
  102. for(inti=0;i<index;i++)
  103. prev=prev.next;
  104. NoderetNode=prev.nextN | , y \ f;
  105. p\ m Q o 3 [ Hrev.next=retNode.next;
  106. retNode.next=null;
  107. size--;
  108. returnretNode.e;
  109. }
  110. //从链表中删除第一个位置的W \ R c M元素
  111. publicEremoveFirst(){
  112. returnremove(0);
  113. }
  114. //从链表中删除最后一个位置的元素\ k M K } M J e o
  115. publicEremoveLast()Q o f Z .{
  116. returnremr ] t # I c @ aove(size-1);
  117. }
  118. @Override
  119. publicStringtoString(){
  120. StringBuilderres=newStringBuilder();
  121. for(j t fNodecur=dummyHead.next;cur!=null;cur=cur.next)
  122. res.append(cur+"->");
  123. res.append("Null");
  124. returnres.toString();
  125. }
  126. }p P m =

4.2.7 结果测试:

  1. publicstaticvoidmain& 6 # `(String[]args){
  2. LinkedList<Integer>linkedList=, ] /newL@ c o y ~ HinkedList<>();
  3. //添加元素0-4
  4. for(inti=0;i<5;i++){
  5. linkedList.addFirst(i);
  6. System.out.println(linkedList);
  7. }
  8. //添加第二个b } t N t . /元素添加666
  9. linkF * C , + k ; medList.add(2,666);
  10. System.out.println(linkedL5 n -ist);
  11. //删除第二个元素666
  12. linkedList.remove(2);
  13. System.out.println(linkedList);
  14. //删除第一个元素
  15. linkedList.removeN 7 B ] \First();
  16. System.out.println(linkedList);
  17. /y $ 2 6/删除最后一个元素
  18. linkedList.removeM n Q 5 a u 5 g #La9 Z vst();
  19. System.out.println(linkedList);
  20. }

打印结果:

  1. 0->Null
  2. 1->0-&g= o i r T i / ,t;Null
  3. 2->1-^ B @ ] & V O I E>0->Null
  4. 3->2->1->0->Null
  5. 4->3->2-&gC A [ | *t;1-/ X + e>0->Null
  6. 4->3->666->2->1->0->Null
  7. 4->3->2->1->0->Null
  8. 3->2->1->0->Null
  9. 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

  1. /**
  2. *@program:Data-Structures
  3. *@ClassNameStack
  4. *@desw j r = t 2cription:
  5. *@author:lyy
  6. *@create:201I } J / h C i +9-11-2021:51
  7. *@Version1.0
  8. **/
  9. publicin8 # = ) qterfaceStack<E>{
  10. intgetSize();
  11. booleanisEmpty();
  12. voidpush(Ee);
  13. Epop();
  14. Epeek();
  15. }

5.1.2 实现类:

  1. importcom.lyy.d^ D $ W { W h V {atasty.Mystack.Stack;
  2. //链表栈实现
  3. publicclassLinkedListStack<E>implementsStack<E>{
  4. privateLinkedList1<E>list;
  5. publicLinkedListSta` A / ) V } X 6ck(){
  6. list=newLinkedList1<>();
  7. }
  8. @Override
  9. publicintgetSize(){
  10. returnlist.getSize();
  11. }
  12. @Override
  13. publiJ N ] M E : e H {cbooleanisEmpty(){
  14. returnlist.isEmpty();
  15. }
  16. @Override
  17. publicvoidpusj Y Z q ! 1h(Ee){
  18. list.addFirst(e, e v S % l I S a);
  19. }
  20. @Override
  21. publicEpop(){
  22. returnlist$ 2 n.rj r ` \ u 5 3 E qemoveFirst();
  23. }
  24. @Override
  25. puS t 0 L & eblicEpeek(){
  26. returnlist.getFirstk [ % X C();
  27. }
  28. @Override
  29. publicStringtoString(){
  30. StringBuildev $ y J 0rres=newStringBuilder();
  31. res.append("Stack:top");
  32. res.append(list);
  33. returnres.e t d z m a qtoString();
  34. }
  35. }

5.1.3 运行结果:

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

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

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

5.2 使用链表实现队列

5.2.1 接口类

  1. /**
  2. *@program:Data-Structures
  3. *@ClassNameQueue
  4. *@description:
  5. *@author:lyy
  6. *@create:2019-11-2121:54
  7. *@Version1.0
  8. **/
  9. publicinterfaceQueue<E>{
  10. intgetSize();
  11. booleanisEm ~ 4 8 Q . z gmpty();
  12. voidenqueue(Ee);
  13. Edequeue();
  14. EgetFrontd k t $();
  15. }

5.m , z a2.2 实现类

  1. publicclassLinkedListQueue&l1 C [ J { c h kt;E>implementsQueue<E>{
  2. //设计私有的内部类,对于用户来说不需要知B S K d \ [ s :道链表底层实现,
  3. //不需要知道node这个节p e 0点,对用户屏蔽编码实现的底层实] * z t ( ]
  4. privateclassNode{
  5. publicEe;
  6. publicNodenext;//public可以在LinkedList随意操作
  7. publicNode(EeI ( v,Nodenext){
  8. this.e=e;
  9. this.next=next;
  10. }
  11. publicNode(Ee){
  12. this(e,null);
  13. }
  14. publicNode(){
  15. this(nuP r Q f d O B 7ll,null);
  16. }
  17. @O7 ? X A q ( yverride
  18. publicStringtoString(){
  19. ret{ m GuY 9 N c Q Qrne.toString();
  20. }
  21. }
  22. privateNodehead,tail;
  23. privateintsize;
  24. publicLinkedListQueue(){
  25. head=null;
  26. tail=null;
  27. size=0;
  28. }
  29. @% # x @ E A IOverride
  30. publicintgetSize(){
  31. returnsize;
  32. }
  33. @Override
  34. publi- j ScbooleanisEmpty(){
  35. returnsize==0;
  36. }
  37. @Override
  38. publicvoidenqueue(Ee){
  39. if(tai4 L [ R - rl==null){
  40. tail=newNode(e);
  41. head=tail;F R e W o w -
  42. }else{
  43. tail.next=newNode(e);
  44. tail=tail.next;
  45. }
  46. size++;
  47. }
  48. @Override
  49. publicEdequeue(){
  50. if(isEmpty())
  51. thrownewIllegalArgumentException("Cannotdequeuefromanemptyqueue.");
  52. NoderetNode=head;
  53. head=head.next;
  54. retNode.next=null;
  55. if(head==null)
  56. tail=null;
  57. size--;
  58. returnretNode.e;
  59. }
  60. @Override
  61. publicEgetFront(){
  62. if(isEmpty())
  63. thrownewIllegalArgumentExH S k % Uception("queu~ 8 U } ; x {eisempty.");
  64. returnhead.e;
  65. }
  66. @Overridez X ~ \ O q [ N
  67. publicStringtoString(){
  68. StringB? ? { ~ $uilderres=newStrinq { s k 1gBuilder();
  69. res.append("Queue:front");
  70. N} a & 0 q W k r aodecur=head;
  71. while(cur!=null){
  72. res.append(cur+"->");
  73. cur=cur.next;
  74. }
  75. res.append("Nulltail");
  76. returnres.toString();
  77. }
  78. }

5.2.2 测试类

  1. publicstaticvoidmain(String[]args){
  2. Li{ d $nkedListQueue<Integer>queue=newLinkedListQueue<>();
  3. for(inti=0;i<10;i++){
  4. queu` ? 0 Qe.enqueue(i);
  5. Sq v k E 9 . 7 o #ystem.out.println(queue);
  6. if(i%3==2){
  7. queue.dequeue();
  8. System.out.println(queue);
  9. }
  10. }
  11. }

打印结果:

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

六、更多链表结构

6.1 双链表4 , / 6

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

代码:

  1. classNode{
  2. Ee;
  3. Nodenext,prev;
  4. }

6.1 循环列表

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

代码:

  1. classNode{
  2. Ee;
  3. Nodenext,prev;
  4. }

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

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

上一篇 2021年5月15日 下午10:51
下一篇 2021年5月15日 下午10:51