c++ 链表详细介绍
链表是数据结构的一种，由节点组成，每个节点包含数据和指向下一个节点的指针。链表在C++中的实现可以是单链表、双链表或循环链表。以下是链表的详细介绍：
1. 单链表
结构：
- 节点（Node）：每个节点包含数据和一个指针（
next），指向链表中的下一个节点。
示例结构：
struct Node {int data;Node* next;Node(int d) : data(d), next(nullptr) {}
};
操作：
- 插入：在链表头部、尾部或中间插入新节点。
- 删除：从链表中删除指定节点。
- 遍历：从头到尾访问链表中的每个节点。
- 查找：在链表中查找指定值的节点。
2. 双链表
结构：
- 节点（Node）：每个节点包含数据、一个指针（
next）指向下一个节点，和一个指针（prev）指向前一个节点。
示例结构：
struct Node {int data;Node* next;Node* prev;Node(int d) : data(d), next(nullptr), prev(nullptr) {}
};
操作：
- 插入：可以在任意位置插入新节点，同时更新前驱和后继指针。
- 删除：从链表中删除指定节点，并调整前驱和后继指针。
- 遍历：可以从头到尾或从尾到头访问节点。
3. 循环链表
单循环链表：
- 结构：链表的最后一个节点指向头节点，形成一个循环。
双循环链表：
- 结构：结合了双链表和循环链表的特点，最后一个节点指向头节点，头节点的前驱指向最后一个节点。
操作：
- 插入和删除：类似于单链表和双链表，但需要注意循环结构的维护。
- 遍历：遍历链表时需要避免无限循环。
优缺点
优点：
- 动态大小：链表的大小可以在运行时调整。
- 插入和删除：在已知节点的情况下，插入和删除操作比数组更高效。
缺点：
- 额外内存：每个节点需要额外的指针存储。
- 访问速度：访问链表的元素通常比数组慢，因为需要从头部开始逐个遍历。
示例代码（单链表基本操作）
插入节点：
void insertAtHead(Node*& head, int data) {Node* newNode = new Node(data);newNode->next = head;head = newNode;
}
删除节点：
void deleteNode(Node*& head, int key) {Node* temp = head;Node* prev = nullptr;if (temp != nullptr && temp->data == key) {head = temp->next;delete temp;return;}while (temp != nullptr && temp->data != key) {prev = temp;temp = temp->next;}if (temp == nullptr) return;prev->next = temp->next;delete temp;
}
遍历链表：
void printList(Node* head) {Node* temp = head;while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl;
}
链表是一种灵活的动态数据结构，适用于需要频繁插入和删除操作的场景。