结合leetcode学习c++
链表比数组更易增加和删除数据，但访问速度更慢
定义
链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过“引用”相连接。
引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。
1 单向链表通常用于实现栈、队列、哈希表和图等数据结构。
栈与队列：当插入和删除操作都在链表的一端进行时，它表现的特性为先进后出，对应栈；当插入操作在链表的一端进行，删除操作在链表的另一端进行，它表现的特性为先进先出，对应队列。
哈希表：链式地址是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表中。
图：邻接表是表示图的一种常用方式，其中图的每个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连的其他顶点。
2 双向链表常用于需要快速查找前一个和后一个元素的场景。
高级数据结构：比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指向父节点的引用来实现，类似于双向链表。
浏览器历史：在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和后一个网页。双向链表的特性使得这种操作变得简单。
LRU 算法：在缓存淘汰（LRU）算法中，我们需要快速找到最近最少使用的数据，以及支持快速添加和删除节点。这时候使用双向链表就非常合适。
3 环形链表常用于需要周期性操作的场景，比如操作系统的资源调度。
时间片轮转调度算法：在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循环操作可以通过环形链表来实现。
数据缓冲区：在某些数据缓冲区的实现中，也可能会使用环形链表。比如在音频、视频播放器中，数据流可能会被分成多个缓冲块并放入一个环形链表，以便实现无缝播放。
1 c++中的单链表
在 C++ 中，单链表通常是由一系列节点组成的，每个节点包含两个部分：数据部分 (val) 和指向下一个节点的指针 (next)。
单链表结构体定义
struct SinglyListNode {int val; // 数据域，存储节点的值SinglyListNode *next; // 指针域，指向下一个节点SinglyListNode(int x) : val(x), next(NULL) {} // 构造函数，初始化节点
};
成员变量
val: 用于存储节点的值。在这个例子中，val是一个int类型的变量，但也可以是其他类型。next: 用于存储指向链表中下一个节点的指针。初始化为NULL表示这是一个新创建的节点，还没有被链接到链表中。
构造函数
SinglyListNode(int x): 这是一个构造函数，用于创建新的SinglyListNode实例。构造函数接收一个整数参数x并将其赋值给val，同时将next指针初始化为NULL。
构造函数的初始化列表
构造函数使用了初始化列表的形式来初始化成员变量：
SinglyListNode(int x) : val(x), next(NULL) {}
这里，val(x) 和 next(NULL) 分别初始化 val 和 next 成员变量。具体来说：
val(x): 将构造函数传入的参数x赋值给成员变量val。next(NULL): 将成员变量next初始化为NULL，表示这个新创建的节点目前还没有指向下一个节点。
使用示例
下面是一个简单的示例，展示了如何使用 SinglyListNode 结构体创建并操作单向链表：
#include <iostream>
using namespace std;// Definition for singly-linked list.
struct SinglyListNode {int val;SinglyListNode *next;SinglyListNode(int x) : val(x), next(NULL) {}
};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 2 3
创建多个节点并连接
/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
// 初始化各个节点
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// 构建节点之间的引用
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
总结
单链表的定义和构造函数的设计是为了方便创建和操作链表。通过这样的设计，你可以轻松地在链表中插入、删除和查找节点，同时也能够有效地管理内存，避免内存泄漏等问题。
2 双链表
/* 双向链表节点结构体 */
struct ListNode {int val; // 节点值ListNode *next; // 指向后继节点的指针ListNode *prev; // 指向前驱节点的指针ListNode(int x) : val(x), next(nullptr), prev(nullptr) {} // 构造函数
};
3 环形链表
环形链表（Circular Linked List）是一种特殊类型的链表，其中最后一个节点的指针不是指向 NULL，而是指向链表的头节点，形成一个闭环。这种结构使得遍历链表时可以从任何一个节点开始，并且在到达末尾节点后可以无缝地回到头节点。
环形链表（Circular Linked List）是一种特殊类型的链表，其中最后一个节点的指针不是指向 NULL，而是指向链表的头节点，形成一个闭环。这种结构使得遍历链表时可以从任何一个节点开始，并且在到达末尾节点后可以无缝地回到头节点。
环形链表的基本概念
环形链表的类型
环形链表可以根据节点间的连接方式分为不同的类型：
- 单向环形链表 (Singly Circular Linked List): 每个节点只包含一个指向下一个节点的指针。
- 双向环形链表 (Doubly Circular Linked List): 每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。
环形链表的操作
环形链表支持多种操作，包括但不限于：
-
插入节点:
-
删除节点:
- 删除头部节点.
- 删除尾部节点.
- 删除中间节点.
-
查找节点: 根据给定的值或索引查找对应的节点。
环形链表的优点
- 方便的遍历: 无需担心遍历到最后一个节点时如何返回头节点的问题。
- 节省空间: 对于单向环形链表，不需要额外的空间来存储尾节点的指针，因为最后一个节点直接指向头节点。
环形链表的缺点
示例代码
下面是一个使用 C++ 实现单向环形链表的简单示例：
#include <iostream>
using namespace std;// 定义节点结构
struct Node {int data;Node *next;Node(int x) : data(x), next(NULL) {}
};// 定义环形链表类
class CircularLinkedList {
public:Node *head;CircularLinkedList() : head(NULL) {}void append(int data) {Node *newNode = new Node(data);if (!head) {head = newNode;head->next = head;} else {Node *temp = head;while (temp->next != head) {temp = temp->next;}temp->next = newNode;newNode->next = head;}}void prepend(int data) {Node *newNode = new Node(data);if (!head) {head = newNode;head->next = head;} else {Node *temp = head;while (temp->next != head) {temp = temp->next;}newNode->next = head;head = newNode;temp->next = head;}}void deleteNode(int key) {if (!head) {return;}Node *prev = NULL;Node *cur = head;do {if (cur->data == key) {if (cur == head) {Node *temp = head;while (temp->next != head) {temp = temp->next;}head = cur->next;temp->next = head;} else {prev->next = cur->next;}delete cur;return;}prev = cur;cur = cur->next;} while (cur != head);}void printList() {if (!head) {cout << "Empty List" << endl;return;}Node *temp = head;do {cout << temp->data << " ";temp = temp->next;} while (temp != head);cout << endl;}
};int main() {CircularLinkedList cll;cll.append(1);cll.append(2);cll.prepend(0);cll.deleteNode(1);cll.printList();return 0;
}
输出
0 2
总结
环形链表是一种特殊类型的链表，它在最后的节点处闭合成一个环。这种结构在某些应用场景中非常有用，特别是当需要频繁遍历整个链表时。
