双链表的基本操作讲解

双向链表是一种常用的数据结构，也是程序员们经常要学习和掌握的基本操作之一。下面将从多个角度对双向链表的基本操作进行讲解。

一、什么是双向链表？

双向链表是指在链表的基础上，每个节点除了储存指向下一个节点的指针之外，还储存指向前一个节点的指针。这样就可以在需要查询某个节点的前驱节点时，只需要通过该节点的指针就可以找到其前驱节点，而不需要从头开始遍历链表。

二、双向链表的基本结构

在C语言中，双向链表的基本结构可以定义如下：

```

typedef struct doublyListNode{

int val;

struct doublyListNode *prev;

struct doublyListNode *next;

} DoublyListNode;

```

其中，`val`表示节点的值，`prev`表示指向前一个节点的指针，`next`表示指向后一个节点的指针。

三、双向链表的基本操作

双向链表与单向链表相比，多了指向前一个节点的指针，因此它所涉及的基本操作也与单向链表不同。下面将讲解几个常用的双向链表操作。

1. 初始化操作

初始化一个双向链表时，需要先将头节点的指针初始化为NULL。代码如下：

```

DoublyListNode* initDoublyLinkedList() {

DoublyListNode *head;

head = (DoublyListNode*)malloc(sizeof(DoublyListNode));

head->prev = NULL;

head->next = NULL;

return head;

}

```

2. 在链表尾部插入节点

在双向链表的尾部插入一个节点时，需要先找到链表的最后一个节点，然后再将新节点插入到最后一个节点的后面即可。代码如下：

```

void add_node(DoublyListNode *head, int val) {

DoublyListNode *cur, *new_node;

new_node = (DoublyListNode*)malloc(sizeof(DoublyListNode));

new_node->val = val;

cur = head;

while(cur->next != NULL) {

cur = cur->next; //找到链表的最后一个节点

}

new_node->prev = cur;

new_node->next = NULL;

cur->next = new_node;

}

```

3. 删除节点

在双向链表中删除一个节点时，需要将该节点从链表中剥离，并将其前驱节点和后继节点相连。代码如下：

```

void delete_node(DoublyListNode *head, DoublyListNode *node) {

if(node == NULL || head == NULL) {

return;

}

if(node == head) {

head = head->next; //如果删除的是头节点，则将头节点指针指向下一个节点

head->prev = NULL;

free(node); //释放原来的头节点内存

return;

}

if(node->prev != NULL) {

node->prev->next = node->next; //将节点的前驱节点和后继节点相连

}

if(node->next != NULL) {

node->next->prev = node->prev;

}

free(node); //释放该节点内存

}

```

四、双向链表的特点

从上面的操作可以看出，双向链表的主要特点有以下几点：

1. 可以双向遍历链表。

2. 可以快速删除某个节点。

3. 在插入和删除节点时，需要维护前驱节点和后继节点的指针，因此可以实现较快的插入和删除操作。