链表c++（链表存储结构）

## C++链表详解### 简介链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的内存空间不必连续，这使得它在插入和删除元素方面具有更高的效率。### 链表的类型C++ 中常见的链表类型有：

单链表:

每个节点包含一个数据元素和一个指向下一个节点的指针。

双链表:

每个节点包含一个数据元素、一个指向前一个节点的指针和一个指向下一个节点的指针。

循环链表:

尾节点的指针指向头节点，形成一个环。### 单链表#### 定义节点结构体```cpp struct Node {int data;Node

next; }; ```#### 创建链表```cpp Node

createLinkedList(int arr[], int n) {Node

head = nullptr;Node

tail = nullptr;for (int i = 0; i < n; i++) {Node

newNode = new Node;newNode->data = arr[i];newNode->next = nullptr;if (head == nullptr) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}return head; } ```#### 插入节点

头部插入:

```cpp void insertAtHead(Node

headRef, int newData) {Node

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

headRef;

headRef = newNode; } ```

中间插入:

```cpp void insertAfter(Node

prevNode, int newData) {if (prevNode == nullptr) {cout << "The given previous node cannot be NULL";return;}Node

newNode = new Node;newNode->data = newData;newNode->next = prevNode->next;prevNode->next = newNode; } ```

尾部插入:

```cpp void insertAtTail(Node

headRef, int newData) {Node

newNode = new Node;newNode->data = newData;newNode->next = nullptr;if (

headRef == nullptr) {

headRef = newNode;return;}Node

last =

headRef;while (last->next != nullptr) {last = last->next;}last->next = newNode; } ```#### 删除节点```cpp void deleteNode(Node

headRef, int key) {Node

temp =

headRef,

prev = nullptr;if (temp != nullptr && temp->data == key) {

headRef = 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; } ```#### 遍历链表```cpp void printList(Node

node) {while (node != nullptr) {cout << node->data << " ";node = node->next;} } ```### 双链表双链表与单链表类似，但每个节点还包含一个指向前一个节点的指针。#### 定义节点结构体```cpp struct Node {int data;Node

prev;Node

next; }; ```#### 双链表的操作双链表的操作与单链表类似，但在插入和删除节点时需要同时更新两个指针。### 循环链表循环链表是尾节点指向头节点的链表。#### 循环链表的操作循环链表的操作与单链表类似，但需要注意边界条件。### 总结链表是一种灵活的数据结构，它在插入和删除元素方面具有优势。C++ 提供了多种链表类型，可以根据实际需求选择合适的类型。

C++链表详解

简介链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表的内存空间不必连续，这使得它在插入和删除元素方面具有更高的效率。

链表的类型C++ 中常见的链表类型有：* **单链表:** 每个节点包含一个数据元素和一个指向下一个节点的指针。 * **双链表:** 每个节点包含一个数据元素、一个指向前一个节点的指针和一个指向下一个节点的指针。 * **循环链表:** 尾节点的指针指向头节点，形成一个环。

单链表

定义节点结构体```cpp struct Node {int data;Node* next; }; ```

创建链表```cpp Node* createLinkedList(int arr[], int n) {Node* head = nullptr;Node* tail = nullptr;for (int i = 0; i < n; i++) {Node* newNode = new Node;newNode->data = arr[i];newNode->next = nullptr;if (head == nullptr) {head = newNode;tail = newNode;} else {tail->next = newNode;tail = newNode;}}return head; } ```

插入节点* **头部插入:**```cpp void insertAtHead(Node** headRef, int newData) {Node* newNode = new Node;newNode->data = newData;newNode->next = *headRef;*headRef = newNode; } ```* **中间插入:**```cpp void insertAfter(Node* prevNode, int newData) {if (prevNode == nullptr) {cout << "The given previous node cannot be NULL";return;}Node* newNode = new Node;newNode->data = newData;newNode->next = prevNode->next;prevNode->next = newNode; } ```* **尾部插入:**```cpp void insertAtTail(Node** headRef, int newData) {Node* newNode = new Node;newNode->data = newData;newNode->next = nullptr;if (*headRef == nullptr) {*headRef = newNode;return;}Node* last = *headRef;while (last->next != nullptr) {last = last->next;}last->next = newNode; } ```

删除节点```cpp void deleteNode(Node** headRef, int key) {Node* temp = *headRef, *prev = nullptr;if (temp != nullptr && temp->data == key) {*headRef = 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; } ```

遍历链表```cpp void printList(Node* node) {while (node != nullptr) {cout << node->data << " ";node = node->next;} } ```

双链表双链表与单链表类似，但每个节点还包含一个指向前一个节点的指针。

定义节点结构体```cpp struct Node {int data;Node* prev;Node* next; }; ```

双链表的操作双链表的操作与单链表类似，但在插入和删除节点时需要同时更新两个指针。

循环链表循环链表是尾节点指向头节点的链表。

循环链表的操作循环链表的操作与单链表类似，但需要注意边界条件。

总结链表是一种灵活的数据结构，它在插入和删除元素方面具有优势。C++ 提供了多种链表类型，可以根据实际需求选择合适的类型。