双向链表c++实现（c 双向链表）

双向链表是一种常见的数据结构，它由一系列节点组成，每个节点都含有指向前一个节点的指针和指向后一个节点的指针。在C语言中，我们可以使用指针来实现双向链表。

## 简介

双向链表是一种具有灵活性和高效性的数据结构，它允许在O(1)时间内对链表进行插入、删除和遍历操作。与单向链表相比，双向链表具有双向遍历的能力，因此可以方便地从前向后或从后向前遍历链表。

## 多级标题

### 结构定义和节点创建

在C语言中，我们可以通过以下方式定义双向链表的结构：

```

typedef struct Node {

int data;

struct Node* prev;

struct Node* next;

} Node;

```

每个节点包含一个整型数据以及指向前一个节点和后一个节点的指针。通过这种定义方式，我们可以轻松地创建一个双向链表节点：

```

Node* createNode(int data) {

Node* newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

newNode->prev = NULL;

newNode->next = NULL;

return newNode;

```

### 插入操作

双向链表的插入操作比较简单，我们只需修改相关节点的指针即可。假设我们要在链表中的某个节点之后插入一个新节点，代码如下：

```

void insertAfter(Node* currNode, int data) {

if (currNode == NULL) {

return;

}

Node* newNode = createNode(data);

newNode->next = currNode->next;

newNode->prev = currNode;

if (currNode->next != NULL) {

currNode->next->prev = newNode;

}

currNode->next = newNode;

```

### 删除操作

和插入操作类似，删除节点时我们也只需要修改相关节点的指针即可。假设我们要删除链表中的某个节点，代码如下：

```

void deleteNode(Node** headRef, Node* delNode) {

if (*headRef == NULL || delNode == NULL) {

return;

}

if (*headRef == delNode) {

*headRef = delNode->next;

}

if (delNode->next != NULL) {

delNode->next->prev = delNode->prev;

}

if (delNode->prev != NULL) {

delNode->prev->next = delNode->next;

}

free(delNode);

```

### 遍历操作

双向链表的遍历操作和单向链表类似，我们可以从头节点开始，依次访问每个节点的数据。代码如下：

```

void traverse(Node* head) {

if (head == NULL) {

return;

}

Node* currNode = head;

while (currNode != NULL) {

printf("%d ", currNode->data);

currNode = currNode->next;

}

```

## 内容详细说明

双向链表在C语言中的实现并不复杂。通过定义相应的结构，我们可以方便地创建节点，并通过指针修改节点的关联关系。插入和删除操作只需对相应节点的指针进行简单的修改。遍历操作则可以通过遍历每个节点，并输出节点的数据来实现。

通过双向链表，我们可以有效地实现对数据的插入、删除和遍历操作，这在很多实际应用中非常有用。在实际编程过程中，我们可以根据具体需求，结合双向链表的特点，灵活地使用它来解决问题。