c++实现链表（c++实现链表逆转）

## C++ 实现链表### 简介链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的节点在内存中可以不连续，因此可以动态地添加或删除节点，而无需像数组那样重新分配内存。### 链表的类型链表主要分为两种类型：

单链表

: 每个节点只有一个指针，指向下一个节点。

双链表

: 每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。### C++ 单链表实现#### 1. 节点定义```c++ struct Node {int data;Node

next; }; ```这个结构体定义了链表中的单个节点。它包含两个成员：

`data`: 用于存储数据。

`next`: 指向下一个节点的指针。#### 2. 链表类定义```c++ class LinkedList {public:Node

head; // 指向链表头节点的指针LinkedList() { head = nullptr; } // 构造函数，初始化头节点为 nullptr// 在链表头部插入节点void insertAtBeginning(int data);// 在链表尾部插入节点void insertAtEnd(int data);// 在指定位置插入节点void insertAtPosition(int data, int position);// 删除链表中的节点void deleteNode(int data);// 打印链表void printList(); }; ```这个类定义了一个简单的链表，包含以下成员：

`head`: 指向链表头节点的指针。

构造函数：初始化头节点为 `nullptr`。

一系列方法：用于插入、删除、打印链表等操作。#### 3. 实现方法

3.1 插入节点

`insertAtBeginning(int data)`:

在链表头部插入一个新节点。```c++ void LinkedList::insertAtBeginning(int data) {Node

newNode = new Node;newNode->data = data;newNode->next = head;head = newNode; } ```

`insertAtEnd(int data)`:

在链表尾部插入一个新节点。```c++ void LinkedList::insertAtEnd(int data) {Node

newNode = new Node;newNode->data = data;newNode->next = nullptr;if (head == nullptr) {head = newNode;return;}Node

temp = head;while (temp->next != nullptr) {temp = temp->next;}temp->next = newNode; } ```

`insertAtPosition(int data, int position)`:

在指定位置插入一个新节点。```c++ void LinkedList::insertAtPosition(int data, int position) {if (position < 1) {return;}if (position == 1) {insertAtBeginning(data);return;}Node

newNode = new Node;newNode->data = data;newNode->next = nullptr;Node

temp = head;for (int i = 1; i < position - 1; i++) {if (temp == nullptr) {return; // 位置无效}temp = temp->next;}if (temp == nullptr) {return; // 位置无效}newNode->next = temp->next;temp->next = newNode; } ```

3.2 删除节点

`deleteNode(int data)`:

删除链表中值为 `data` 的节点。```c++ void LinkedList::deleteNode(int data) {Node

temp = head;Node

prev = nullptr;if (temp != nullptr && temp->data == data) {head = temp->next; // 删除头节点delete temp;return;}while (temp != nullptr && temp->data != data) {prev = temp;temp = temp->next;}if (temp == nullptr) {return; // 没有找到要删除的节点}prev->next = temp->next;delete temp; } ```

3.3 打印链表

`printList()`:

打印链表中所有节点的值。```c++ void LinkedList::printList() {Node

temp = head;while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl; } ```#### 4. 使用示例```c++ int main() {LinkedList list;list.insertAtEnd(1);list.insertAtBeginning(2);list.insertAtPosition(3, 2);list.printList(); // 输出: 2 3 1list.deleteNode(3);list.printList(); // 输出: 2 1return 0; } ```### C++ 双链表实现#### 1. 节点定义```c++ struct Node {int data;Node

prev;Node

next; }; ```双链表的节点包含三个成员：

`data`: 用于存储数据。

`prev`: 指向前一个节点的指针。

`next`: 指向下一个节点的指针。#### 2. 链表类定义```c++ class DoublyLinkedList {public:Node

head; // 指向链表头节点的指针Node

tail; // 指向链表尾节点的指针DoublyLinkedList() { head = nullptr; tail = nullptr; } // 构造函数// 在链表头部插入节点void insertAtBeginning(int data);// 在链表尾部插入节点void insertAtEnd(int data);// 在指定位置插入节点void insertAtPosition(int data, int position);// 删除链表中的节点void deleteNode(int data);// 打印链表void printList(); }; ```双链表类与单链表类类似，只是增加了 `tail` 指针，用于指向链表的尾节点。#### 3. 实现方法双链表的插入和删除操作与单链表略有不同，需要更新节点的 `prev` 和 `next` 指针。

3.1 插入节点

`insertAtBeginning(int data)`:

在链表头部插入一个新节点。```c++ void DoublyLinkedList::insertAtBeginning(int data) {Node

newNode = new Node;newNode->data = data;newNode->prev = nullptr;newNode->next = head;if (head != nullptr) {head->prev = newNode;}head = newNode;if (tail == nullptr) {tail = newNode; // 如果链表为空，尾节点也指向新节点} } ```

`insertAtEnd(int data)`:

在链表尾部插入一个新节点。```c++ void DoublyLinkedList::insertAtEnd(int data) {Node

newNode = new Node;newNode->data = data;newNode->next = nullptr;if (tail != nullptr) {newNode->prev = tail;tail->next = newNode;tail = newNode;} else {head = newNode;tail = newNode;newNode->prev = nullptr;} } ```

`insertAtPosition(int data, int position)`:

在指定位置插入一个新节点。```c++ void DoublyLinkedList::insertAtPosition(int data, int position) {if (position < 1) {return;}if (position == 1) {insertAtBeginning(data);return;}Node

newNode = new Node;newNode->data = data;Node

temp = head;for (int i = 1; i < position - 1; i++) {if (temp == nullptr) {return; // 位置无效}temp = temp->next;}if (temp == nullptr) {return; // 位置无效}newNode->next = temp->next;newNode->prev = temp;if (temp->next != nullptr) {temp->next->prev = newNode;}temp->next = newNode; } ```

3.2 删除节点

`deleteNode(int data)`:

删除链表中值为 `data` 的节点。```c++ void DoublyLinkedList::deleteNode(int data) {Node

temp = head;if (temp != nullptr && temp->data == data) {head = temp->next;if (head != nullptr) {head->prev = nullptr;} else {tail = nullptr; // 链表为空}delete temp;return;}while (temp != nullptr && temp->data != data) {temp = temp->next;}if (temp == nullptr) {return; // 没有找到要删除的节点}if (temp->next != nullptr) {temp->next->prev = temp->prev;} else {tail = temp->prev; // 删除尾节点}if (temp->prev != nullptr) {temp->prev->next = temp->next;}delete temp; } ```

3.3 打印链表

`printList()`:

打印链表中所有节点的值。```c++ void DoublyLinkedList::printList() {Node

temp = head;while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl; } ```#### 4. 使用示例```c++ int main() {DoublyLinkedList list;list.insertAtEnd(1);list.insertAtBeginning(2);list.insertAtPosition(3, 2);list.printList(); // 输出: 2 3 1list.deleteNode(3);list.printList(); // 输出: 2 1return 0; } ```### 总结链表是一种灵活的数据结构，适用于动态添加和删除元素的情况。单链表和双链表各有优缺点，选择哪种类型取决于实际应用场景。

单链表优点：

实现简单，占用空间小。

访问顺序线性，可以高效地遍历。

单链表缺点：

无法从当前节点直接访问前一个节点。

在链表中间插入或删除节点需要遍历到目标位置，效率较低。

双链表优点：

可以从当前节点直接访问前后两个节点。

在链表中间插入或删除节点效率更高。

双链表缺点：

实现相对复杂，占用空间比单链表大。在实际应用中，要根据具体需求选择合适的链表类型，并根据其特点进行优化。

C++ 实现链表

简介链表是一种线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的节点在内存中可以不连续，因此可以动态地添加或删除节点，而无需像数组那样重新分配内存。

链表的类型链表主要分为两种类型：* **单链表**: 每个节点只有一个指针，指向下一个节点。 * **双链表**: 每个节点有两个指针，一个指向下一个节点，另一个指向前一个节点。

C++ 单链表实现

1. 节点定义```c++ struct Node {int data;Node* next; }; ```这个结构体定义了链表中的单个节点。它包含两个成员：* `data`: 用于存储数据。 * `next`: 指向下一个节点的指针。

2. 链表类定义```c++ class LinkedList {public:Node* head; // 指向链表头节点的指针LinkedList() { head = nullptr; } // 构造函数，初始化头节点为 nullptr// 在链表头部插入节点void insertAtBeginning(int data);// 在链表尾部插入节点void insertAtEnd(int data);// 在指定位置插入节点void insertAtPosition(int data, int position);// 删除链表中的节点void deleteNode(int data);// 打印链表void printList(); }; ```这个类定义了一个简单的链表，包含以下成员：* `head`: 指向链表头节点的指针。 * 构造函数：初始化头节点为 `nullptr`。 * 一系列方法：用于插入、删除、打印链表等操作。

3. 实现方法**3.1 插入节点*** **`insertAtBeginning(int data)`:** 在链表头部插入一个新节点。```c++ void LinkedList::insertAtBeginning(int data) {Node* newNode = new Node;newNode->data = data;newNode->next = head;head = newNode; } ```* **`insertAtEnd(int data)`:** 在链表尾部插入一个新节点。```c++ void LinkedList::insertAtEnd(int data) {Node* newNode = new Node;newNode->data = data;newNode->next = nullptr;if (head == nullptr) {head = newNode;return;}Node* temp = head;while (temp->next != nullptr) {temp = temp->next;}temp->next = newNode; } ```* **`insertAtPosition(int data, int position)`:** 在指定位置插入一个新节点。```c++ void LinkedList::insertAtPosition(int data, int position) {if (position < 1) {return;}if (position == 1) {insertAtBeginning(data);return;}Node* newNode = new Node;newNode->data = data;newNode->next = nullptr;Node* temp = head;for (int i = 1; i < position - 1; i++) {if (temp == nullptr) {return; // 位置无效}temp = temp->next;}if (temp == nullptr) {return; // 位置无效}newNode->next = temp->next;temp->next = newNode; } ```**3.2 删除节点*** **`deleteNode(int data)`:** 删除链表中值为 `data` 的节点。```c++ void LinkedList::deleteNode(int data) {Node* temp = head;Node* prev = nullptr;if (temp != nullptr && temp->data == data) {head = temp->next; // 删除头节点delete temp;return;}while (temp != nullptr && temp->data != data) {prev = temp;temp = temp->next;}if (temp == nullptr) {return; // 没有找到要删除的节点}prev->next = temp->next;delete temp; } ```**3.3 打印链表*** **`printList()`:** 打印链表中所有节点的值。```c++ void LinkedList::printList() {Node* temp = head;while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl; } ```

4. 使用示例```c++ int main() {LinkedList list;list.insertAtEnd(1);list.insertAtBeginning(2);list.insertAtPosition(3, 2);list.printList(); // 输出: 2 3 1list.deleteNode(3);list.printList(); // 输出: 2 1return 0; } ```

C++ 双链表实现

1. 节点定义```c++ struct Node {int data;Node* prev;Node* next; }; ```双链表的节点包含三个成员：* `data`: 用于存储数据。 * `prev`: 指向前一个节点的指针。 * `next`: 指向下一个节点的指针。

2. 链表类定义```c++ class DoublyLinkedList {public:Node* head; // 指向链表头节点的指针Node* tail; // 指向链表尾节点的指针DoublyLinkedList() { head = nullptr; tail = nullptr; } // 构造函数// 在链表头部插入节点void insertAtBeginning(int data);// 在链表尾部插入节点void insertAtEnd(int data);// 在指定位置插入节点void insertAtPosition(int data, int position);// 删除链表中的节点void deleteNode(int data);// 打印链表void printList(); }; ```双链表类与单链表类类似，只是增加了 `tail` 指针，用于指向链表的尾节点。

3. 实现方法双链表的插入和删除操作与单链表略有不同，需要更新节点的 `prev` 和 `next` 指针。**3.1 插入节点*** **`insertAtBeginning(int data)`:** 在链表头部插入一个新节点。```c++ void DoublyLinkedList::insertAtBeginning(int data) {Node* newNode = new Node;newNode->data = data;newNode->prev = nullptr;newNode->next = head;if (head != nullptr) {head->prev = newNode;}head = newNode;if (tail == nullptr) {tail = newNode; // 如果链表为空，尾节点也指向新节点} } ```* **`insertAtEnd(int data)`:** 在链表尾部插入一个新节点。```c++ void DoublyLinkedList::insertAtEnd(int data) {Node* newNode = new Node;newNode->data = data;newNode->next = nullptr;if (tail != nullptr) {newNode->prev = tail;tail->next = newNode;tail = newNode;} else {head = newNode;tail = newNode;newNode->prev = nullptr;} } ```* **`insertAtPosition(int data, int position)`:** 在指定位置插入一个新节点。```c++ void DoublyLinkedList::insertAtPosition(int data, int position) {if (position < 1) {return;}if (position == 1) {insertAtBeginning(data);return;}Node* newNode = new Node;newNode->data = data;Node* temp = head;for (int i = 1; i < position - 1; i++) {if (temp == nullptr) {return; // 位置无效}temp = temp->next;}if (temp == nullptr) {return; // 位置无效}newNode->next = temp->next;newNode->prev = temp;if (temp->next != nullptr) {temp->next->prev = newNode;}temp->next = newNode; } ```**3.2 删除节点*** **`deleteNode(int data)`:** 删除链表中值为 `data` 的节点。```c++ void DoublyLinkedList::deleteNode(int data) {Node* temp = head;if (temp != nullptr && temp->data == data) {head = temp->next;if (head != nullptr) {head->prev = nullptr;} else {tail = nullptr; // 链表为空}delete temp;return;}while (temp != nullptr && temp->data != data) {temp = temp->next;}if (temp == nullptr) {return; // 没有找到要删除的节点}if (temp->next != nullptr) {temp->next->prev = temp->prev;} else {tail = temp->prev; // 删除尾节点}if (temp->prev != nullptr) {temp->prev->next = temp->next;}delete temp; } ```**3.3 打印链表*** **`printList()`:** 打印链表中所有节点的值。```c++ void DoublyLinkedList::printList() {Node* temp = head;while (temp != nullptr) {std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl; } ```

4. 使用示例```c++ int main() {DoublyLinkedList list;list.insertAtEnd(1);list.insertAtBeginning(2);list.insertAtPosition(3, 2);list.printList(); // 输出: 2 3 1list.deleteNode(3);list.printList(); // 输出: 2 1return 0; } ```

总结链表是一种灵活的数据结构，适用于动态添加和删除元素的情况。单链表和双链表各有优缺点，选择哪种类型取决于实际应用场景。**单链表优点：*** 实现简单，占用空间小。 * 访问顺序线性，可以高效地遍历。**单链表缺点：*** 无法从当前节点直接访问前一个节点。 * 在链表中间插入或删除节点需要遍历到目标位置，效率较低。**双链表优点：*** 可以从当前节点直接访问前后两个节点。 * 在链表中间插入或删除节点效率更高。**双链表缺点：*** 实现相对复杂，占用空间比单链表大。在实际应用中，要根据具体需求选择合适的链表类型，并根据其特点进行优化。