链表类（链表类型有哪些）

## 链表类

简介

链表是一种常用的数据结构，它由一系列节点组成，每个节点存储一个数据元素和指向下一个节点的指针。与数组不同，链表的节点可以分散在内存中，不需要连续的存储空间，因此在插入和删除元素时效率更高，但访问特定元素的效率较低。 链表有多种类型，例如单链表、双链表、循环链表等，本文将主要介绍单链表和双链表及其相关的操作。### 1. 单链表#### 1.1 定义单链表的每个节点包含两个部分：数据域和指针域。数据域存储数据元素，指针域存储指向下一个节点的指针。最后一个节点的指针域指向NULL（或空指针），表示链表的结尾。#### 1.2 节点结构 (C++)```c++ struct Node {int data; // 数据域，可以根据需要修改数据类型Node

next; // 指针域，指向下一个节点 }; ```#### 1.3 单链表类 (C++)```c++ class SingleLinkedList { private:Node

head; // 头指针，指向链表的第一个节点public:// 构造函数SingleLinkedList() : head(nullptr) {}// 尾部插入节点void append(int data) {Node

newNode = new Node{data, nullptr};if (head == nullptr) {head = newNode;} else {Node

current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;}}// 头部插入节点void prepend(int data) {Node

newNode = new Node{data, head};head = newNode;}// 删除节点 (按值删除，删除第一个匹配的节点)void remove(int data) {if (head == nullptr) return;if (head->data == data) {Node

temp = head;head = head->next;delete temp;return;}Node

current = head;while (current->next != nullptr && current->next->data != data) {current = current->next;}if (current->next != nullptr) {Node

temp = current->next;current->next = current->next->next;delete temp;}}// 打印链表void printList() {Node

current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}// 析构函数 (释放内存)~SingleLinkedList() {Node

current = head;while (current != nullptr) {Node

next = current->next;delete current;current = next;}} }; ```#### 1.4 单链表操作示例 (C++)```c++ #include int main() {SingleLinkedList list;list.append(1);list.append(2);list.append(3);list.prepend(0);list.printList(); // Output: 0 1 2 3list.remove(2);list.printList(); // Output: 0 1 3return 0; } ```### 2. 双链表#### 2.1 定义双链表的每个节点包含三个部分：数据域、前指针域和后指针域。数据域存储数据元素，前指针域指向其前一个节点，后指针域指向其后一个节点。#### 2.2 节点结构 (C++)```c++ struct Node {int data;Node

prev; // 前指针Node

next; // 后指针 }; ```#### 2.3 双链表类 (C++) (简化版，只包含插入和打印功能)```c++ class DoubleLinkedList { private:Node

head;Node

tail; // 尾指针public:DoubleLinkedList() : head(nullptr), tail(nullptr) {}void append(int data) {Node

newNode = new Node{data, nullptr, nullptr};if (head == nullptr) {head = tail = newNode;} else {newNode->prev = tail;tail->next = newNode;tail = newNode;}}void printList() {Node

current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}~DoubleLinkedList() {Node

current = head;while (current != nullptr) {Node

next = current->next;delete current;current = next;}} }; ```#### 2.4 双链表操作示例 (C++)```c++ #include int main() {DoubleLinkedList list;list.append(1);list.append(2);list.append(3);list.printList(); // Output: 1 2 3return 0; } ```

总结

本文简要介绍了单链表和双链表的基本概念、节点结构和部分操作。 双链表相较于单链表，在删除节点时效率更高，因为可以直接访问前一个节点。 选择哪种链表取决于具体的应用场景。 更复杂的链表操作（例如查找、排序等）可以基于以上提供的基础代码进行扩展。 记住在链表操作完成后，需要正确释放分配的内存，避免内存泄漏。 为了简明起见，代码中省略了错误处理和更全面的功能。 读者可以根据实际需求进行完善。

链表类**简介**链表是一种常用的数据结构，它由一系列节点组成，每个节点存储一个数据元素和指向下一个节点的指针。与数组不同，链表的节点可以分散在内存中，不需要连续的存储空间，因此在插入和删除元素时效率更高，但访问特定元素的效率较低。 链表有多种类型，例如单链表、双链表、循环链表等，本文将主要介绍单链表和双链表及其相关的操作。

1. 单链表

1.1 定义单链表的每个节点包含两个部分：数据域和指针域。数据域存储数据元素，指针域存储指向下一个节点的指针。最后一个节点的指针域指向NULL（或空指针），表示链表的结尾。

1.2 节点结构 (C++)```c++ struct Node {int data; // 数据域，可以根据需要修改数据类型Node *next; // 指针域，指向下一个节点 }; ```

1.3 单链表类 (C++)```c++ class SingleLinkedList { private:Node *head; // 头指针，指向链表的第一个节点public:// 构造函数SingleLinkedList() : head(nullptr) {}// 尾部插入节点void append(int data) {Node *newNode = new Node{data, nullptr};if (head == nullptr) {head = newNode;} else {Node *current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;}}// 头部插入节点void prepend(int data) {Node *newNode = new Node{data, head};head = newNode;}// 删除节点 (按值删除，删除第一个匹配的节点)void remove(int data) {if (head == nullptr) return;if (head->data == data) {Node* temp = head;head = head->next;delete temp;return;}Node *current = head;while (current->next != nullptr && current->next->data != data) {current = current->next;}if (current->next != nullptr) {Node *temp = current->next;current->next = current->next->next;delete temp;}}// 打印链表void printList() {Node *current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}// 析构函数 (释放内存)~SingleLinkedList() {Node *current = head;while (current != nullptr) {Node *next = current->next;delete current;current = next;}} }; ```

1.4 单链表操作示例 (C++)```c++

include int main() {SingleLinkedList list;list.append(1);list.append(2);list.append(3);list.prepend(0);list.printList(); // Output: 0 1 2 3list.remove(2);list.printList(); // Output: 0 1 3return 0; } ```

2. 双链表

2.1 定义双链表的每个节点包含三个部分：数据域、前指针域和后指针域。数据域存储数据元素，前指针域指向其前一个节点，后指针域指向其后一个节点。

2.2 节点结构 (C++)```c++ struct Node {int data;Node *prev; // 前指针Node *next; // 后指针 }; ```

2.3 双链表类 (C++) (简化版，只包含插入和打印功能)```c++ class DoubleLinkedList { private:Node *head;Node *tail; // 尾指针public:DoubleLinkedList() : head(nullptr), tail(nullptr) {}void append(int data) {Node* newNode = new Node{data, nullptr, nullptr};if (head == nullptr) {head = tail = newNode;} else {newNode->prev = tail;tail->next = newNode;tail = newNode;}}void printList() {Node* current = head;while (current != nullptr) {std::cout << current->data << " ";current = current->next;}std::cout << std::endl;}~DoubleLinkedList() {Node* current = head;while (current != nullptr) {Node* next = current->next;delete current;current = next;}} }; ```

2.4 双链表操作示例 (C++)```c++

include int main() {DoubleLinkedList list;list.append(1);list.append(2);list.append(3);list.printList(); // Output: 1 2 3return 0; } ```**总结**本文简要介绍了单链表和双链表的基本概念、节点结构和部分操作。 双链表相较于单链表，在删除节点时效率更高，因为可以直接访问前一个节点。 选择哪种链表取决于具体的应用场景。 更复杂的链表操作（例如查找、排序等）可以基于以上提供的基础代码进行扩展。 记住在链表操作完成后，需要正确释放分配的内存，避免内存泄漏。 为了简明起见，代码中省略了错误处理和更全面的功能。 读者可以根据实际需求进行完善。