点击收藏
00 月 00 00:00:00 周几
JSON在线格式化校验工具 - www.qjson.cn

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

前端 2023-07-05 17:29:38
60阅读

一、序言

在前面两章大家解读了动态数组、栈和队列的解读，这种最底层全是借助静态数据二维数组，靠 resize处理固定不动容积难题的，以前尽管客户见到的是动态数组，可是仍然应用的是静态数据二维数组，他是借助 resize 这一方式 处理 固定不动容积难题 ，可是大家今日要解读的 链表 不一样，链表是大家算法设计学习培训的一个关键，也是有可能是一个难题，为何链表那么关键呢?由于他是非常简单的也是 真真正正的动态性算法设计。

二、为何链表很重要

  • 链表是一个真真正正的动态性算法设计
  • 非常简单的动态性算法设计
  • 更深层次的了解引入(或是表针)
  • 更深层次的了解递归算法
  • 輔助构成别的算法设计

更深层次的了解引入(或是表针)：和运行内存有关，尽管在 java 中大伙儿无需手动式的管理方法运行内存，可是对 链表 这类算法设计，更为深层次的了解，能够 协助大伙儿对引入、表针、乃至计算机软件中合代码优化有关的许多 话题讨论，有更为深层次的了解。

更深层次的了解递归算法：链表 原本也是有他十分清楚的递归结构的，、因为 链表 这类算法设计是 算法设计，我们可以更为 深层次了解递归算法，针对递归算法这类深层次理解是不能获得的。

链表 自身也是具备多功能性：輔助构成别的算法设计(hashMap 、栈和队列)

三、什么叫链表

链表 是一种算法设计，在运行内存中根据 连接点纪录内存地址 而互相连接产生一条链的存储方法。对比二维数组来讲，链表在运行内存中不用持续的地区，只必须每一个连接点都可以 纪录下一个连接点 的 内存地址 ，根据 引入 开展搜索，那样的特性也就铸就了 链表 删改实际操作時间耗费不大，而搜索解析xml時间耗费非常大的特性。

大家日经常在 Java 中应用的 LinkedList 即是 双向链表。而在链表是由其基本上构成模块连接点 (Node) 来完成的。我们在日常中看到的链表绝大多数全是 单链表和双链表

模块连接点 (Node)：

 
    
  
  1. class Node{ 
    2. 
  
  2.   E e; 
    3. 
  
  3.   Node next; 
    4. 
  
  4. } 
    5.

e 便是链表原素

next 指的是当今连接点的下一个连接点

针对 链表 而言它如同大家的列车一样，每一个连接点实际上便是一火车车厢，我们在车箱中储存真真正正的数据信息，而车箱和车箱中间也要开展联接，使我们数据信息是融合在一起的，客户能够 便捷的在全部的数据信息上开展查看或别的实际操作，那麼 数据信息和数据信息联接 便是由这一 next 来进行的

自然 链表 不可以数不胜数，假如一个连接点的 next 是 Null 了，就表明这一连接点是最后一个连接点了，这就是 链表

如下图所显示(单链表)：

链表的优势：真真正正的动态性，不用解决固定不动容积的难题链表的缺陷：缺失了任意浏览的工作能力

在二维数组中：每一个数据库索引，立即从二维数组中取出数据库索引相匹配的原素，这是由于从最底层体制上，二维数组所开拓的室内空间，在运行内存里是持续遍布的，因此 我们可以立即能够 去找这一二维数组的偏位，立即测算出这一数据信息所储存的内存地址，能够 立即应用。

链表：而链表是靠 Next 一层一层联接的，必须依靠这一 Next 一点一点的去找大家必须取下来的原素。

四、建立我们自己的链表

4.1 链表基本上构造

 
    
  
  1. /** 
    2. 
  
  2.  * 最底层链表的内部类 
    3. 
  
  3.  * @param <E> 
    4. 
  
  4.  */ 
    5. 
  
  5. public class LinkedList<E> { 
    6. 
  
  6.  
    7. 
  
  7.     //设计方案独享的内部类，针对客户而言不用了解链表最底层完成， 
    8. 
  
  8.     // 不用了解node这一连接点，对客户屏蔽掉编号完成的最底层完成 
    9. 
  
  9.     private class Node{ 
    10. 
  
  10.         public E e; 
    11. 
  
  11.         public Node next;//public 能够 在LinkedList随便实际操作 
    12. 
  
  12.  
    13. 
  
  13.         public Node(E e,Node next){ 
    14. 
  
  14.             this.e = e; 
    15. 
  
  15.             this.next = next; 
    16. 
  
  16.         } 
    17. 
  
  17.  
    18. 
  
  18.         public Node(E e){ 
    19. 
  
  19.             this(e,null); 
    20. 
  
  20.         } 
    21. 
  
  21.  
    22. 
  
  22.         public Node(){ 
    23. 
  
  23.             this(null,null); 
    24. 
  
  24.         } 
    25. 
  
  25.  
    26. 
  
  26.         @Override 
    27. 
  
  27.         public String toString() { 
    28. 
  
  28.             return e.toString(); 
    29. 
  
  29.         } 
    30. 
  
  30.     } 
    31. 
  
  31. } 
    32.

内部类Node：设计方案独享的内部类，针对客户而言不用了解链表最底层完成，不用了解node这一连接点，对客户屏蔽掉编号完成的最底层完成e：原素next：偏向Node的一个引入

4.2 加上原素

以前大家讲的是怎样在二维数组中加上原素，我们在二维数组尾加上原素是十分便捷的，由于针对二维数组而言是次序排出的，有趣的是针对链表而言，正好相反，在链表头加上原素是十分便捷的，实际上那样很好了解，针对二维数组而言大家有 size 这一自变量，它立即偏向了二维数组中最后一个原素下一个部位，也就是下一个待加上原素的部位，因此 立即加上就很容易，由于有 size 这一自变量，在追踪二维数组的小尾巴，而针对链表而言大家开设了链表的一个头 head ，而沒有自变量来追踪链表的小尾巴,因此 我们在链表头加上原素是十分便捷的，最重要的便是 node.next = head 和 head = node，如下图所显示：

4.2.1 链表头加上原素

编码完成：

 
    
  
  1. //在链表头中加上原素e 
    2. 
  
  2.   public void addFirst(E e){ 
    3. 
  
  3.   //方法一 
    4. 
  
  4.   //        Node node = new Node(e); 
    5. 
  
  5.   //        node.next = head; 
    6. 
  
  6.   //        head = node; 
    7. 
  
  7.   //方法二 
    8. 
  
  8.       head = new Node(e,head); 
    9. 
  
  9.       size   ; 
    10. 
  
  10.   } 
    11.

4.2.2 链表正中间加上原素

大家必须在数据库索引为2的地区加上原素 666，大家只必须寻找 原素666要 插进以前的连接点(1) ，大家管它叫 prev，随后把 以前连接点的(1) next 偏向 666，随后在将 666的这一 连接点偏向以前连接点(1) 的 以后的连接点(2) ，就完成了全部插入了，在其中重要编码便是 node.next=prev.next和prev.next=node;，在其中重要：我们要寻找加上连接点的前一个连接点 。

编码完成：

 
    
  
  1.  //在链表的index(0-based)部位加上新的原素e 
    2. 
  
  2.     public void add(int index,E e){ 
    3. 
  
  3.         if(index < 0 || index > size) 
    4. 
  
  4.             throw new IllegalArgumentException("Add failed. Illegal index."); 
    5. 
  
  5.  
    6. 
  
  6.         if(index == 0) 
    7. 
  
  7.             addFirst(e); 
    8. 
  
  8.         else{ 
    9. 
  
  9.             Node prev = head; 
    10. 
  
  10.             for (int i = 0; i < index - 1; i  ) {//将prev 放进下一个连接点，直至挪动到index - 1 
    11. 
  
  11.                 prev = prev.next; 
    12. 
  
  12.  
    13. 
  
  13.                 //方法一 
    14. 
  
  14. //                Node node = new Node(e); 
    15. 
  
  15. //                node.next = prev.next; 
    16. 
  
  16. //                prev.next = node; 
    17. 
  
  17.  
    18. 
  
  18.                 //方法二 
    19. 
  
  19.                 prev.next = new Node(e,prev.next); 
    20. 
  
  20.                 size  ; 
    21. 
  
  21.             } 
    22. 
  
  22.         } 
    23. 
  
  23.     } 
    24. 
  
  24.  
    25. 
  
  25.  //在链表结尾加上新的原素e 
    26. 
  
  26.     public void addLast(E e){ 
    27. 
  
  27.         add(size,e); 
    28. 
  
  28.     } 
    29.

4.2.3 加上实际操作算法复杂度

4.3 为链表设计方案虚似头节点

上边大家详细介绍了链表的加上实际操作，那麼我们在加上的情况下碰到了一个难题，便是在链表随意一个地区的情况下，加上一个原素，在链表头加上一个原素，与在链表别的地区加上原素，逻辑性上面有区别，为啥链表头加上原素会较为独特呢，由于我们在链表加上原素的全过程，要寻找待加上的 以前的一个连接点，可是因为针对链表头沒有以前的一个连接点，但是我们可以自身建立一个头节点，这一头连接点便是 虚似头节点，这一连接点针对客户而言是不会有， 客户也不会认知到这一连接点的存有，我们都是屏蔽掉这一连接点的存有，如下图所显示：

编码完成：

 
    
  
  1. private Node dummyHead; 
    2. 
  
  2.    int size; 
    3. 
  
  3.  
    4. 
  
  4.    public LinkedList(){ 
    5. 
  
  5.        dummyHead = new Node(null,null); 
    6. 
  
  6.        size = 0; 
    7. 
  
  7.    } 
    8. 
  
  8.  
    9. 
  
  9.  
    10. 
  
  10.    //获得链表中的原素数量 
    11. 
  
  11.    public int getSize(){ 
    12. 
  
  12.        return size; 
    13. 
  
  13.    } 
    14. 
  
  14.  
    15. 
  
  15.    //回到链表是不是为空 
    16. 
  
  16.    public boolean isEmpty(){ 
    17. 
  
  17.        return size == 0; 
    18. 
  
  18.    } 
    19. 
  
  19.    //在链表的index(0-based)部位加上新的原素e 
    20. 
  
  20.    public void add(int index,E e){ 
    21. 
  
  21.  
    22. 
  
  22.        if(index < 0 || index > size) 
    23. 
  
  23.            throw new IllegalArgumentException("Add failed. Illegal index."); 
    24. 
  
  24.  
    25. 
  
  25.        Node prev = dummyHead; 
    26. 
  
  26.        for (int i = 0; i < index; i  ) 
    27. 
  
  27.            prev = prev.next; 
    28. 
  
  28.  
    29. 
  
  29.        prev.next = new Node(e,prev.next); 
    30. 
  
  30.        size   ; 
    31. 
  
  31.    } 
    32. 
  
  32.  
    33. 
  
  33.  //在链表头中加上原素e 
    34. 
  
  34.    public void addFirst(E e){ 
    35. 
  
  35.        add(0,e); 
    36. 
  
  36.    } 
    37. 
  
  37.  
    38. 
  
  38.    //在链表结尾加上新的原素e 
    39. 
  
  39.    public void addLast(E e){ 
    40. 
  
  40.        add(size,e); 
    41. 
  
  41.    } 
    42.

4.4 链表原素 get、set、是不是存有实际操作

 
    
  
  1. //在链表的index(0-based)部位加上新的原素e 
    2. 
  
  2.    public E get(int index){ 
    3. 
  
  3.        if(index < 0 || index > size) 
    4. 
  
  4.            throw new IllegalArgumentException("Get failed. Illegal index."); 
    5. 
  
  5.  
    6. 
  
  6.        Node cur = dummyHead.next; 
    7. 
  
  7.        for (int i = 0; i < index; i  ) 
    8. 
  
  8.            cur = cur.next; 
    9. 
  
  9.  
    10. 
  
  10.        return cur.e; 
    11. 
  
  11.    } 
    12. 
  
  12.  
    13. 
  
  13.    //得到链表的第一个原素 
    14. 
  
  14.    public E getFirst(){ 
    15. 
  
  15.        return get(0); 
    16. 
  
  16.    } 
    17. 
  
  17.  
    18. 
  
  18.    //获得链表的最后一个原素 
    19. 
  
  19.    public E getLast(){ 
    20. 
  
  20.        return get(size - 1); 
    21. 
  
  21.    } 
    22. 
  
  22.  
    23. 
  
  23.    //在链表的index(0-based)部位加上新的原素e 
    24. 
  
  24.    public void set(int index,E e){ 
    25. 
  
  25.        if(index < 0 || index > size) 
    26. 
  
  26.            throw new IllegalArgumentException("Set failed. Illegal index."); 
    27. 
  
  27.  
    28. 
  
  28.        Node cur = dummyHead.next; 
    29. 
  
  29.        for (int i = 0; i < index; i  ) 
    30. 
  
  30.            cur = cur.next; 
    31. 
  
  31.  
    32. 
  
  32.        cur.e = e; 
    33. 
  
  33.    } 
    34. 
  
  34.  
    35. 
  
  35.    //搜索链表中是不是有原素e 
    36. 
  
  36.    public boolean contains(E e){ 
    37. 
  
  37.        Node cur = dummyHead.next; 
    38. 
  
  38.        while (cur != null){ 
    39. 
  
  39.            if(cur.e.equals(e)) 
    40. 
  
  40.                return  true; 
    41. 
  
  41.            cur = cur.next; 
    42. 
  
  42.        } 
    43. 
  
  43.        return false; 
    44. 
  
  44.    } 
    45.

4.5.1 改动和搜索实际操作算法复杂度

4.5 删掉链表原素

加入团队要想删除索引为 (2) 部位的原素，大家必须寻找 待删掉连接点以前的一个部位，也就是(1) ，大家用 prev 表明，寻找这一连接点以后，那麼 (2) 便是大家必须删掉的数据库索引了 大家叫 delNode，如下图所显示：

编码完成：

 
    
  
  1. //从链表中删掉Index(0-based)部位的原素，回到删掉的原素 
    2. 
  
  2.     public E remove(int index){ 
    3. 
  
  3.         if(index < 0 || index > size) 
    4. 
  
  4.             throw new IllegalArgumentException("Remove failed. Illegal index."); 
    5. 
  
  5.  
    6. 
  
  6.         Node prev = dummyHead; 
    7. 
  
  7.         for (int i = 0; i < index; i  ) 
    8. 
  
  8.             prev = prev.next; 
    9. 
  
  9.  
    10. 
  
  10.         Node retNode = prev.next; 
    11. 
  
  11.         prev.next = retNode.next; 
    12. 
  
  12.         retNode.next = null; 
    13. 
  
  13.  
    14. 
  
  14.         size --; 
    15. 
  
  15.  
    16. 
  
  16.         return  retNode.e; 
    17. 
  
  17.  
    18. 
  
  18.     } 
    19. 
  
  19.  
    20. 
  
  20.     //从链表中删掉第一个部位的原素 
    21. 
  
  21.     public E removeFirst(){ 
    22. 
  
  22.         return remove(0); 
    23. 
  
  23.     } 
    24. 
  
  24.  
    25. 
  
  25.     //从链表中删掉最后一个部位的原素 
    26. 
  
  26.     public E removeLast(){ 
    27. 
  
  27.         return remove(size - 1); 
    28. 
  
  28.     } 
    29.

4.5.1 删掉实际操作算法复杂度

4.6 详细编码

 
    
  
  1. /** 
    2. 
  
  2.  * 最底层链表的内部类 
    3. 
  
  3.  * @param <E> 
    4. 
  
  4.  */ 
    5. 
  
  5. public class LinkedList<E> { 
    6. 
  
  6.  
    7. 
  
  7.     private class Node{ 
    8. 
  
  8.         public E e; 
    9. 
  
  9.         public Node next;//public 能够 在LinkedList随便实际操作 
    10. 
  
  10.  
    11. 
  
  11.         public Node(E e,Node next){ 
    12. 
  
  12.             this.e = e; 
    13. 
  
  13.             this.next = next; 
    14. 
  
  14.         } 
    15. 
  
  15.  
    16. 
  
  16.         public Node(E e){ 
    17. 
  
  17.             this(e,null); 
    18. 
  
  18.         } 
    19. 
  
  19.  
    20. 
  
  20.         public Node(){ 
    21. 
  
  21.             this(null,null); 
    22. 
  
  22.         } 
    23. 
  
  23.  
    24. 
  
  24.         @Override 
    25. 
  
  25.         public String toString() { 
    26. 
  
  26.             return e.toString(); 
    27. 
  
  27.         } 
    28. 
  
  28.     } 
    29. 
  
  29.  
    30. 
  
  30.  
    31. 
  
  31.     private Node dummyHead; 
    32. 
  
  32.     int size; 
    33. 
  
  33.  
    34. 
  
  34.     public LinkedList(){ 
    35. 
  
  35.         dummyHead = new Node(null,null); 
    36. 
  
  36.         size = 0; 
    37. 
  
  37.     } 
    38. 
  
  38.  
    39. 
  
  39.  
    40. 
  
  40.     //获得链表中的原素数量 
    41. 
  
  41.     public int getSize(){ 
    42. 
  
  42.         return size; 
    43. 
  
  43.     } 
    44. 
  
  44.  
    45. 
  
  45.     //回到链表是不是为空 
    46. 
  
  46.     public boolean isEmpty(){ 
    47. 
  
  47.         return size == 0; 
    48. 
  
  48.     } 
    49. 
  
  49.  
    50. 
  
  50.  
    51. 
  
  51.  
    52. 
  
  52.  
    53. 
  
  53.     //在链表头中加上原素e 
    54. 
  
  54.     public void addFirst(E e){ 
    55. 
  
  55. //方法一 
    56. 
  
  56. //        Node node = new Node(e); 
    57. 
  
  57. //        node.next = head; 
    58. 
  
  58. //        head = node; 
    59. 
  
  59. //方法二 
    60. 
  
  60.         add(0,e); 
    61. 
  
  61.     } 
    62. 
  
  62.  
    63. 
  
  63.     //在链表的index(0-based)部位加上新的原素e 
    64. 
  
  64.     public void add(int index,E e){ 
    65. 
  
  65.  
    66. 
  
  66.         if(index < 0 || index > size) 
    67. 
  
  67.             throw new IllegalArgumentException("Add failed. Illegal index."); 
    68. 
  
  68.  
    69. 
  
  69.         Node prev = dummyHead; 
    70. 
  
  70.         for (int i = 0; i < index; i  ) 
    71. 
  
  71.             prev = prev.next; 
    72. 
  
  72.  
    73. 
  
  73.         prev.next = new Node(e,prev.next); 
    74. 
  
  74.         size   ; 
    75. 
  
  75.     } 
    76. 
  
  76.  
    77. 
  
  77.     //在链表结尾加上新的原素e 
    78. 
  
  78.     public void addLast(E e){ 
    79. 
  
  79.         add(size,e); 
    80. 
  
  80.     } 
    81. 
  
  81.  
    82. 
  
  82.     //在链表的index(0-based)部位加上新的原素e 
    83. 
  
  83.     public E get(int index){ 
    84. 
  
  84.         if(index < 0 || index > size) 
    85. 
  
  85.             throw new IllegalArgumentException("Get failed. Illegal index."); 
    86. 
  
  86.  
    87. 
  
  87.         Node cur = dummyHead.next; 
    88. 
  
  88.         for (int i = 0; i < index; i  ) 
    89. 
  
  89.             cur = cur.next; 
    90. 
  
  90.  
    91. 
  
  91.         return cur.e; 
    92. 
  
  92.     } 
    93. 
  
  93.  
    94. 
  
  94.     //得到链表的第一个原素 
    95. 
  
  95.     public E getFirst(){ 
    96. 
  
  96.         return get(0); 
    97. 
  
  97.     } 
    98. 
  
  98.  
    99. 
  
  99.     //获得链表的最后一个原素 
    100. 
  
  100.     public E getLast(){ 
    101. 
  
  101.         return get(size - 1); 
    102. 
  
  102.     } 
    103. 
  
  103.  
    104. 
  
  104.     //在链表的index(0-based)部位加上新的原素e 
    105. 
  
  105.     public void set(int index,E e){ 
    106. 
  
  106.         if(index < 0 || index > size) 
    107. 
  
  107.             throw new IllegalArgumentException("Set failed. Illegal index."); 
    108. 
  
  108.  
    109. 
  
  109.         Node cur = dummyHead.next; 
    110. 
  
  110.         for (int i = 0; i < index; i  ) 
    111. 
  
  111.             cur = cur.next; 
    112. 
  
  112.  
    113. 
  
  113.         cur.e = e; 
    114. 
  
  114.     } 
    115. 
  
  115.  
    116. 
  
  116.     //搜索链表中是不是有原素e 
    117. 
  
  117.     public boolean contains(E e){ 
    118. 
  
  118.         Node cur = dummyHead.next; 
    119. 
  
  119.         while (cur != null){ 
    120. 
  
  120.             if(cur.e.equals(e)) 
    121. 
  
  121.                 return  true; 
    122. 
  
  122.             cur = cur.next; 
    123. 
  
  123.         } 
    124. 
  
  124.         return false; 
    125. 
  
  125.     } 
    126. 
  
  126.  
    127. 
  
  127.  
    128. 
  
  128.     //从链表中删掉Index(0-based)部位的原素，回到删掉的原素 
    129. 
  
  129.     public E remove(int index){ 
    130. 
  
  130.         if(index < 0 || index > size) 
    131. 
  
  131.             throw new IllegalArgumentException("Remove failed. Illegal index."); 
    132. 
  
  132.  
    133. 
  
  133.         Node prev = dummyHead; 
    134. 
  
  134.         for (int i = 0; i < index; i  ) 
    135. 
  
  135.             prev = prev.next; 
    136. 
  
  136.  
    137. 
  
  137.         Node retNode = prev.next; 
    138. 
  
  138.         prev.next = retNode.next; 
    139. 
  
  139.         retNode.next = null; 
    140. 
  
  140.  
    141. 
  
  141.         size --; 
    142. 
  
  142.  
    143. 
  
  143.         return  retNode.e; 
    144. 
  
  144.  
    145. 
  
  145.     } 
    146. 
  
  146.  
    147. 
  
  147.     //从链表中删掉第一个部位的原素 
    148. 
  
  148.     public E removeFirst(){ 
    149. 
  
  149.         return remove(0); 
    150. 
  
  150.     } 
    151. 
  
  151.  
    152. 
  
  152.     //从链表中删掉最后一个部位的原素 
    153. 
  
  153.     public E removeLast(){ 
    154. 
  
  154.         return remove(size - 1); 
    155. 
  
  155.     } 
    156. 
  
  156.  
    157. 
  
  157.     @Override 
    158. 
  
  158.     public String toString() { 
    159. 
  
  159.  
    160. 
  
  160.         StringBuilder res = new StringBuilder(); 
    161. 
  
  161.         for (Node cur = dummyHead.next;cur != null; cur= cur.next) 
    162. 
  
  162.             res.append(cur   "->"); 
    163. 
  
  163.  
    164. 
  
  164.         res.append("Null"); 
    165. 
  
  165.         return res.toString(); 
    166. 
  
  166.     } 
    167. 
  
  167.  
    168. 
  
  168. } 
    169.

4.2.7 結果检测：

 
    
  
  1. public static void main(String[] args) { 
    2. 
  
  2.         LinkedList<Integer> linkedList = new LinkedList<>(); 
    3. 
  
  3.         //加上原素 0-4 
    4. 
  
  4.         for (int i = 0; i < 5 ; i  ) { 
    5. 
  
  5.             linkedList.addFirst(i); 
    6. 
  
  6.             System.out.println(linkedList); 
    7. 
  
  7.         } 
    8. 
  
  8.  
    9. 
  
  9.         //加上第二个原素加上 666 
    10. 
  
  10.         linkedList.add(2,666); 
    11. 
  
  11.         System.out.println(linkedList); 
    12. 
  
  12.  
    13. 
  
  13.         //删掉第二个原素 666 
    14. 
  
  14.         linkedList.remove(2); 
    15. 
  
  15.         System.out.println(linkedList); 
    16. 
  
  16.  
    17. 
  
  17.         //删掉第一个原素 
    18. 
  
  18.         linkedList.removeFirst(); 
    19. 
  
  19.         System.out.println(linkedList); 
    20. 
  
  20.  
    21. 
  
  21.         //删掉最后一个原素 
    22. 
  
  22.         linkedList.removeLast(); 
    23. 
  
  23.         System.out.println(linkedList); 
    24. 
  
  24.     } 
    25.

打印出結果：

 
    
  
  1. 0->Null 
    2. 
  
  2. 1->0->Null 
    3. 
  
  3. 2->1->0->Null 
    4. 
  
  4. 3->2->1->0->Null 
    5. 
  
  5. 4->3->2->1->0->Null 
    6. 
  
  6. 4->3->666->2->1->0->Null 
    7. 
  
  7. 4->3->2->1->0->Null 
    8. 
  
  8. 3->2->1->0->Null 
    9. 
  
  9. 3->2->1->Null 
    10.

四、链表算法复杂度剖析

针对提升和删掉而言，如果是对链表头开展实际操作，那麼便是 O(1) 等级的复杂性，针对查看而言，也是一样

五、链表运用

5.1 应用栈完成链表

5.1.1 接口类：

 
    
  
  1. /** 
    2. 
  
  2.  * @program: Data-Structures 
    3. 
  
  3.  * @ClassName Stack 
    4. 
  
  4.  * @description: 
    5. 
  
  5.  * @author: lyy 
    6. 
  
  6.  * @create: 2019-11-20 21:51 
    7. 
  
  7.  * @Version 1.0 
    8. 
  
  8.  **/ 
    9. 
  
  9. public interface Stack<E> { 
    10. 
  
  10.  
    11. 
  
  11.     int getSize(); 
    12. 
  
  12.     boolean isEmpty(); 
    13. 
  
  13.     void push(E e); 
    14. 
  
  14.     E pop(); 
    15. 
  
  15.     E peek(); 
    16. 
  
  16.  
    17. 
  
  17. } 
    18.

5.1.2 完成类：

 
    
  
  1. import com.lyy.datasty.Mystack.Stack; 
    2. 
  
  2.  
    3. 
  
  3. //链表栈完成 
    4. 
  
  4. public class LinkedListStack<E> implements Stack<E> { 
    5. 
  
  5.  
    6. 
  
  6.     private LinkedList1<E> list; 
    7. 
  
  7.  
    8. 
  
  8.     public LinkedListStack(){ 
    9. 
  
  9.         list = new LinkedList1<>(); 
    10. 
  
  10.     } 
    11. 
  
  11.  
    12. 
  
  12.  
    13. 
  
  13.     @Override 
    14. 
  
  14.     public int getSize() { 
    15. 
  
  15.         return list.getSize(); 
    16. 
  
  16.     } 
    17. 
  
  17.  
    18. 
  
  18.     @Override 
    19. 
  
  19.     public boolean isEmpty() { 
    20. 
  
  20.         return list.isEmpty(); 
    21. 
  
  21.     } 
    22. 
  
  22.  
    23. 
  
  23.     @Override 
    24. 
  
  24.     public void push(E e) { 
    25. 
  
  25.         list.addFirst(e); 
    26. 
  
  26.     } 
    27. 
  
  27.  
    28. 
  
  28.     @Override 
    29. 
  
  29.     public E pop() { 
    30. 
  
  30.         return list.removeFirst(); 
    31. 
  
  31.     } 
    32. 
  
  32.  
    33. 
  
  33.     @Override 
    34. 
  
  34.     public E peek() { 
    35. 
  
  35.         return list.getFirst(); 
    36. 
  
  36.     } 
    37. 
  
  37.  
    38. 
  
  38.     @Override 
    39. 
  
  39.     public String toString() { 
    40. 
  
  40.  
    41. 
  
  41.         StringBuilder res = new StringBuilder(); 
    42. 
  
  42.         res.append("Stack：top  "); 
    43. 
  
  43.         res.append(list); 
    44. 
  
  44.         return res.toString(); 
    45. 
  
  45.     } 
    46. 
  
  46.  
    47. 
  
  47.    
    48. 
  
  48. } 
    49.

5.1.3 运作結果：

 
    
  
  1. public static void main(String[] args) { 
    2. 
  
  2.         LinkedListStack<Integer> stack = new LinkedListStack<>(); 
    3. 
  
  3.         for (int i = 0; i < 5; i  ) { 
    4. 
  
  4.             stack.push(i); 
    5. 
  
  5.             System.out.println(stack); 
    6. 
  
  6.         } 
    7. 
  
  7.         stack.pop(); 
    8. 
  
  8.         System.out.println(stack); 
    9. 
  
  9.  
    10. 
  
  10.  
    11. 
  
  11.     } 
    12.

5.1.4 結果打印出：

 
    
  
  1. Stack：top  0->Null 
    2. 
  
  2. Stack：top  1->0->Null 
    3. 
  
  3. Stack：top  2->1->0->Null 
    4. 
  
  4. Stack：top  3->2->1->0->Null 
    5. 
  
  5. Stack：top  4->3->2->1->0->Null 
    6. 
  
  6. Stack：top  3->2->1->0->Null 
    7.

5.2 应用链表完成序列

5.2.1 接口类

 
    
  
  1. /** 
    2. 
  
  2.  * @program: Data-Structures 
    3. 
  
  3.  * @ClassName Queue 
    4. 
  
  4.  * @description: 
    5. 
  
  5.  * @author: lyy 
    6. 
  
  6.  * @create: 2019-11-21 21:54 
    7. 
  
  7.  * @Version 1.0 
    8. 
  
  8.  **/ 
    9. 
  
  9. public interface Queue<E> { 
    10. 
  
  10.  
    11. 
  
  11.     int getSize(); 
    12. 
  
  12.     boolean isEmpty(); 
    13. 
  
  13.     void enqueue(E e); 
    14. 
  
  14.     E dequeue(); 
    15. 
  
  15.     E getFront(); 
    16. 
  
  16.  
    17. 
  
  17.  
    18. 
  
  18. } 
    19.

5.2.2 完成类

 
    
  
  1. public class LinkedListQueue<E> implements Queue<E>{ 
    2. 
  
  2.  
    3. 
  
  3.     //设计方案独享的内部类，针对客户而言不用了解链表最底层完成， 
    4. 
  
  4.     // 不用了解node这一连接点，对客户屏蔽掉编号完成的最底层完成 
    5. 
  
  5.     private class Node{ 
    6. 
  
  6.         public E e; 
    7. 
  
  7.         public Node next;//public 能够 在LinkedList随便实际操作 
    8. 
  
  8.  
    9. 
  
  9.         public Node(E e, Node next){ 
    10. 
  
  10.             this.e = e; 
    11. 
  
  11.             this.next = next; 
    12. 
  
  12.         } 
    13. 
  
  13.  
    14. 
  
  14.         public Node(E e){ 
    15. 
  
  15.             this(e,null); 
    16. 
  
  16.         } 
    17. 
  
  17.  
    18. 
  
  18.         public Node(){ 
    19. 
  
  19.             this(null,null); 
    20. 
  
  20.         } 
    21. 
  
  21.  
    22. 
  
  22.         @Override 
    23. 
  
  23.         public String toString() { 
    24. 
  
  24.             return e.toString(); 
    25. 
  
  25.         } 
    26. 
  
  26.     } 
    27. 
  
  27.  
    28. 
  
  28.     private Node head,tail; 
    29. 
  
  29.     private int size; 
    30. 
  
  30.  
    31. 
  
  31.     public LinkedListQueue(){ 
    32. 
  
  32.         head = null; 
    33. 
  
  33.         tail = null; 
    34. 
  
  34.         size = 0; 
    35. 
  
  35.     } 
    36. 
  
  36.  
    37. 
  
  37.  
    38. 
  
  38.     @Override 
    39. 
  
  39.     public int getSize() { 
    40. 
  
  40.         return size; 
    41. 
  
  41.     } 
    42. 
  
  42.  
    43. 
  
  43.     @Override 
    44. 
  
  44.     public boolean isEmpty() { 
    45. 
  
  45.         return size == 0; 
    46. 
  
  46.     } 
    47. 
  
  47.  
    48. 
  
  48.     @Override 
    49. 
  
  49.     public void enqueue(E e) { 
    50. 
  
  50.         if(tail == null){ 
    51. 
  
  51.             tail = new Node(e); 
    52. 
  
  52.             head = tail; 
    53. 
  
  53.         }else{ 
    54. 
  
  54.             tail.next = new Node(e); 
    55. 
  
  55.             tail = tail.next; 
    56. 
  
  56.         } 
    57. 
  
  57.         size   ; 
    58. 
  
  58.     } 
    59. 
  
  59.  
    60. 
  
  60.     @Override 
    61. 
  
  61.     public E dequeue() { 
    62. 
  
  62.         if(isEmpty()) 
    63. 
  
  63.             throw new IllegalArgumentException("Cannot dequeue from an empty queue."); 
    64. 
  
  64.  
    65. 
  
  65.         Node retNode = head; 
    66. 
  
  66.         head = head.next; 
    67. 
  
  67.         retNode.next = null; 
    68. 
  
  68.         if(head == null) 
    69. 
  
  69.             tail = null; 
    70. 
  
  70.  
    71. 
  
  71.         size --; 
    72. 
  
  72.  
    73. 
  
  73.         return retNode.e; 
    74. 
  
  74.     } 
    75. 
  
  75.  
    76. 
  
  76.     @Override 
    77. 
  
  77.     public E getFront() { 
    78. 
  
  78.         if(isEmpty()) 
    79. 
  
  79.             throw new IllegalArgumentException("queue is empty."); 
    80. 
  
  80.  
    81. 
  
  81.         return head.e; 
    82. 
  
  82.     } 
    83. 
  
  83.  
    84. 
  
  84.     @Override 
    85. 
  
  85.     public String toString() { 
    86. 
  
  86.         StringBuilder res = new StringBuilder(); 
    87. 
  
  87.         res.append("Queue：front  "); 
    88. 
  
  88.  
    89. 
  
  89.         Node cur = head; 
    90. 
  
  90.         while (cur != null) { 
    91. 
  
  91.             res.append(cur   "->"); 
    92. 
  
  92.             cur = cur.next; 
    93. 
  
  93.         } 
    94. 
  
  94.         res.append("Null tail"); 
    95. 
  
  95.         return res.toString(); 
    96. 
  
  96.     } 
    97. 
  
  97. } 
    98.

5.2.2 检测类

 
    
  
  1. public static void main(String[] args) { 
    2. 
  
  2.         LinkedListQueue<Integer> queue = new LinkedListQueue<>(); 
    3. 
  
  3.         for (int i = 0; i < 10; i  ) { 
    4. 
  
  4.             queue.enqueue(i); 
    5. 
  
  5.             System.out.println(queue); 
    6. 
  
  6.  
    7. 
  
  7.             if(i % 3 ==2){ 
    8. 
  
  8.                 queue.dequeue(); 
    9. 
  
  9.                 System.out.println(queue); 
    10. 
  
  10.             } 
    11. 
  
  11.         } 
    12. 
  
  12.     } 
    13.

打印出結果：

 
    
  
  1. Queue：front  0->Null tail 
    2. 
  
  2. Queue：front  0->1->Null tail 
    3. 
  
  3. Queue：front  0->1->2->Null tail 
    4. 
  
  4. Queue：front  1->2->Null tail 
    5. 
  
  5. Queue：front  1->2->3->Null tail 
    6. 
  
  6. Queue：front  1->2->3->4->Null tail 
    7. 
  
  7. Queue：front  1->2->3->4->5->Null tail 
    8. 
  
  8. Queue：front  2->3->4->5->Null tail 
    9. 
  
  9. Queue：front  2->3->4->5->6->Null tail 
    10. 
  
  10. Queue：front  2->3->4->5->6->7->Null tail 
    11. 
  
  11. Queue：front  2->3->4->5->6->7->8->Null tail 
    12. 
  
  12. Queue：front  3->4->5->6->7->8->Null tail 
    13. 
  
  13. Queue：front  3->4->5->6->7->8->9->Null tail 
    14.

六、大量链表构造

6.1 双链表

编码：

 
    
  
  1. class Node{ 
    2. 
  
  2.   E e; 
    3. 
  
  3.   Node next,prev; 
    4. 
  
  4. } 
    5.

 6.1 循环系统目录

编码：

 
    
  
  1. class Node{ 
    2. 
  
  2.   E e; 
    3. 
  
  3.   Node next,prev; 
    4. 
  
  4. } 
    5.

在java中，LinkedList 最底层应用的便是 循环链表，也就是循环系统双向链表，到这儿大家链表就解读完成了。

the end
免责声明：本文不代表本站的观点和立场，如有侵权请联系本站删除！本站仅提供信息存储空间服务。

精选推荐

随机推荐