说明
链表是数据结构中的线性结构，用于存储一系列元素（节点），其中每个元素都包含一个指向下一个元素的引用。
链表由一组节点组成，每个节点包含两个部分：数据和指向下一个节点的指针（或引用）。
线性结构中对比数组/列表的优势：插入和删除性能较好
涉及的概念：
1. 节点：节点包括2个域,元素域、链接域
2. 元素域也叫数据域：就是链表在该节点上存储的数据（元素）
3. 链接域也叫指针域：建立当前节点与前后节点的关系。比如：单链表就是当前节点存储其下个节点地址的指针。
分类
链表有多种类型，包括单链表、双链表和循环链表等。
单链表（Singly Linked List）
单链表（Singly Linked List）是一种常见的链表数据结构，它由一组节点组成，每个节点包含两部分信息：
- 数据域：存储实际的元素值。
- 指针域（或引用域）：指向下一个节点的引用或指针。
单链表的特点是每个节点只有一个指针，它指向链表中的下一个节点，而最后一个节点的指针通常为空，表示链表的结束。
单链表的第一个节点被称为头节点（Head），而最后一个节点的指针为空。链表的头节点用于表示链表的起始位置，通过头节点可以访问整个链表。
下面是一个简单的单链表示例：
[Head] -> [Node1] -> [Node2] -> [Node3] -> null
在上面的示例中，链表的头节点指向第一个节点Node1，Node1的指针指向Node2，依此类推，最后一个节点Node3的指针为空，表示链表结束。
单链表常用于需要频繁插入和删除元素的场景，因为插入和删除节点的操作相对高效。然而，它的随机访问效率较低，因为要访问特定位置的元素，必须从头节点开始遍历链表，直到达到目标节点。
特点：
单链表（Singly Linked List）是一种常见的链表数据结构，其主要特点包括以下几点：
-
节点结构：单链表由一组节点组成，每个节点包含两个部分信息：
- 数据域：用于存储实际的元素值。
- 指针域（或引用域）：指向下一个节点的引用或指针。
-
单向连接：单链表的节点之间通过指针（引用）实现单向连接。每个节点指向链表中的下一个节点，而最后一个节点的指针通常为空（null或nil），表示链表的结束。
-
头节点：单链表通常有一个头节点（Head），它是链表的第一个节点。
-
随机访问效率低：要访问单链表中的特定位置的元素，通常需要从头节点开始遍历链表，直到达到目标位置。因此，单链表的随机访问效率相对较低，时间复杂度为 O(n)，其中 n 表示链表的长度。
-
插入和删除效率高：单链表对于插入和删除节点的操作相对高效。插入节点时，只需修改相邻节点的指针，不需要移动整个链表。同样，删除节点时也只需修改相邻节点的指针。
-
动态大小：单链表的大小可以动态增长或缩小，因为节点的插入和删除操作是高效的。
-
占用内存相对较少（考虑到数组创建时就已经占用内存空间，链表是加入元素/节点才占用）：与数组相比，单链表通常占用较少的内存，因为它不需要预分配连续的内存空间。
-
适用场景：单链表通常在需要频繁插入和删除元素，而不需要频繁随机访问元素的情况下使用。
总之，单链表是一种简单但常见的数据结构，用于存储和操作一系列元素。它的主要优势在于插入和删除操作的高效性，以及动态大小的能力。然而，随机访问效率较低，因此在需要随机访问元素的情况下，数组可能更为合适。选择链表类型应根据特定需求和应用场景来决定。
双链表（Doubly Linked List）
是一种链表数据结构，与单链表相比，它的节点包含两个指针，分别指向前一个节点和后一个节点。这使得双链表在某些操作上比单链表更加灵活，但也更占用内存。
双链表节点的结构如下：
- 数据域：存储实际的元素值。
- 前驱指针（或前向指针）：指向前一个节点的引用或指针。
- 后继指针（或后向指针）：指向后一个节点的引用或指针。
下面是一个简单的双链表示例：
null <- [Head] <-> [Node1] <-> [Node2] <-> [Node3] <-> ... <-> [LastNode] <-> null
[Head]表示头节点。<-表示前驱指针。<->表示后继指针。[Node1]、[Node2]、[Node3]表示实际的数据节点。[LastNode]表示链表的最后一个节点。null表示空指针，表示链表的结束。
在上面的示例中，双链表的头节点前驱指针为空，尾节点的后继指针都为空。Node1的前驱指针为空，后继指针指向Node2，Node2的前驱指针指向Node1，后继指针指向Node3，以此类推。
双链表相对于单链表具有以下优势：
-
前向和后向遍历：双链表允许从头到尾或从尾到头轻松遍历链表，而不需要重新遍历。
-
插入和删除效率高：插入和删除节点的操作在双链表中通常比在单链表中更高效，因为不需要查找前一个节点，可以直接通过前驱和后继指针执行操作。
-
反向操作：在某些情况下，需要反向操作，双链表可以轻松满足这种需求。
然而，双链表相对于单链表也有一些缺点，其中之一是占用更多的内存，因为每个节点需要存储两个指针。此外，实现和维护双链表可能比单链表更复杂。
总之，双链表是一种灵活的数据结构，适用于需要前向和后向遍历以及高效插入和删除操作的场景。在选择链表类型时，您应该考虑您的需求以及链表的优缺点。
特点：
双链表（Doubly Linked List）是一种链表数据结构，相对于单链表具有以下主要特点：
-
双向连接：每个节点包含两个指针，一个指向前一个节点（前驱节点），一个指向后一个节点（后继节点）。这使得在双链表中可以轻松从前向后或从后向前遍历链表，而不需要重新遍历。
-
头节点和尾节点：通常，双链表有一个头节点和一个尾节点，它们分别用于表示链表的起始和结束。头节点的前驱指针为空，尾节点的后继指针为空，这样可以方便地在链表的两端插入和删除元素。
-
插入和删除效率高：双链表对于插入和删除节点的操作相对高效。插入和删除节点时，只需修改相邻节点的指针，不需要重新遍历链表。
-
随机访问效率较低：虽然双链表允许从前向后和从后向前遍历链表，但对于随机访问特定位置的元素，仍然需要从头节点或尾节点开始遍历，因此随机访问的效率相对较低，时间复杂度为 O(n)，其中 n 表示链表的长度。
-
占用内存相对较多：相对于单链表，双链表通常占用更多的内存，因为每个节点需要存储两个指针（前驱和后继指针）。
-
适用场景：双链表通常在需要频繁从前向后和从后向前遍历链表的场景中使用，以及需要在链表两端进行插入和删除操作的情况下使用。
总之，双链表是一种灵活的数据结构，它允许在链表中轻松进行前向和后向遍历，以及高效地进行插入和删除操作。但它相对于单链表占用更多的内存空间，因此在选择链表类型时，应根据特定需求和应用场景来决定。
双链表的最佳实践：
-
初始化：始终在创建双链表时初始化头节点和尾节点，并确保它们的前驱和后继指针都为空。
-
插入节点：插入节点时，更新前一个节点和后一个节点的指针（与当前节点的关系），以确保链表的正确连接。
-
删除节点：删除节点时，更新前一个节点和后一个节点的指针，以跳过要删除的节点。
-
前向和后向遍历：利用前驱和后继指针进行前向和后向遍历链表。注意在进行遍历之前检查指针是否为空，以防止访问不存在的节点。
-
注意边界情况：在操作头节点和尾节点时要格外小心，因为它们的前驱和后继指针可能为空。
循环链表（特殊的单链表）
循环链表（Circular Linked List）是一种链表数据结构，它与常规链表（单链表或双链表）不同之处在于，循环链表的最后一个节点指向链表的第一个节点，形成一个循环。这个特点使得在循环链表中可以轻松地从任何节点开始遍历整个链表。
以下是循环链表的主要特点和详细解释：
-
循环连接：循环链表的最后一个节点不是指向空（null或nil），而是指向链表的第一个节点，从而形成一个环。这种循环结构使得可以无限循环地遍历链表。
-
头节点：循环链表通常有一个头节点（Head），它是链表的第一个节点。头节点不包含实际数据，只是用于表示链表的起始位置。头节点的后继指针指向链表的第一个实际节点，而尾节点的后继指针指向头节点。
-
插入和删除效率高：与常规链表一样，循环链表对于插入和删除节点的操作相对高效。插入和删除节点时，只需修改相邻节点的指针，不需要重新遍历链表。
-
随机访问效率较低：与常规链表一样，循环链表的随机访问效率较低，因为要访问特定位置的元素，通常需要从头节点开始遍历链表。
-
应用场景：循环链表在某些特定场景中非常有用，例如循环队列（Circular Queue）和循环缓冲区（Circular Buffer）的实现。在这些场景中，需要循环使用有限的存储空间，而循环链表可以很好地满足这种需求。
特点：
-
循环连接：循环链表的最后一个节点不是指向空，而是指向链表的第一个节点，形成一个环。这使得可以轻松地在循环链表中进行循环遍历，而不需要重新遍历整个链表。
-
头节点：循环链表通常有一个头节点（Head），它是链表的第一个节点。头节点的后继指针指向链表的第二节点，而尾节点的后继指针也指向头节点，形成了循环。
-
插入和删除效率高：与常规链表一样，循环链表对于插入和删除节点的操作相对高效。插入和删除节点时，只需修改相邻节点的指针，不需要重新遍历链表。
-
随机访问效率较低：与常规链表一样，循环链表的随机访问效率相对较低，因为要访问特定位置的元素，通常需要从头节点开始遍历链表。
-
应用场景：循环链表在某些特定场景中非常有用，例如实现循环队列（Circular Queue）和循环缓冲区（Circular Buffer）。在这些场景中，需要循环使用有限的存储空间，而循环链表可以很好地满足这种需求。
-
无限循环：由于循环链表的特性，它可以被无限循环遍历，从而适用于需要连续循环访问数据的情况。
总之，循环链表是一种具有循环连接的链表数据结构，使得在链表中可以轻松进行循环遍历。它通常用于需要循环使用数据集的场景，同时具有与常规链表相似的插入和删除操作效率。选择循环链表还是常规链表应根据特定需求和应用场景来决定。
链表的优势
链表相对于数组具有一些优势：
-
动态大小：链表可以根据需要动态增长或缩小，而数组的大小是固定的。
-
插入和删除：在链表中插入或删除元素的操作通常比在数组中更高效，因为不需要移动其他元素。
-
没有预分配内存：链表不需要预分配连续内存空间，这在处理大型数据集时非常有用。
链表的最佳实践
-
选择正确的类型：选择链表类型（单链表、双链表、循环链表等）根据您的需求。不同类型的链表适用于不同的场景。
-
维护头和尾：通常，保持对链表头和尾的引用可以加速插入和删除操作。
-
避免过度使用链表：链表不适用于所有情况。在需要随机访问元素的情况下，数组通常更适合。
Javascript中的链表
单链表示例：
1 // 定义一个节点类：一个节点2个域，数据域、指针域
2 class Node {
3 constructor(data) {
4 this.data = data; // 为数据域赋值
5 this.next = null; // 指针域默认是null，等入链时根据其位置设值：1. 作为head节点，其指针域值为之前的head值。 2. 作为tail节点，其指针域值就是null。
6 }
7 }
8
9 class LinkedList {
10 constructor() {
11 this.head = null;
12 }
13
14 append(data) {
15 const newNode = new Node(data);
16 if (!this.head) {
17 this.head = newNode;
18 } else {
19 let current = this.head;
20 while (current.next) {
21 current = current.next;
22 }
23 current.next = newNode;
24 }
25 }
26
27 display() {
28 let current = this.head;
29 while (current) {
30 console.log(current.data);
31 current = current.next;
32 }
33 }
34 }
35
36 const myList = new LinkedList();
37 myList.append(1);
38 myList.append(2);
39 myList.append(3);
40
41 myList.display(); // 输出 1, 2, 3
输出：
1 2 3
双链表示例：
1 class Node {
2 constructor(data) {
3 this.data = data;
4 this.prev = null; // 前驱指针
5 this.next = null; // 后继指针
6 }
7 }
8
9 class DoublyLinkedList {
10 constructor() {
11 this.head = null;
12 this.tail = null;
13 }
14
15 // 在链表尾部添加节点
16 append(data) {
17 const newNode = new Node(data);
18 if (!this.head) { // 如果是空链，待插入的节点即是头节点，也是尾节点
19 this.head = newNode;
20 this.tail = newNode;
21 } else {
22 newNode.prev = this.tail; // 设置待插入的节点前驱指针指向尾节点
23 this.tail.next = newNode; // 当前尾节点的后继指针直线待插入节点
24 this.tail = newNode; // 将待插入节点设置为尾节点即tail变量的值为待插入节点
25 }
26 }
27
28 // 在链表头部添加节点
29 prepend(data) {
30 const newNode = new Node(data);
31 if (!this.head) { // 空链，待插入节点既是头节点也是尾节点
32 this.head = newNode;
33 this.tail = newNode;
34 } else {
35 newNode.next = this.head; // 1. 待插入节点的后继指针，指向当前头节点
36 this.head.prev = newNode; // 2. 当前头节点的前驱指针指向待插入节点
37 this.head = newNode; // 3. 更新head变量的值为待插入节点
38 }
39 }
40
41 // 删除指定节点
42 delete(data) {
43 let current = this.head;
44 while (current) {
45 if (current.data === data) { // 1. 遍历，找到待删除的节点即current节点
46 if (current === this.head) { // 2. 如果是头节点，头节点下一个节点为head变量的值
47 this.head = current.next;
48 if (this.head) { // 2.1 如果头节点不为空，则其前驱节点为null
49 this.head.prev = null;
50 }
51 } else if (current === this.tail) { // 3. 如果待删除的是尾节点
52 this.tail = current.prev; // 3.1 其前驱节点为尾节点
53 this.tail.next = null; // 3.2 要满足尾节点的特点，后继指针为null
54 } else {
55 current.prev.next = current.next; // 4. 非头非尾节点，当前节点的下一个节点作为当前节点上一个节点的后继节点
56 current.next.prev = current.prev; // 4.1 当前节点前驱节点作为当前节点下一个节点的前驱节点
57 }
58 return;
59 }
60 current = current.next;
61 }
62 }
63
64 // 打印链表元素
65 display() {
66 let current = this.head;
67 while (current) {
68 console.log(current.data);
69 current = current.next;
70 }
71 }
72 }
73
74 // 创建双链表实例
75 const myList = new DoublyLinkedList();
76
77 // 添加元素
78 myList.append(1);
79 myList.append(2);
80 myList.append(3);
81 myList.prepend(0);
82
83 // 打印链表
84 myList.display(); // 输出: 0 1 2 3
85
86 // 删除元素
87 myList.delete(2);
88
89 // 打印链表
90 myList.display(); // 输出: 0 1 3
输出：
0 1 2 3 0 1 3
循环链表示例
1 // 节点类，就是单向链表，把尾节点的后继指针指向了头节点
2 class Node {
3 constructor(data) {
4 this.data = data;
5 this.next = null; // 单向循环链表，有一个后继节点就ok了
6 }
7 }
8
9 class CircularLinkedList {
10 constructor() {
11 this.head = null; // 循环链表，要记录头，方便后面遍历、添加、删除等操作
12 }
13
14 // 在链表尾部添加节点
15 append(data) {
16 const newNode = new Node(data);
17 if (!this.head) { // 1. 如果是空链，那么当前节点就是头节点，也是尾节点，因此其后继指针指向head
18 this.head = newNode;
19 newNode.next = this.head; // 将新节点的下一个指向自身，形成循环
20 } else { // 2. 如果不是空链，从头遍历遍历找到尾节点
21 let current = this.head;
22 while (current.next !== this.head) { // 2.1 尾节点的特点就是其后继指针指向了头节点head
23 current = current.next;
24 }
25 current.next = newNode; // 3. current代表尾节点，其后继节点变成了新节点
26 newNode.next = this.head; // 4. 新节点的下一个指向头节点，形成循环
27 }
28 }
29
30 // 删除指定节点
31 delete(data) {
32 if (!this.head) { // 1. 空节点直接返回
33 return;
34 }
35 let current = this.head; // 2. 从头开始遍历，找目标节点
36 let prev = null; // 目标节点前一个节点
37
38 // 寻找要删除的节点并找到其前驱节点
39 do {
40 if (current.data === data) { // 找到目标节点
41 if (prev) { // 目标节点前一个节点，如果不为空，其后继指针指向目标节点后继指针指向的节点
42 prev.next = current.next;
43 } else {
44 // 如果要删除的是头节点，需要更新头节点
45 let temp = current;
46 while (temp.next !== this.head) { //如果当前节点不是尾节点，就遍历，让temp变成尾节点
47 temp = temp.next;
48 }
49 this.head = current.next;
50 temp.next = this.head;
51 }
52 return;
53 }
54 prev = current;
55 current = current.next;
56 } while (current !== this.head); // 遍历链表
57 }
58
59 // 打印链表元素
60 display() {
61 if (!this.head) {
62 return;
63 }
64 let current = this.head;
65 do {
66 console.log(current.data);
67 current = current.next;
68 } while (current !== this.head);
69 }
70 }
71
72 // 创建循环链表实例
73 const myList = new CircularLinkedList();
74
75 // 添加元素
76 myList.append(1);
77 myList.append(2);
78 myList.append(3);
79
80 // 打印链表
81 myList.display(); // 输出: 1 2 3 1 2 3 ...
82
83 // 删除元素
84 myList.delete(2);
85
86 // 打印链表
87 myList.display(); // 输出: 1 3 1 3 ...
输出：
1 2 3 1 3
Java语言中的链表
单链表示例
1 class Node {
2 int data;
3 Node next;
4
5 Node(int data) {
6 this.data = data;
7 this.next = null;
8 }
9 }
10
11 public class LinkedList {
12
13 private Node head;
14
15 LinkedList() {
16 this.head = null;
17 }
18
19 // 在链表头部插入元素
20 public void prepend(int data) {
21 Node newNode = new Node(data);
22 newNode.next = head;
23 head = newNode;
24 }
25
26 // 在链表尾部追加元素
27 public void append(int data) {
28 Node newNode = new Node(data);
29 if (head == null) {
30 head = newNode;
31 return;
32 }
33 Node current = head;
34 while (current.next != null) {
35 current = current.next;
36 }
37 current.next = newNode;
38 }
39
40 // 删除指定元素
41 public void delete(int data) {
42 if (head == null) {
43 return;
44 }
45 if (head.data == data) {
46 head = head.next;
47 return;
48 }
49 Node current = head;
50 while (current.next != null && current.next.data != data) {
51 current = current.next;
52 }
53 if (current.next != null) {
54 current.next = current.next.next;
55 }
56 }
57
58 // 打印链表元素
59 public void display() {
60 Node current = head;
61 while (current != null) {
62 System.out.print(current.data + " ");
63 current = current.next;
64 }
65 System.out.println();
66 }
67
68 public static void main(String[] args) {
69 LinkedList myList = new LinkedList();
70 myList.append(1);
71 myList.append(2);
72 myList.append(3);
73
74 myList.display(); // 输出: 1 2 3
75
76 myList.prepend(0);
77
78 myList.display(); // 输出: 0 1 2 3
79
80 myList.delete(2);
81
82 myList.display(); // 输出: 0 1 3
83 }
84
85 }
输出：
1 2 3 0 1 2 3 0 1 3
双向链表示例
1 //1. 节点类
2 class Node {
3 int data;
4 Node prev;
5 Node next;
6
7 Node(int data) {
8 this.data = data;
9 this.prev = null;
10 this.next = null;
11 }
12 }
13
14 public class DoublyLinkedList {
15
16 Node head;
17 Node tail;
18
19 // 在链表尾部添加节点
20 public void append(int data) {
21 Node newNode = new Node(data); // 创建节点
22 if (head == null) { // 是空链，新节点即为头节点也是尾节点
23 head = newNode;
24 tail = newNode;
25 } else {
26 newNode.prev = tail; // 当前尾节点作为新节点的前驱节点
27 tail.next = newNode; // 新节点为当前尾节点的后继节点
28 tail = newNode; // 新节点为尾节点
29 }
30 }
31
32 // 在链表头部添加节点
33 public void prepend(int data) {
34 Node newNode = new Node(data); // 1. 创建新节点
35 if (head == null) { // 2. 如果链表为空，新节点既是头也是尾节点
36 head = newNode;
37 tail = newNode;
38 } else {
39 newNode.next = head; // 3. 新节点的后继指针指向头节点
40 head.prev = newNode; // 4. 新节点作为当前头节点的后继节点
41 head = newNode; // 5. 把新节点赋值给头节点变量
42 }
43 }
44
45 // 删除指定节点
46 public void delete(int data) {
47 Node current = head; // 从头开始遍历，找到待删除节点 current
48 while (current != null) {
49 if (current.data == data) {
50 if (current == head) { // 1. 如果待删除节点是头节点
51 head = current.next; // 其下一个节点为头节点
52 if (head != null) { // 如果不为空，则其前驱节点为null
53 head.prev = null;
54 }
55 } else if (current == tail) { // 1. 如果待删除节点是尾节点
56 tail = current.prev; // 当前节点的前驱节点指向tail遍历
57 tail.next = null; // tail的后继指针指向null
58 } else {
59 current.prev.next = current.next; // 非头非尾
60 current.next.prev = current.prev;
61 }
62 return;
63 }
64 current = current.next;
65 }
66 }
67
68 // 打印链表元素
69 public void display() {
70 Node current = head;
71 while (current != null) {
72 System.out.print(current.data + " ");
73 current = current.next;
74 }
75 System.out.println();
76 }
77
78 public static void main(String[] args) {
79 DoublyLinkedList myList = new DoublyLinkedList();
80 myList.append(1);
81 myList.append(2);
82 myList.append(3);
83
84 myList.display(); // 输出: 1 2 3
85
86 myList.prepend(0);
87
88 myList.display(); // 输出: 0 1 2 3
89
90 myList.delete(2);
91
92 myList.display(); // 输出: 0 1 3
93 }
94
95 }
输出：
1 2 3 0 1 2 3 0 1 3
循环链表示例
package org.allen.data.structure.linkedlist;
/**
* 节点类
*/
class Node {
int data; // 数据域，用于存放数据
Node next; // 指针域，用于指向后继节点
public Node(int data) { // 生成器快捷键Alt + insert
this.data = data;
this.next = null;
}
}
/**
* 循环链表(单链表的特例)
*/
public class CircularLinkedList {
private Node head; // 头节点，必须要有，后面操作必须用到
// private Node tail; // 尾节点，有在尾部经常添加删除操作的需要
public CircularLinkedList() {
this.head = null;
}
/**
* 在链表尾巴添加元素
*
* @param data 节点的数据域的值
*/
public void append(int data) {
// 1. 根据数据域的值构建一个节点对象
Node newNode = new Node(data);
// 2. 判断是否空链
if (head == null) {
head = newNode; // 2.1 空链，就把待插入节点作为head
head.next = head; // 2.1 循环链特殊场景：只有head，head的后继节点执行自己
} else {
// 2.2 不是空链（没有保留尾节点），需要从头遍历，找到尾节点，然后建立尾节点与待插入元素的关系
Node current = head;
while (current.next != head) { // 尾节点的特点就是后继节点是head
current = current.next; // 切换当前节点，直到当前节点current是尾节点
}
// 2.2 建立尾节点与待插入节点的关系:当前尾节点下一个节点是待插入节点
current.next = newNode;
// 建立循环
newNode.next = head;
}
}
/**
* 打印链表元素
*/
public void display() {
// 1. 如果链表是空链，直接结束
if (head == null) {
return;
} else { // 打印
Node current = head;
do {
System.out.println(current.data + "\t");
current = current.next;
} while (current.next != head);
System.out.println(current.data); // 打印尾节点的值
}
}
public static void main(String[] args) {
CircularLinkedList myList = new CircularLinkedList();
myList.append(1);
myList.append(2);
myList.append(3);
myList.display();
}
}
输出：
1 2 3
标签：current,head,next,链表,数据结构,data,节点 From： https://www.cnblogs.com/allenxx/p/17689063.html