数据结构-链表-第二天

结合leetcode学习c++
链表比数组更易增加和删除数据，但访问速度更慢

  定义

1. 链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。
2. 引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

复制代码

1 单向链表通常用于实现栈、队列、哈希表和图等数据结构。

栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
哈希表：链式地址是解决哈希辩论的主流方案之一，在该方案中，所有辩论的元素都会被放到一个链表中。
图：毗邻表是表示图的一种常用方式，此中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。
2 双向链表常用于需要快速查找前一个和后一个元素的场景。

高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
欣赏器历史：在网页欣赏器中，当用户点击前进或后退按钮时，欣赏器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU 算法：在缓存镌汰（LRU）算法中，我们需要快速找到迩来最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
3 环形链表常用于需要周期性操作的场景，比如操作体系的资源调度。

时间片轮转调度算法：在操作体系中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区：在某些数据缓冲区的实现中，也大概会使用环形链表。比如在音频、视频播放器中，数据流大概会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。
1 c++中的单链表

在 C++ 中，单链表通常是由一系列节点组成的，每个节点包含两个部门：数据部门 (val) 和指向下一个节点的指针 (next)。
单链表结构体定义

1. struct SinglyListNode {
2.     int val;       // 数据域，存储节点的值
3.     SinglyListNode *next; // 指针域，指向下一个节点
4.     SinglyListNode(int x) : val(x), next(NULL) {}
5. // 构造函数，初始化节点
6. };

复制代码

成员变量

• val: 用于存储节点的值。在这个例子中，val 是一个 int 范例的变量，但也可以是其他范例。
  
• next: 用于存储指向链表中下一个节点的指针。初始化为 NULL 表示这是一个新创建的节点，还没有被链接到链表中。
  

构造函数

• SinglyListNode(int x): 这是一个构造函数，用于创建新的 SinglyListNode 实例。构造函数接收一个整数参数 x 并将其赋值给 val，同时将 next 指针初始化为 NULL。
  

构造函数的初始化列表

构造函数使用了初始化列表的情势来初始化成员变量：

1. SinglyListNode(int x) : val(x), next(NULL) {}

复制代码

这里，val(x) 和 next(NULL) 分别初始化 val 和 next 成员变量。详细来说：

• val(x): 将构造函数传入的参数 x 赋值给成员变量 val。
  
• next(NULL): 将成员变量 next 初始化为 NULL，表示这个新创建的节点目前还没有指向下一个节点。
  

使用示例

下面是一个简单的示例，展示了怎样使用 SinglyListNode 结构体创建并操作单向链表：

1. #include <iostream>using namespace std;// Definition for singly-linked list.struct SinglyListNode {    int val;    SinglyListNode *next;    SinglyListNode(int x) : val(x), next(NULL) {}
2. };int main() {    // 创建链表    SinglyListNode *head = new SinglyListNode(1); // 创建第一个节点    head->next = new SinglyListNode(2);           // 创建第二个节点并连接    head->next->next = new SinglyListNode(3);     // 创建第三个节点并连接    // 打印链表中的值    SinglyListNode *current = head;    while (current != NULL) {        cout << current->val << " ";        current = current->next;    }    // 释放内存    while (head != NULL) {        SinglyListNode *temp = head;        head = head->next;        delete temp;    }    return 0;}

复制代码

输出

1. 1 2 3

复制代码

创建多个节点并连接

1. /* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
2. // 初始化各个节点
3. ListNode* n0 = new ListNode(1);
4. ListNode* n1 = new ListNode(3);
5. ListNode* n2 = new ListNode(2);
6. ListNode* n3 = new ListNode(5);
7. ListNode* n4 = new ListNode(4);
8. // 构建节点之间的引用
9. n0->next = n1;
10. n1->next = n2;
11. n2->next = n3;
12. n3->next = n4;

复制代码

总结

单链表的定义和构造函数的设计是为了方便创建和操作链表。通过这样的设计，你可以轻松地在链表中插入、删除和查找节点，同时也可以大概有效地管理内存，制止内存走漏等问题。
2 双链表

1. /* 双向链表节点结构体 */
2. struct ListNode {
3.     int val;         // 节点值
4.     ListNode *next;  // 指向后继节点的指针
5.     ListNode *prev;  // 指向前驱节点的指针
6.     ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // 构造函数
7. };

复制代码

3 环形链表

环形链表（Circular Linked List）是一种特殊范例的链表，此中最后一个节点的指针不是指向 NULL，而是指向链表的头节点，形成一个闭环。这种结构使得遍历链表时可以从任何一个节点开始，而且在到达末尾节点后可以无缝地回到头节点。
环形链表（Circular Linked List）是一种特殊范例的链表，此中最后一个节点的指针不是指向 NULL，而是指向链表的头节点，形成一个闭环。这种结构使得遍历链表时可以从任何一个节点开始，而且在到达末尾节点后可以无缝地回到头节点。
环形链表的基本概念

• 节点: 环形链表中的每个节点包含数据和一个指向下一个节点的指针。
  
• 头节点 (Head): 链表的第一个节点，通常用来标识整个链表的开始。
  
• 尾节点 (Tail): 链表的最后一个节点，其指针指向头节点。
  

环形链表的范例

环形链表可以根据节点间的连接方式分为差异的范例：

• 单向环形链表 (Singly Circular Linked List): 每个节点只包含一个指向下一个节点的指针。
  
• 双向环形链表 (Doubly Circular Linked List): 每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。
  

环形链表的操作

环形链表支持多种操作，包括但不限于：

• 插入节点:
  
  
  
  • 头部插入: 在链表的头部添加一个新节点。
    
  • 尾部插入: 在链表的尾部添加一个新节点。
    
  • 中间插入: 在指定位置插入一个新节点。
    
  
  
• 删除节点:
  
  
  
  • 删除头部节点.
    
  • 删除尾部节点.
    
  • 删除中间节点.
    
  
  
• 查找节点: 根据给定的值或索引查找对应的节点。
  
• 遍历链表: 由于链表形成闭环，可以方便地从恣意节点开始遍历整个链表。
  

环形链表的优点

• 方便的遍历: 无需担心遍历到最后一个节点时怎样返回头节点的问题。
  
• 节省空间: 对于单向环形链表，不需要额外的空间来存储尾节点的指针，由于最后一个节点直接指向头节点。
  

环形链表的缺点

• 检测环形: 对于外部用户来说，需要额外的逻辑来确定链表是否已经遍历完整个环。
  
• 额外的复杂性: 与普通链表相比，环形链表的插入和删除操作大概需要更多的指针更新。
  

示例代码

下面是一个使用 C++ 实现单向环形链表的简单示例：

1. #include <iostream>
2. using namespace std;
4. // 定义节点结构
5. struct Node {
6.     int data;
7.     Node *next;
9.     Node(int x) : data(x), next(NULL) {}
10. };
12. // 定义环形链表类
13. class CircularLinkedList {
14. public:
15.     Node *head;
17.     CircularLinkedList() : head(NULL) {}
19.     void append(int data) {
20.         Node *newNode = new Node(data);
22.         if (!head) {
23.             head = newNode;
24.             head->next = head;
25.         } else {
26.             Node *temp = head;
27.             while (temp->next != head) {
28.                 temp = temp->next;
29.             }
30.             temp->next = newNode;
31.             newNode->next = head;
32.         }
33.     }
35.     void prepend(int data) {
36.         Node *newNode = new Node(data);
37.         if (!head) {
38.             head = newNode;
39.             head->next = head;
40.         } else {
41.             Node *temp = head;
42.             while (temp->next != head) {
43.                 temp = temp->next;
44.             }
45.             newNode->next = head;
46.             head = newNode;
47.             temp->next = head;
48.         }
49.     }
51.     void deleteNode(int key) {
52.         if (!head) {
53.             return;
54.         }
56.         Node *prev = NULL;
57.         Node *cur = head;
59.         do {
60.             if (cur->data == key) {
61.                 if (cur == head) {
62.                     Node *temp = head;
63.                     while (temp->next != head) {
64.                         temp = temp->next;
65.                     }
66.                     head = cur->next;
67.                     temp->next = head;
68.                 } else {
69.                     prev->next = cur->next;
70.                 }
71.                 delete cur;
72.                 return;
73.             }
74.             prev = cur;
75.             cur = cur->next;
76.         } while (cur != head);
77.     }
79.     void printList() {
80.         if (!head) {
81.             cout << "Empty List" << endl;
82.             return;
83.         }
84.         Node *temp = head;
85.         do {
86.             cout << temp->data << " ";
87.             temp = temp->next;
88.         } while (temp != head);
89.         cout << endl;
90.     }
91. };
93. int main() {
94.     CircularLinkedList cll;
95.     cll.append(1);
96.     cll.append(2);
97.     cll.prepend(0);
98.     cll.deleteNode(1);
99.     cll.printList();
101.     return 0;
102. }

复制代码

输出

1. 0 2

复制代码

总结

环形链表是一种特殊范例的链表，它在最后的节点处闭合成一个环。这种结构在某些应用场景中非常有效，特殊是当需要频繁遍历整个链表时。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。