双向链表的基本操作（双向链表的基本操作王道）

# 双向链表的基本操作## 简介双向链表是一种链式数据结构，每个节点除了存储数据外，还包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。这使得可以从任意节点向两个方向遍历链表，相较于单向链表，它在某些操作上效率更高。本文将详细介绍双向链表的基本操作，包括创建、插入、删除、查找等。## 一、 双向链表节点结构在开始讲解操作之前，我们先定义双向链表节点的结构体（以C++为例）：```cpp struct Node {int data; // 数据域Node

prev; // 指向前一个节点的指针Node

next; // 指向下一个节点的指针Node(int data) : data(data), prev(nullptr), next(nullptr) {} // 构造函数 }; ```这个结构体包含数据域`data`，以及指向前一个节点和下一个节点的指针 `prev` 和 `next`。构造函数方便我们创建节点。## 二、 基本操作详解### 2.1 创建双向链表创建空链表很简单，只需要创建一个头节点 (head) 指针，并将其初始化为 `nullptr`。```cpp Node

head = nullptr; // 创建空链表 ```后续操作都基于这个 `head` 指针进行。### 2.2 在链表头部插入节点在链表头部插入节点操作需要修改头结点的指针，以及新节点的 `prev` 和 `next` 指针。```cpp void insertAtHead(Node

& head, int data) {Node

newNode = new Node(data);if (head == nullptr) {head = newNode;} else {newNode->next = head;head->prev = newNode;head = newNode;} } ```这个函数接收头指针的引用 (`Node

& head`)，以便修改其值。 `head == nullptr` 的判断处理了空链表的情况。### 2.3 在链表尾部插入节点在链表尾部插入节点需要遍历链表找到最后一个节点，然后修改最后一个节点的 `next` 指针和新节点的 `prev` 指针。```cpp void insertAtTail(Node

& head, int data) {Node

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

temp = head;while (temp->next != nullptr) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;} } ```### 2.4 在指定位置插入节点在指定位置插入节点需要找到插入位置的前一个节点，然后修改指针。假设我们想在节点 `key` 之后插入新节点。```cpp void insertAfter(Node

& head, int key, int data) {Node

newNode = new Node(data);Node

temp = head;while (temp != nullptr && temp->data != key) {temp = temp->next;}if (temp == nullptr) {return; // key 不存在}newNode->next = temp->next;newNode->prev = temp;if (temp->next != nullptr) {temp->next->prev = newNode;}temp->next = newNode; } ```### 2.5 删除节点删除节点需要找到要删除节点的前一个节点，然后修改指针。这里以删除值为 `key` 的节点为例。```cpp void deleteNode(Node

& head, int key) {Node

temp = head;while (temp != nullptr && temp->data != key) {temp = temp->next;}if (temp == nullptr) {return; // key 不存在}if (temp->prev != nullptr) {temp->prev->next = temp->next;} else {head = temp->next; // 删除的是头节点}if (temp->next != nullptr) {temp->next->prev = temp->prev;}delete temp; } ```### 2.6 查找节点查找值为 `key` 的节点，返回其指针。```cpp Node

findNode(Node

head, int key) {Node

temp = head;while (temp != nullptr && temp->data != key) {temp = temp->next;}return temp; } ```## 三、 总结双向链表的基本操作相对单向链表来说复杂一些，但它允许双向遍历，这在某些应用场景下效率更高。 理解指针操作是掌握双向链表的关键。 记住在操作过程中，要仔细处理各种边界条件，例如空链表、删除头节点或尾节点等情况。 以上代码仅供参考，实际应用中可能需要根据具体需求进行修改和完善。 例如，添加错误处理和内存管理机制等。

双向链表的基本操作

简介双向链表是一种链式数据结构，每个节点除了存储数据外，还包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。这使得可以从任意节点向两个方向遍历链表，相较于单向链表，它在某些操作上效率更高。本文将详细介绍双向链表的基本操作，包括创建、插入、删除、查找等。

一、 双向链表节点结构在开始讲解操作之前，我们先定义双向链表节点的结构体（以C++为例）：```cpp struct Node {int data; // 数据域Node *prev; // 指向前一个节点的指针Node *next; // 指向下一个节点的指针Node(int data) : data(data), prev(nullptr), next(nullptr) {} // 构造函数 }; ```这个结构体包含数据域`data`，以及指向前一个节点和下一个节点的指针 `prev` 和 `next`。构造函数方便我们创建节点。

二、 基本操作详解

2.1 创建双向链表创建空链表很简单，只需要创建一个头节点 (head) 指针，并将其初始化为 `nullptr`。```cpp Node* head = nullptr; // 创建空链表 ```后续操作都基于这个 `head` 指针进行。

2.2 在链表头部插入节点在链表头部插入节点操作需要修改头结点的指针，以及新节点的 `prev` 和 `next` 指针。```cpp void insertAtHead(Node*& head, int data) {Node* newNode = new Node(data);if (head == nullptr) {head = newNode;} else {newNode->next = head;head->prev = newNode;head = newNode;} } ```这个函数接收头指针的引用 (`Node*& head`)，以便修改其值。 `head == nullptr` 的判断处理了空链表的情况。

2.3 在链表尾部插入节点在链表尾部插入节点需要遍历链表找到最后一个节点，然后修改最后一个节点的 `next` 指针和新节点的 `prev` 指针。```cpp void insertAtTail(Node*& head, int data) {Node* newNode = new Node(data);if (head == nullptr) {head = newNode;} else {Node* temp = head;while (temp->next != nullptr) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;} } ```

2.4 在指定位置插入节点在指定位置插入节点需要找到插入位置的前一个节点，然后修改指针。假设我们想在节点 `key` 之后插入新节点。```cpp void insertAfter(Node*& head, int key, int data) {Node* newNode = new Node(data);Node* temp = head;while (temp != nullptr && temp->data != key) {temp = temp->next;}if (temp == nullptr) {return; // key 不存在}newNode->next = temp->next;newNode->prev = temp;if (temp->next != nullptr) {temp->next->prev = newNode;}temp->next = newNode; } ```

2.5 删除节点删除节点需要找到要删除节点的前一个节点，然后修改指针。这里以删除值为 `key` 的节点为例。```cpp void deleteNode(Node*& head, int key) {Node* temp = head;while (temp != nullptr && temp->data != key) {temp = temp->next;}if (temp == nullptr) {return; // key 不存在}if (temp->prev != nullptr) {temp->prev->next = temp->next;} else {head = temp->next; // 删除的是头节点}if (temp->next != nullptr) {temp->next->prev = temp->prev;}delete temp; } ```

2.6 查找节点查找值为 `key` 的节点，返回其指针。```cpp Node* findNode(Node* head, int key) {Node* temp = head;while (temp != nullptr && temp->data != key) {temp = temp->next;}return temp; } ```

三、 总结双向链表的基本操作相对单向链表来说复杂一些，但它允许双向遍历，这在某些应用场景下效率更高。 理解指针操作是掌握双向链表的关键。 记住在操作过程中，要仔细处理各种边界条件，例如空链表、删除头节点或尾节点等情况。 以上代码仅供参考，实际应用中可能需要根据具体需求进行修改和完善。 例如，添加错误处理和内存管理机制等。