一身转战三千里，一剑曾当百万师。这篇文章主要讲述『数据结构与算法』链表（单链表双链表环形链表）：原理与Java实现相关的知识，希望能为你提供帮助。
1. 前言
通过前篇文章《数组》了解到数组的存储结构是一块连续的内存，插入和删除元素时其每个部分都有可能整体移动。为了避免这样的线性开销，我们需要保证数据可以不连续存储。本篇介绍另一种数据结构：链表。
2. 链表（Linked List）
链表是一种线性的数据结构，其物理存储结构是零散的，数据元素通过指针实现链表的逻辑顺序。链表由一系列结点（链表中每一个元素称为节点）组成，节点可以在内存中动态生成。
链表的特性：

• 链表是以节点（Node）的方式来存储，所以又叫链式存储。
• 节点可以连续存储，也可以不连续存储。
• 节点的逻辑顺序与物理顺序可以不一致
• 表可以扩充（不像数组那样还得重新分配内存空间）

链表分为单链表、双链表和环形链表，下面通过实例逐个介绍。
3. 单链表（Singly Linked List）
单链表又叫单向链表，其节点由两部分构成：

• data域：数据域，用来存储元素数据
• next域：用于指向下一节点

单链表的结构如下图：

文章图片

3.1 单链表的操作单链表的所有操作都是从head开始，head本身不存储元素，其next指向第一个节点，然后顺着next链进行一步步操作。其尾部节点的next指向为空，这也是判断尾部节点的依据。
这里主要介绍插入和删除节点的操作。
3.1.1 插入节点向单链表中插入一个新节点，可以通过调整两次next指向来完成。如下图所示，X为新节点，将其next指向为A2，再将A1的next指向为X即可。
若是从尾部节点插入，直接将尾部节点的next指向新节点即可。

文章图片

3.1.2 删除节点从单链表中删除一个节点，可以通过修改next指向来实现，如下图所示，将A1的next指向为A3，这样便删除A2，A2的内存空间会自动被垃圾回收。
若是删除尾部节点，直接将上一节点的next指向为空即可。

文章图片

3.2 代码实现我们使用java代码来实现一个单链表。其中Node类存储单链表的一个节点，SinglyLinkedList类实现了单链表的所有操作方法。
SinglyLinkedList类使用带头节点的方式实现，即head节点，该节点不存储数据，只是标记单链表的开始。

public class SinglyLinkedListDemo {public static void main(String[] args) { Node node1 = new Node(1, "张三"); Node node2 = new Node(3, "李四"); Node node3 = new Node(7, "王五"); Node node4 = new Node(5, "赵六"); SinglyLinkedList singlyLinkedList = new SinglyLinkedList(); System.out.println("-----------添加节点（尾部）"); singlyLinkedList.add(node1); singlyLinkedList.add(node2); singlyLinkedList.add(node3); singlyLinkedList.add(node4); singlyLinkedList.print(); System.out.println("-----------获取某个节点"); Node node = singlyLinkedList.get(3); System.out.println(node); singlyLinkedList.remove(node3); System.out.println("-----------移除节点"); singlyLinkedList.print(); System.out.println("-----------修改节点"); singlyLinkedList.update(new Node(5, "赵六2")); singlyLinkedList.print(); System.out.println("-----------按顺序添加节点"); Node node5 = new Node(4, "王朝"); singlyLinkedList.addOfOrder(node5); singlyLinkedList.print(); }private static class SinglyLinkedList {// head节点是单链表的开始，不用来存储数据 private Node head = new Node(0, null); /** * 将节点添加到尾部 * * @param node */ public void add(Node node) { Node temp = head; while (true) { if (temp.next == null) { temp.next = node; break; } temp = temp.next; } }/** * 按顺序添加节点 * * @param node */ public void addOfOrder(Node node) { Node temp = head; while (true) { if (temp.next == null) { temp.next = node; break; } else if(temp.next.key > node.getKey()){ node.next = temp.next; temp.next = node; break; } temp = temp.next; } }/** * 获取某个节点 * * @param key * @return */ public Node get(int key) { if (head.next == null) { return null; } Node temp = head.next; while (temp != null) { if (temp.key == key) { return temp; } temp = temp.next; } return null; }/** * 移除一个节点 * * @param node */ public void remove(Node node) { Node temp = head; while (true) { if (temp.next == null) { break; } if (temp.next.key == node.key) { temp.next = temp.next.next; break; } temp = temp.next; } }/** * 修改一个节点 * * @param node */ public void update(Node node) { Node temp = head.next; while (true) { if (temp == null) { break; } if (temp.key == node.key) { temp.value = https://www.songbingjia.com/android/node.value; break; } temp = temp.next; } }/** * 打印链表 */ public void print() { Node temp = head.next; while (temp != null) { System.out.println(temp.toString()); temp = temp.next; } }}private static class Node { private final int key; private String value; private Node next; public Node(int key, String value) { this.key = key; this.value = value; }public int getKey() { return key; }public String getValue() { return value; }public void setValue(String value) { this.value = value; }public Node getNext() { return next; }@Override public String toString() { return"Node{" + "key=" + key + ", value=https://www.songbingjia.com/'" + value + \'\\\'\' + \'}\'; } } }

输出结果：

-----------添加节点（尾部） Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=3, value=https://www.songbingjia.com/'李四\'} Node{key=7, value=https://www.songbingjia.com/'王五\'} Node{key=5, value=https://www.songbingjia.com/'赵六\'} -----------获取某个节点 Node{key=3, value=https://www.songbingjia.com/'李四\'} -----------移除节点 Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=3, value=https://www.songbingjia.com/'李四\'} Node{key=5, value=https://www.songbingjia.com/'赵六\'} -----------修改节点 Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=3, value=https://www.songbingjia.com/'李四\'} Node{key=5, value=https://www.songbingjia.com/'赵六2\'} -----------按顺序添加节点 Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=3, value=https://www.songbingjia.com/'李四\'} Node{key=4, value=https://www.songbingjia.com/'王朝\'} Node{key=5, value=https://www.songbingjia.com/'赵六2\'}

3.3 单链表的缺点通过对单链表的分析，可以看出单链表有如下缺点：
（1）单链表的查找方法只能是一个方向
（2）单链表不能自我删除，需要靠上一节点进行辅助操作。
而这些缺点可以通过双链表来解决，下面来看详细介绍。
4. 双链表（Doubly Linked List）
双链表又叫双向链表，其节点由三部分构成：

• prev域：用于指向上一节点
• data域：数据域，用来存储元素数据
• next域：用于指向下一节点

双链表的结构如下图：

文章图片

4.1 双链表的操作双链表的操作可以从两端开始，从第一个节点通过next指向可以一步步操作到尾部，从最后一个节点通过prev指向可以一步步操作到头部。
这里主要介绍插入和删除节点的操作。
4.1.1 插入节点向双链表中插入一个新节点，需要通过调整两次prev指向和两次next指向来完成。如下图所示，X为新节点，将A1的next指向X，将X的next指向A2，将A2的prev指向X，将X的prev指向A1即可。

文章图片

4.1.2 删除节点从双链表中删除一个节点，需要通过调整一次prev指向和一次next指向来完成。如下图所示，删除A2节点，将A1的next指向A3，将A3的 prev指向A1即可。

文章图片

4.2 代码实现我们使用Java代码来实现一个双链表。其中 Node类存储双链表的一个节点，DoublyLinkedList类实现双链表的所有操作方法。
DoublyLinkedList类使用不带头节点的方式实现，其中first为第一个节点，last为最后一个节点。这两个节点默认都为空，若只有一个元素时，则两个节点指向同一元素。

public class DoublyLinkedListDemo {public static void main(String[] args) {DoublyLinkedList doublyLinkedList = new DoublyLinkedList(); System.out.println("-----------从尾部添加节点"); doublyLinkedList .addToTail(new Node(1, "张三")) .addToTail(new Node(3, "李四")) .addToTail(new Node(7, "王五")) .addToTail(new Node(5, "赵六")) .print(); System.out.println("-----------从头部添加节点"); doublyLinkedList .addToHead(new Node(0, "朱开山")) .print(); System.out.println("-----------获取某个节点"); System.out.println(doublyLinkedList.get(3)); System.out.println("-----------移除节点"); doublyLinkedList .remove(new Node(3, "李四")) .print(); System.out.println("-----------修改节点"); doublyLinkedList .update(new Node(5, "赵六2")).print(); System.out.println("-----------按顺序添加节点"); doublyLinkedList .addOfOrder(new Node(4, "王朝")) .print(); }private static class DoublyLinkedList {private Node first = null; // first节点是双链表的头部，即第一个节点 private Node last = null; // tail节点是双链表的尾部，即最后一个节点/** * 从尾部添加 * * @param node */ public DoublyLinkedList addToTail(Node node) { if (last == null) { first = node; } else { last.next = node; node.prev = last; } last = node; return this; }/** * 按照顺序添加 * * @param node */ public DoublyLinkedList addOfOrder(Node node) { if (first == null) { first = node; last = node; return this; }// node比头节点小，将node设为头节点 if (first.key > node.key) { first.prev = node; node.next = first; first = node; return this; }// node比尾节点大，将node设为尾节点 if (last.key < node.key) { last.next = node; node.prev = last; last = node; return this; }Node temp = first.next; while (true) { if (temp.key > node.key) { node.next = temp; node.prev = temp.prev; temp.prev.next = node; temp.prev = node; break; } temp = temp.next; } return this; }/** * 从头部添加 * * @param node */ public DoublyLinkedList addToHead(Node node) { if (first == null) { last = node; } else { node.next = first; first.prev = node; } first = node; return this; }/** * 获取节点 * * @param key * @return */ public Node get(int key) { if (first == null) { return null; } Node temp = first; while (temp != null) { if (temp.key == key) { return temp; } temp = temp.next; } return null; }/** * 移除节点 * * @param node */ public DoublyLinkedList remove(Node node) { if (first == null) { return this; } // 要移除的是头节点 if (first == node) { first.next.prev = null; first = first.next; return this; } // 要移除的是尾节点 if (last == node) { last.prev.next = null; last = last.prev; return this; }Node temp = first.next; while (temp != null) { if (temp.key == node.key) { temp.prev.next = temp.next; temp.next.prev = temp.prev; break; } temp = temp.next; } return this; }/** * 修改某个节点 * * @param node */ public DoublyLinkedList update(Node node) { if (first == null) { return this; }Node temp = first; while (temp != null) { if (temp.key == node.key) { temp.value = https://www.songbingjia.com/android/node.value; break; } temp = temp.next; } return this; }/** * 打印链表 */ public void print() { if (first == null) { return; } Node temp = first; while (temp != null) { System.out.println(temp); temp = temp.next; } } }private static class Node { private final int key; private String value; private Node prev; // 指向上一节点 private Node next; // 指向下一节点public Node(int key, String value) { this.key = key; this.value = value; }@Override public String toString() { return"Node{" + "key=" + key + ", value=https://www.songbingjia.com/'" + value + \'\\\'\' + \'}\'; } } }

输出结果：

-----------从尾部添加节点 Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=3, value=https://www.songbingjia.com/'李四\'} Node{key=7, value=https://www.songbingjia.com/'王五\'} Node{key=5, value=https://www.songbingjia.com/'赵六\'} -----------从头部添加节点 Node{key=0, value=https://www.songbingjia.com/'朱开山\'} Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=3, value=https://www.songbingjia.com/'李四\'} Node{key=7, value=https://www.songbingjia.com/'王五\'} Node{key=5, value=https://www.songbingjia.com/'赵六\'} -----------获取某个节点 Node{key=3, value=https://www.songbingjia.com/'李四\'} -----------移除节点 Node{key=0, value=https://www.songbingjia.com/'朱开山\'} Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=7, value=https://www.songbingjia.com/'王五\'} Node{key=5, value=https://www.songbingjia.com/'赵六\'} -----------修改节点 Node{key=0, value=https://www.songbingjia.com/'朱开山\'} Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=7, value=https://www.songbingjia.com/'王五\'} Node{key=5, value=https://www.songbingjia.com/'赵六2\'} -----------按顺序添加节点 Node{key=0, value=https://www.songbingjia.com/'朱开山\'} Node{key=1, value=https://www.songbingjia.com/'张三\'} Node{key=4, value=https://www.songbingjia.com/'王朝\'} Node{key=7, value=https://www.songbingjia.com/'王五\'} Node{key=5, value=https://www.songbingjia.com/'赵六2\'}

5. 环形链表（Circular Linked List）
环形链表又叫循环链表，本文讲述的是单向环形链表，其与单链表的唯一区别是尾部节点的next不再为空，则是指向了头部节点，这样便形成了一个环。
环形链表的结构如下图：

文章图片

5.1 约瑟夫问题约瑟夫问题：有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”。
引自百度百科：

文章图片

5.2 代码实现我们使用Java代码来实现一个环形链表，并将节点按约瑟夫问题顺序出列。

public class CircularLinkedListDemo {public static void main(String[] args) {CircularLinkedList circularLinkedList = new CircularLinkedList(); System.out.println("-----------添加10个节点"); for (int i = 1; i < = 10; i++) { circularLinkedList.add(new Node(i)); } circularLinkedList.print(); System.out.println("-----------按约瑟夫问题顺序出列"); circularLinkedList.josephusProblem(3); }private static class CircularLinkedList { private Node first = null; // 头部节点，即第一个节点/** * 添加节点，并将新添加的节点的next指向头部，形成一个环形 * * @param node * @return */ public void add(Node node) { if (first == null) { first = node; first.next = first; return; }Node temp = first; while (true) { if (temp.next == null || temp.next == first) { temp.next = node; node.next = first; break; } temp = temp.next; } }/** * 按约瑟夫问题顺序出列 * 即从第1个元素开始报数，报到num时当前元素出列，然后重新从下一个元素开始报数，直至所有元素出列 * * @param num 表示报几次数 */ public void josephusProblem(int num) { Node currentNode = first; // 将当前节点指向最后一个节点 do { currentNode = currentNode.next; } while (currentNode.next != first); // 开始出列 while (true) { // 当前节点要指向待出列节点的前一节点（双向环形队列不需要） for (int i = 0; i < num - 1; i++) { currentNode = currentNode.next; } System.out.printf("%s\\t", currentNode.next.no); if(currentNode.next == currentNode){ break; } currentNode.next = currentNode.next.next; } }/** * 输出节点 */ public void print() { if (first == null) { return; }Node temp = first; while (true) { System.out.printf("%s\\t", temp.no); if (temp.next == first) { break; } temp = temp.next; } System.out.println(); } }private static class Node { private final int no; private Node next; // 指向下一节点public Node(int no) { this.no = no; }@Override public String toString() { return "Node{" + "no=" + no + \'}\'; } } }

输出结果：

-----------添加10个节点 12345678910 -----------按约瑟夫问题顺序出列 36927185104

推荐阅读

• 数组
• 稀疏数组
• 链表（单链表、双链表、环形链表）
• 栈
• 队列
• 树
• 二叉树
• 二叉查找树（BST）
• AVL树（平衡二叉树）
• B树
• 散列表（哈希表）

【『数据结构与算法』链表（单链表双链表环形链表）（原理与Java实现）】
文章图片

推荐阅读

• 

  如何下载bt磁力种子
• 

  亚索在永恩出来后新台词 mysql的特征及性能
• 

  三星W2019手机屏幕失灵维修价格
• 

  解压包子使用感怎么样 网红解压包子里面是什么
• 

  经常莫名其妙的就来一下胸口痛，想知道怎么了
• 

  非法吸收公众存款罪怎么处罚 非法吸收公众存款罪怎么处罚的
• 

  方太烤箱烧烤用哪个模式 方太烤箱烤红薯用哪个模式
• 

  大金空调制冷可以制热没反应 大金空调为什么加热不制冷解决步骤
• 

  湖山入映—西湖游记
• 

  石斛粉一天吃多少克为好
• 

  《LOL》IG经理透露,战队被官方针对,选手在韩服无法正常游戏,这事你怎么看？
• 

  莲子煮粥一次放几个
• 

  数据分析行业的薪酬,游戏公司数据分析工程师薪酬
• 

  原神神鹤是谁 原神神鹤雨海阵容厉害吗
• 

  ?V怎么读 汜怎么读
• 

  有没有专门抓小三的机构 专业捉小三团队多少钱
• 

  公司不证明个人可以申请工伤鉴定吗
• 

  大众辉昂的发动机是进口的吗 大众辉昂的发动机是进口的吗多少钱
• 

  八下期中语文考卷
• 

  二零小麦粉和三零面粉的区别 二零小麦粉和三零面粉的区别是什么

• 如何使用 Visual Studio Code 调试 Angular Schematics 实现
• NPOI根据模板生成chart图表导出Excel
• win7系统黑屏修好 看视频无故黑屏的修好措施
• Win7虚拟内存怎样设置最好 详细说明合理分配的技巧
• Win7系统dll动态链接库有问题的处理措施
• win7系统bioss根据不同蜂鸣警报声响判断故障的技巧
• win7系统如何自动取得ip地址 无法自动取得IP的应对措施
• win7系统外置摄像头QDI显示白板的处理办法
• win7系统更改hosts与service的迅速设置技巧