链表:单向链表,双向链表,单向环形链表

亦凉 2023-02-27 13:57 28阅读 0赞

1,单向链表

1.1,单项链表基本介绍

  • 链表是以节点的方式存储
  • 链表的每个节点都包括data域和next域,指向下一个节点
  • 链表的各个节点不一定都是连续存储的
  • 链表分为带头结点的链表和不带头结点的链表

1.2,单向链表示意图

在这里插入图片描述

1.3,单向链表代码实现

  1. package com.self.datastructure.linked;
  2. import lombok.Data;
  3. /** * @author LiYanBin * @create 2020-01-08 14:06 **/
  4. public class MyLinkedList {
  5. public static void main(String[] args) {
  6. SimpleLinkedList linkedList = new SimpleLinkedList();
  7. linkedList.addByOrder(new LinkedNode(2, "名称", "昵称"));
  8. linkedList.addByOrder(new LinkedNode(1, "名称", "昵称"));
  9. linkedList.addByOrder(new LinkedNode(4, "名称", "昵称"));
  10. linkedList.addByOrder(new LinkedNode(3, "名称", "昵称"));
  11. linkedList.update(new LinkedNode(1, "覆盖", "覆盖"));
  12. linkedList.delete(new LinkedNode(3, "", ""));
  13. linkedList.showDetails();
  14. }
  15. }
  16. class SimpleLinkedList {
  17. // 初始化头结点
  18. private LinkedNode head = new LinkedNode(-1, "", "", null);
  19. // 添加数据, 直接添加不带过滤
  20. public void add(LinkedNode linkedNode) {
  21. // 赋值头节点到临时节点
  22. LinkedNode temp = head;
  23. while (null != temp.getNext()) {
  24. temp = temp.getNext();
  25. }
  26. // 将尾节点的下一个节点指向当前节点
  27. temp.setNext(linkedNode);
  28. }
  29. // 添加数据, 按照主键排序
  30. public void addByOrder(LinkedNode linkedNode) {
  31. // 赋值头几点到临时节点
  32. LinkedNode temp = head;
  33. while (null != temp.getNext()) {
  34. LinkedNode nextNode = temp.getNext();
  35. // 进行升序排列
  36. if (nextNode.getNo() > linkedNode.getNo()) {
  37. temp.setNext(linkedNode);
  38. linkedNode.setNext(nextNode);
  39. return;
  40. // 相同直接进行修改
  41. } else if (nextNode.getNo() == linkedNode.getNo()) {
  42. temp.setNext(linkedNode);
  43. linkedNode.setNext(nextNode.getNext());
  44. nextNode.setNext(null); // 辅助GC
  45. return;
  46. }
  47. temp = nextNode;
  48. }
  49. // 将尾节点的下一个节点指向当前节点
  50. temp.setNext(linkedNode);
  51. }
  52. // 修改数据
  53. public void update(LinkedNode linkedNode) {
  54. LinkedNode temp = head;
  55. while (null != temp) {
  56. LinkedNode next = temp.getNext();
  57. if (null != next && next.getNo() == linkedNode.getNo()) {
  58. temp.setNext(linkedNode);
  59. linkedNode.setNext(next.getNext());
  60. next.setNext(null); // 辅助GC
  61. return;
  62. }
  63. temp = next;
  64. }
  65. }
  66. // 删除节点, 根据编号删除
  67. public void delete(LinkedNode linkedNode) {
  68. LinkedNode temp = head;
  69. while (null != temp.getNext()) {
  70. LinkedNode next = temp.getNext();
  71. // 找到该节点, 并把该节点的next节点指向上一个节点的next, 把该节点挂空
  72. if (next.getNo() == linkedNode.getNo()) {
  73. temp.setNext(next.getNext());
  74. next.setNext(null); // 辅助GC
  75. return;
  76. }
  77. temp = next;
  78. }
  79. }
  80. // 展示详情信息
  81. public void showDetails() {
  82. LinkedNode next = head.getNext();
  83. while (next != null) {
  84. System.out.println(next);
  85. next = next.getNext();
  86. }
  87. }
  88. }
  89. @Data
  90. class LinkedNode {
  91. // 编号, 编号为主键, 不允许重复, 并需要顺序处理
  92. private int no;
  93. // 名称
  94. private String name;
  95. // 昵称
  96. private String nickName;
  97. // 单项链表
  98. private LinkedNode next;
  99. public LinkedNode(int no, String name, String nickName) {
  100. this(no, name, nickName, null);
  101. }
  102. public LinkedNode(int no, String name, String nickName, LinkedNode next) {
  103. this.no = no;
  104. this.name = name;
  105. this.nickName = nickName;
  106. this.next = next;
  107. }
  108. @Override
  109. public String toString() {
  110. return "[LinkedNode: no = " + no + ", name = " + name + ", nickName = " + nickName + "]";
  111. }
  112. }

1.4,单向链表相关面试题

1.4.1,获取单链表的节点个数

  1. /** * 获取单向链表中有效节点的数量 * @param head 头节点 * @param isNeedHead 头节点是否是有效节点 * @return */
  2. public static int getNodeLength(LinkedNode head, boolean isNeedHead) {
  3. if (null == head) {
  4. return 0;
  5. }
  6. // 需要头节点直接初始化为1,表示头结点已经统计
  7. int count = isNeedHead ? 1 : 0;
  8. LinkedNode temp = head;
  9. for (;null != temp.getNext();) {
  10. count++;
  11. temp = temp.getNext();
  12. }
  13. return count;
  14. }

1.4.2,查找单向链表中的倒数第K个节点:即获取正数第(count - K)个节点的数据

  1. /** * 获取单链表中的倒数第K个节点 * 索引从0开始算, 即倒是第K个节点就是正数第(length - k) * @param head 单向链表头结点 * @param isNeedHead 头结点是否是有效节点 * @param descCount 倒数位置 * @return */
  2. public static LinkedNode getIndexDataDesc(LinkedNode head, boolean isNeedHead, int descCount) {
  3. // 获取数量
  4. int count = getNodeLength(head, isNeedHead);
  5. if (count < descCount) {
  6. throw new IndexOutOfBoundsException("索引越界");
  7. }
  8. int index = count - descCount;
  9. LinkedNode temp = isNeedHead ? head : head.getNext();
  10. for (int i = 0; i < index; i++, temp = temp.getNext());
  11. return temp;
  12. }

1.4.3,单链表反转

  1. /** * 单向链表反转 * 每次获取下一个节点, 并重新构造该节点为头节点 * 把之前存储的头节点置位该节点的next节点, 即一步步遍历, 一步步后推 * @param head 单向链表 * @param isNeedHead 头节点是否是有效节点 * @return */
  2. public static LinkedNode reverseLinked(LinkedNode head, boolean isNeedHead) {
  3. // 获取有效数据
  4. LinkedNode realData = isNeedHead ? head : head.getNext();
  5. // 初始化返回数据, 不需要头节点的直接初始化虚拟节点
  6. LinkedNode reverseLinked = isNeedHead ? null : new LinkedNode(head);
  7. // 反转
  8. for (; null != realData ;) {
  9. // 构造新节点
  10. LinkedNode newNode = new LinkedNode(realData);
  11. if (null == reverseLinked) {
  12. reverseLinked = newNode;
  13. } else {
  14. // 获取下一个节点
  15. // 非虚拟头节点
  16. if (isNeedHead) {
  17. newNode.setNext(reverseLinked);
  18. reverseLinked = newNode;
  19. } else { // 虚拟头节点
  20. // 获取虚拟头节点的下一个节点
  21. LinkedNode nextNode = reverseLinked.getNext();
  22. // 把原节点挂到该节点下
  23. newNode.setNext(nextNode);
  24. // 把当前节点设为下一个节点
  25. reverseLinked.setNext(newNode);
  26. }
  27. }
  28. realData = realData.getNext();
  29. }
  30. return reverseLinked;
  31. }

1.4.4,反向打印链表

  1. /** * 从尾节点开始打印链表 * 方式1: * 先将单链表进行翻转操作, 然后进行遍历即可 * 该方式可能会改变原链表结构, 不建议 * 该方式可以直接调用反转方法, 并打印 * 方式2: * 利用栈数据结构, 将各个节点压入栈中 * 利用栈先进后出的特点, 完成逆序打印 * @param linkedNode 节点 * @param isNeedHead 头结点是否是有效节点 */
  2. public static void showDetailsReverse(LinkedNode linkedNode, boolean isNeedHead) {
  3. Stack<LinkedNode> stack = new Stack<>();
  4. LinkedNode realNode = isNeedHead ? linkedNode : linkedNode.getNext();
  5. if (null == realNode) {
  6. return;
  7. }
  8. // 遍历节点, 添加到栈中
  9. for (; null != realNode; ) {
  10. stack.push(realNode);
  11. realNode = realNode.getNext();
  12. }
  13. // 打印栈对象
  14. LinkedNode currNode = null;
  15. for (;stack.size() > 0; ) {
  16. System.out.println(stack.pop());
  17. }
  18. }

1.4.5,合并两个有序的单链表,合并之后的链表依然有序

  1. /** * 合并两个有序(顺序)链表, 默认不需要头结点 * @param firstNode * @param secondNode */
  2. public static LinkedNode mergeOrderNode(LinkedNode firstNode, LinkedNode secondNode) {
  3. // 获取有效节点
  4. firstNode = firstNode.getNext();
  5. secondNode = secondNode.getNext();
  6. // 存在为空, 直接返回
  7. if (null == firstNode || null == secondNode) {
  8. return null == firstNode ? secondNode : firstNode;
  9. }
  10. // 比较节点数据
  11. // 用首节点编号较小的链表进行遍历,
  12. // 较大编号的链表进行填充, 最终返回有效节点
  13. return firstNode.getNo() > secondNode.getNo()
  14. ? doMergeOrderNode(secondNode, firstNode)
  15. : doMergeOrderNode(firstNode, secondNode);
  16. }
  17. public static LinkedNode doMergeOrderNode(LinkedNode firstNode, LinkedNode secondNode) {
  18. // 初始化头节点
  19. SimpleLinkedList simpleLinkedList = new SimpleLinkedList();
  20. // 遍历节点进行填充
  21. for (;null != firstNode;) {
  22. // first节点数据大于second节点数据, 将second节点数据置于之前
  23. for (;secondNode != null && firstNode.getNo() > secondNode.getNo();) {
  24. simpleLinkedList.add(new LinkedNode(secondNode));
  25. // 当前second已经被比较过, 向前推动一位
  26. secondNode = secondNode.getNext();
  27. }
  28. // 处理完成当前区间的seconde数据后, 添加first数据
  29. simpleLinkedList.add(new LinkedNode(firstNode));
  30. firstNode = firstNode.getNext();
  31. }
  32. // first节点遍历完成后, 如果second节点还存在数据, 全部添加到最后
  33. for (;null != secondNode;) {
  34. simpleLinkedList.add(new LinkedNode(secondNode));
  35. secondNode = secondNode.getNext();
  36. }
  37. return simpleLinkedList.getHead();
  38. }

2,双向链表

2.1,双向链表介绍

  • 单向链表查找方向是能是一个方向;双向链表可以向前或者向后查找
  • 单向链表不能自我删除,需要靠辅助节点即前一个节点;双向链表可以进行自删除,因为同时持有上一个节点和下一个节点的地址
  • 遍历:遍历方式与单向链表基本一致,不过双向链表可以直接从后往前遍历
  • 添加

    • 先找到需要插入到双向链表的目标节点
    • 讲节点和对应前置节点与后置节点的prenext属性进行修改
  • 删除

    • 双向链表可以实现单个节点的自删除,直接遍历到需要删除的当前节点
    • 将当前节点前置节点的next属性指向当前节点的后置节点
    • 将当前节点后置节点的pre属性指向当前节点的前置节点
    • 处理之后,当前节点在链表中会挂空,也就是从链表中删除

2.2,代码演示

  1. package com.self.datastructure.linked;
  2. import lombok.Data;
  3. /** * 双向链表 * @author LiYanBin * @create 2020-01-09 14:21 **/
  4. public class DoubleLinkedList {
  5. public static void main(String[] args) {
  6. DLinkedList dLinkedList = new DLinkedList();
  7. // dLinkedList.add(new DoubleNode(0, "名称", "昵称"));
  8. // dLinkedList.add(new DoubleNode(1, "名称", "昵称"));
  9. // dLinkedList.add(new DoubleNode(2, "名称", "昵称"));
  10. // dLinkedList.add(new DoubleNode(3, "名称", "昵称"));
  11. dLinkedList.addByOrder(new DoubleNode(3, "名称", "昵称"));
  12. dLinkedList.addByOrder(new DoubleNode(2, "名称", "昵称"));
  13. dLinkedList.addByOrder(new DoubleNode(4, "名称", "昵称"));
  14. dLinkedList.addByOrder(new DoubleNode(1, "名称", "昵称"));
  15. dLinkedList.showDetailsFromHead();
  16. }
  17. }
  18. class DLinkedList {
  19. private DoubleNode head = new DoubleNode(-1, "", "");
  20. private DoubleNode tail = new DoubleNode(-2, "", "");
  21. public DLinkedList() {
  22. head.setNext(tail);
  23. tail.setPre(head);
  24. }
  25. // 根据序列号添加
  26. public void addByOrder(DoubleNode doubleNode) {
  27. // 获取有效数据
  28. DoubleNode realData = head.getNext();
  29. for (;null != realData;) {
  30. // 遍历到尾节点, 直接添加
  31. if (realData == tail) {
  32. add(doubleNode);
  33. return;
  34. }
  35. // 编号大于当前编号, 则置于该编号之前
  36. if (realData.getNo() > doubleNode.getNo()) {
  37. DoubleNode pre = realData.getPre();
  38. pre.setNext(doubleNode);
  39. doubleNode.setPre(pre);
  40. doubleNode.setNext(realData);
  41. realData.setPre(doubleNode);
  42. return;
  43. }
  44. realData = realData.getNext();
  45. }
  46. }
  47. // 添加数据到链表中, 默认添加到链表尾部
  48. public void add(DoubleNode doubleNode) {
  49. // 获取尾节点的上一个节点
  50. DoubleNode preNode = tail.getPre();
  51. // 将上一个节点置为该节点的前置节点,
  52. preNode.setNext(doubleNode);
  53. // 添加该节点的前置节点和后置节点
  54. doubleNode.setPre(preNode);
  55. doubleNode.setNext(tail);
  56. // 将tail节点的前置节点改为该节点
  57. tail.setPre(doubleNode);
  58. }
  59. // 删除指定数据
  60. public void remove(int no) {
  61. DoubleNode realData = head.getNext();
  62. for (;null != realData && tail != realData;) {
  63. // 匹配到数据, 直接移除
  64. if (realData.getNo() == no) {
  65. // 获取前置节点
  66. DoubleNode pre = realData.getPre();
  67. // 获取后置节点
  68. DoubleNode next = realData.getNext();
  69. // 互为前置后置节点, 将当前节点挂空
  70. pre.setNext(next);
  71. next.setPre(pre);
  72. realData = null; // 辅助GC
  73. return;
  74. }
  75. realData = realData.getNext();
  76. }
  77. }
  78. // 打印, 从头打印
  79. public void showDetailsFromHead() {
  80. DoubleNode realData = head.getNext();
  81. for (;null != realData && tail != realData;) {
  82. System.out.println(realData);
  83. realData = realData.getNext();
  84. }
  85. }
  86. // 打印, 从尾部打印
  87. public void showDetailsFromTail() {
  88. DoubleNode realData = tail.getPre();
  89. for (;null != realData && realData != head;) {
  90. System.out.println(realData);
  91. realData = realData.getPre();
  92. }
  93. }
  94. public DoubleNode getHead() {
  95. return head;
  96. }
  97. public DoubleNode getTail() {
  98. return tail;
  99. }
  100. }
  101. @Data
  102. class DoubleNode {
  103. private DoubleNode pre;
  104. private DoubleNode next;
  105. private int no;
  106. private String name;
  107. private String nickName;
  108. public DoubleNode(DoubleNode doubleNode) {
  109. this(doubleNode.getNo(), doubleNode.getName(), doubleNode.getNickName());
  110. }
  111. public DoubleNode(int no, String name, String nickName) {
  112. this(no, name, nickName, null, null);
  113. }
  114. public DoubleNode(int no, String name, String nickName, DoubleNode pre, DoubleNode next) {
  115. this.no = no;
  116. this.name = name;
  117. this.nickName = nickName;
  118. this.pre = pre;
  119. this.next = next;
  120. }
  121. @Override
  122. public String toString() {
  123. return "[DoubleNode: no = " + no + ", name = " + name + ", nickName = " + nickName + "]";
  124. }
  125. }

3,单向环形链表:约瑟夫问题(Josephu)

3.1,Josephu(约瑟夫)问题介绍

  • 设编号为1,2 … n的n个人围成一个圈,并约定编号为K(1<=K<=n)的人从1开始报数,数到M的那个人出列,他的下一位又从1开始数,依次类推,直到所有人出列
  • 通过不带头节点的单向链表来处理

3.2,Josephu(约瑟夫)问题实现代码

  1. package com.self.datastructure.linked;
  2. import lombok.Data;
  3. import java.util.Scanner;
  4. /** * 约瑟夫问题解决代码 * @author LiYanBin * @create 2020-01-09 15:45 **/
  5. public class JosephuQuestion {
  6. public static void main(String[] args) {
  7. // 初始化游戏玩家
  8. JosephuLinkedList linkedList = new JosephuLinkedList();
  9. for (int i = 0; i < 10; i++) {
  10. linkedList.add(new Node(i));
  11. }
  12. linkedList.startGame();
  13. }
  14. }
  15. class JosephuLinkedList {
  16. // 该头节点表示有效节点
  17. private Node head = null;
  18. // 统计总数
  19. private int totalCount = 0;
  20. // 开始游戏
  21. public void startGame() {
  22. Scanner scanner = new Scanner(System.in);
  23. // 默认从头号玩家开始
  24. Node startNode = head;
  25. for(;;) {
  26. if (totalCount == 0) {
  27. System.out.println("编号全部移除, 游戏结束...");
  28. return;
  29. }
  30. System.out.println("当前游戏人数: " + totalCount);
  31. String input = scanner.nextLine();
  32. switch (input) {
  33. case "s": // show
  34. showDetails();
  35. break;
  36. case "r": // run
  37. System.out.println("输入跳过的人数: M");
  38. int runCount = scanner.nextInt();
  39. // 移除数据
  40. // 从1号开始数两位, 则移除3号, 下一次从4号开始玩
  41. // 此处获取要移除数据的前一位
  42. Node targetPreNode = startNode;
  43. for (int i = 0; i < runCount - 1; i++, targetPreNode = targetPreNode.getNext());
  44. // 记录, 获取移除数据的下一个数据, 此处需要两次next
  45. startNode = targetPreNode.getNext().getNext();
  46. System.out.println("移除完成..., 移除编号: " + targetPreNode.getNext().getNo() + ", 下次开始编号: " + startNode.getNo());
  47. // 直接移除, 将该节点的next 指向目标节点的next, 将目标节点挂空
  48. targetPreNode.setNext(targetPreNode.getNext().getNext());
  49. totalCount--;
  50. // 移除, 此处不需要调移除, 因为节点已经挂空
  51. // remove(targetNode.getNo());
  52. break;
  53. case "e": //exit
  54. return;
  55. default:
  56. break;
  57. }
  58. }
  59. }
  60. // 添加元素
  61. public void add(Node node) {
  62. // 设置为头结点
  63. if (null == head) {
  64. totalCount++;
  65. head = node;
  66. head.setNext(head);
  67. return;
  68. }
  69. // 与头节点进行比较
  70. Node temp = head;
  71. for (;null != temp;) {
  72. // 从头节点开始, 每次获取到下一个节点进行判断
  73. Node next = temp.getNext();
  74. if (head == next) { // 与头节点相等, 说明已经到有效链表末尾
  75. totalCount++;
  76. temp.setNext(node);
  77. node.setNext(head);
  78. return;
  79. }
  80. temp = temp.getNext();
  81. }
  82. }
  83. public void remove(int no) {
  84. if (null == head) return;
  85. // 头结点处理
  86. if (head.getNo() == no) {
  87. // 链表只有当前数据, 直接清空
  88. if (head == head.getNext()) {
  89. head = null;
  90. } else {
  91. // 链表存在其他数据, 移除头节点后遍历
  92. Node preHead = head;
  93. head = head.getNext();
  94. Node temp = head;
  95. for (; null != temp; ) {
  96. // 再遇头节点
  97. if (preHead == temp.getNext()) {
  98. temp.setNext(head);
  99. break;
  100. }
  101. temp = temp.getNext();
  102. }
  103. }
  104. } else { // 非头节点处理
  105. Node temp = head;
  106. for (;null != temp;) {
  107. Node next = temp.getNext();
  108. // 无论是否存在, 再遇头结点直接移除
  109. if (next == head) {
  110. return;
  111. }
  112. // 存在, 直接移除
  113. if (next.getNo() == no) {
  114. temp.setNext(next.getNext());
  115. break;
  116. }
  117. temp = temp.getNext();
  118. }
  119. }
  120. totalCount--;
  121. }
  122. public void showDetails() {
  123. if (null == head) {
  124. System.out.println("数据为空...");
  125. return;
  126. }
  127. Node temp = head;
  128. boolean flag = false;
  129. for (;null != temp;) {
  130. if (flag && temp == head) {
  131. System.out.println("遍历完成...");
  132. return;
  133. }
  134. flag = true;
  135. System.out.println(temp);
  136. temp = temp.getNext();
  137. }
  138. }
  139. public Node getHead() {
  140. return head;
  141. }
  142. }
  143. @Data
  144. class Node {
  145. // 编号
  146. private int no;
  147. // 下一个节点
  148. private Node next;
  149. public Node(int no) {
  150. this.no = no;
  151. }
  152. @Override
  153. public String toString() {
  154. return "[Node: no = " + no + "]";
  155. }
  156. }

发表评论

表情:
评论列表 (有 0 条评论,28人围观)

还没有评论,来说两句吧...

相关阅读