链表：单向链表，双向链表，单向环形链表

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

1，单向链表

1.1，单项链表基本介绍

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

1.2，单向链表示意图

在这里插入图片描述

1.3，单向链表代码实现

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

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. }
  18. public static LinkedNode doMergeOrderNode(LinkedNode firstNode, LinkedNode secondNode) { 
  19.     // 初始化头节点
  20.     SimpleLinkedList simpleLinkedList = new SimpleLinkedList();
  21.     // 遍历节点进行填充
  22.     for (;null != firstNode;) { 
  23.         // first节点数据大于second节点数据, 将second节点数据置于之前
  24.         for (;secondNode != null && firstNode.getNo() > secondNode.getNo();) { 
  25.             simpleLinkedList.add(new LinkedNode(secondNode));
  26.             // 当前second已经被比较过, 向前推动一位
  27.             secondNode = secondNode.getNext();
  28.         }
  29.         // 处理完成当前区间的seconde数据后, 添加first数据
  30.         simpleLinkedList.add(new LinkedNode(firstNode));
  31.         firstNode = firstNode.getNext();
  32.     }
  33.     // first节点遍历完成后, 如果second节点还存在数据, 全部添加到最后
  34.     for (;null != secondNode;) { 
  35.         simpleLinkedList.add(new LinkedNode(secondNode));
  36.         secondNode = secondNode.getNext();
  37.     }
  38.     return simpleLinkedList.getHead();
  39. }

2，双向链表

2.1，双向链表介绍

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

  • 添加：

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

  • 删除：

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

2.2，代码演示

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

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

发表评论

表情：
评论列表 （有 0 条评论，28人围观）

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

相关阅读