参考链接：
https://blog.csdn.net/Edward_Asia/article/details/120876314
链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表可以分为单链表、双链表和循环链表等。以下是链表的基本概念和操作，以及 C++ 中如何实现和使用链表。
1. 单链表
单链表是最简单的链表形式，每个节点包含一个数据域和一个指向下一个节点的指针。
节点定义
struct ListNode {
int val; // 数据域
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
基本操作
插入节点
- 在链表头部插入节点。
- 在链表尾部插入节点。
- 在链表中间插入节点。
删除节点
- 删除链表头部节点。
- 删除链表尾部节点。
- 删除链表中间节点。
遍历链表
- 从头到尾遍历链表。
查找节点
- 查找链表中是否存在某个值的节点。
2. 双链表
双链表的每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。
节点定义
struct DoublyListNode {
int val; // 数据域
DoublyListNode* prev; // 指向前一个节点的指针
DoublyListNode* next; // 指向后一个节点的指针
DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {} // 构造函数
};
基本操作
插入节点
- 在链表头部插入节点。
- 在链表尾部插入节点。
- 在链表中间插入节点。
删除节点
- 删除链表头部节点。
- 删除链表尾部节点。
- 删除链表中间节点。
遍历链表
- 从头到尾遍历链表。
- 从尾到头遍历链表。
查找节点
- 查找链表中是否存在某个值的节点。
3. 循环链表
循环链表的最后一个节点的指针指向链表的头节点，形成一个环。
节点定义
struct CircularListNode {
int val; // 数据域
CircularListNode* next; // 指向下一个节点的指针
CircularListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
基本操作
插入节点
- 在链表头部插入节点。
- 在链表尾部插入节点。
- 在链表中间插入节点。
删除节点
- 删除链表头部节点。
- 删除链表尾部节点。
- 删除链表中间节点。
遍历链表
- 从头到尾遍历链表，注意避免无限循环。
查找节点
- 查找链表中是否存在某个值的节点。
4. C++ 标准库中的链表
C++ 标准库提供了 std::list，这是一个双向链表的实现。它提供了丰富的操作接口，可以方便地进行插入、删除和遍历等操作。
示例代码
#include <iostream>
#include <list>
int main() {
std::list<int> myList;
// 插入元素
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
// 遍历链表
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;
// 删除元素
myList.pop_back();
// 再次遍历链表
for (int value : myList) {
std::cout << value << " ";
}
std::cout << std::endl;
return 0;
}
5. 单链表的实现
以下是一个简单的单链表实现，包括插入、删除和遍历操作。
代码实现
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
class LinkedList {
private:
ListNode* head;
public:
LinkedList() : head(nullptr) {}
// 插入节点到链表头部
void insertAtHead(int value) {
ListNode* newNode = new ListNode(value);
newNode->next = head;
head = newNode;
}
// 插入节点到链表尾部
void insertAtTail(int value) {
ListNode* newNode = new ListNode(value);
if (head == nullptr) {
head = newNode;
return;
}
ListNode* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
// 删除链表头部节点
void deleteAtHead() {
if (head == nullptr) return;
ListNode* temp = head;
head = head->next;
delete temp;
}
// 删除链表尾部节点
void deleteAtTail() {
if (head == nullptr) return;
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
ListNode* temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}
// 遍历链表
void print() {
ListNode* temp = head;
while (temp != nullptr) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << std::endl;
}
};
int main() {
LinkedList list;
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.print(); // 输出 1 2 3
list.insertAtTail(4);
list.insertAtTail(5);
list.print(); // 输出 1 2 3 4 5
list.deleteAtHead();
list.print(); // 输出 2 3 4 5
list.deleteAtTail();
list.print(); // 输出 2 3 4
return 0;
}
6. 总结
- 链表：一种由节点组成的线性数据结构，每个节点包含数据域和指向下一个节点的指针。
- 单链表：每个节点只有一个指针，指向下一个节点。
- 双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
- 循环链表：最后一个节点的指针指向链表的头节点，形成一个环。
std::list：C++ 标准库中的双向链表实现，提供了丰富的操作接口。