共计 10326 个字符，预计需要花费 26 分钟才能阅读完成。
GitHub 源码分享
我的项目主页：https://github.com/gozhuyinglong/blog-demos
本文源码：https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures/src/main/java/com/github/gozhuyinglong/datastructures/linkedlist
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 = 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='" + value + '\'' +
'}';
}
}
}输入后果：
----------- 增加节点（尾部）Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 获取某个节点
Node{key=3, value='李四'}
----------- 移除节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=5, value='赵六'}
----------- 批改节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=5, value='赵六 2'}
----------- 按程序增加节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=4, value='王朝'}
Node{key=5, value='赵六 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类存储双链表的一个节点，DoublyLinkedListDemo类实现双链表的所有操作方法。DoublyLinkedListDemo类应用不带头节点的形式实现，其中 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 = 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='" + value + '\'' +
'}';
}
}
}输入后果：
----------- 从尾部增加节点
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 从头部增加节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=3, value='李四'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 获取某个节点
Node{key=3, value='李四'}
----------- 移除节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=7, value='王五'}
Node{key=5, value='赵六'}
----------- 批改节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=7, value='王五'}
Node{key=5, value='赵六 2'}
----------- 按程序增加节点
Node{key=0, value='朱开山'}
Node{key=1, value='张三'}
Node{key=4, value='王朝'}
Node{key=7, value='王五'}
Node{key=5, value='赵六 2'}5. 环形链表（Circular Linked List）
环形链表又叫循环链表，本文讲述的是环形单向链表，其与单链表的惟一区别是尾部节点的 next 不再为空，则是指向了头部节点，这样便造成了一个环。
环形链表的构造如下图：
5.1 约瑟夫问题
约瑟夫问题：有时也称为约瑟夫斯置换，是一个计算机科学和数学中的问题。在计算机编程的算法中，相似问题又称为约瑟夫环。又称“丢手绢问题”。
引自百度百科：
据说驰名犹太历史学家 Josephus 有过以下的故事：在罗马人霸占乔塔帕特后，39 个犹太人与 Josephus 及他的敌人躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个他杀形式，41 集体排成一个圆圈，由第 1 集体开始报数，每报数到第 3 人该人就必须他杀，而后再由下一个从新报数，直到所有人都自杀身亡为止。然而 Josephus 和他的敌人并不想听从。首先从一个人开始，越过 k - 2 集体（因为第一个人曾经被越过），并杀掉第 k 集体。接着，再越过 k - 1 集体，并杀掉第 k 集体。这个过程沿着圆圈始终进行，直到最终只剩下一个人留下，这个人就能够持续活着。问题是，给定了和，一开始要站在什么中央能力防止被处决。Josephus 要他的敌人先伪装听从，他将敌人与本人安顿在第 16 个与第 31 个地位，于是逃过了这场死亡游戏。
17 世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15 个教徒和 15 个非教徒在深海上脱险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个方法：30 集体围成一圆圈，从第一个人开始顺次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余 15 集体为止。问怎么排法，能力使每次投入大海的都是非教徒。
问题剖析与算法设计
约瑟夫问题并不难，但求解的办法很多；题目的变动模式也很多。这里给出一种实现办法。
题目中 30 集体围成一圈，因此启发咱们用一个循环的链来示意，能够应用构造数组来形成一个循环链。构造中有两个成员，其一为指向下一个人的指针，以形成环形的链；其二为该人是否被扔下海的标记，为 1 示意还在船上。从第一个人开始对还未扔下海的人进行计数，每数到 9 时，将构造中的标记改为 0，示意该人已被扔下海了。这样循环计数直到有 15 集体被扔下海为止。
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 个节点
1 2 3 4 5 6 7 8 9 10
----------- 按约瑟夫问题程序出列
3 6 9 2 7 1 8 5 10 4