链表存储结构

!!! note 目录

链表存储结构

一、链表的分类

  1. 单向链表（Singly Linked List）：
  • 每个节点包含一个数据域和一个指向下一个节点的指针。
  • 只可以从头节点遍历到尾节点，不能反向遍历。
  1. 双向链表（Doubly Linked List）：
  • 每个节点包含一个数据域、一个指向下一个节点的指针和一个指向前一个节点的指针。
  • 可以在链表中双向遍历，即可以从头节点遍历到尾节点，也可以从尾节点遍历到头节点。
  1. 循环链表（Circular Linked List）：
    1. 单向循环链表（Singly Circular Linked List）：
      • 类似于单向链表，但尾节点指向头节点，形成一个环。
      • 可以从任意节点开始遍历，并回到起点。
    2. 双向循环链表（Doubly Circular Linked List）：
      • 类似于双向链表，但尾节点指向头节点，形成一个环。
      • 同样可以从任意节点开始遍历，并回到起点。

二、链表的存储结构

2.1 单向链表

1
2
3
4
5
6
+-------------------+
| int val           |    // 节点的值
+-------------------+
| struct ListNode*  |    // 指向下一个节点的指针
| next              |
+-------------------+
  • val 是存储在节点中的整数值。
  • next 是一个指针，指向链表中的下一个节点。如果这是链表的最后一个节点，则 next 指向 NULL。
1
head -> [1 | next] -> [2 | next] -> [3 | next] -> [4 | next] -> null
  • head 是链表的起始节点。
  • 每个节点的格式是 [val | next]，其中 val 是节点存储的数据，next 是指向下一个节点的指针。
  • 节点1存储值1，节点2存储值2，以此类推。
  • 最后一个节点的 next 指向 null，表示链表的结束。

2.2 双向链表

1
2
3
4
5
6
7
8
9
+-------------------+
| int val           |    // 节点的值
+-------------------+
| struct DListNode* |    // 指向前一个节点的指针
| prev              |
+-------------------+
| struct DListNode* |    // 指向下一个节点的指针
| next              |
+-------------------+
  • val 存储节点的数据。
  • prev 是一个指针，指向链表中的前一个节点。如果这是链表的第一个节点，则 prev 指向 NULL。
  • next 是一个指针，指向链表中的下一个节点。如果这是链表的最后一个节点，则 next 指向 NULL。
1
head <-> [1 | prev] <-> [2 | prev] <-> [3 | prev] <-> [4 | prev] <-> null
  • head 是链表的起始节点。
  • 每个方括号 [val | prev | next] 表示一个双向链表的节点：
  • 最后一个节点（节点4）的 next 指针指向 null，表示链表的结束。
  • 每个箭头 <-> 表示双向的链接，使得可以从一个节点到达前一个节点和后一个节点。

2.3单向循环链表

1
2
3
4
5
6
+-------------------+
| int val           |    // 节点的值
+-------------------+
| struct ListNode*  |    // 指向下一个节点的指针
| next              |
+-------------------+
1
head -> [1 | next] -> [2 | next] -> [3 | next] -> [4 | next] -> head
  • head 是链表的起始节点。
  • 每个方括号 [val | next] 代表一个节点，其中 val 是节点存储的值，next 是指向下一个节点的指针。
  • 链表的最后一个节点的 next 指针指向 head，形成一个循环。
  • 这种结构允许链表在不需要特定终点的情况下循环遍历。

2.4 双向循环链表

1
2
3
4
5
6
7
8
9
+-------------------+
| int val           |    // 节点的值
+-------------------+
| struct DListNode* |    // 指向前一个节点的指针
| prev              |
+-------------------+
| struct DListNode* |    // 指向下一个节点的指针
| next              |
+-------------------+
1
head <-> [1 | prev: 4, next: 2] <-> [2 | prev: 1, next: 3] <-> [3 | prev: 2, next: 4] <-> [4 | prev: 3, next: 1] <-> head
  • head 是链表的起始节点。
  • 每个方括号 [val | prev, next] 代表一个节点，其中 val 是节点的值，prev 是指向前一个节点的指针，next 是指向下一个节点的指针。
  • 链表的最后一个节点（节点4）的 next 指针指向 head，形成一个循环。
  • 这种结构允许在链表的两端进行遍历，同时形成一个循环链表，可以在循环中反复遍历所有节点。