# 数据结构&算法 双向链表

• ## 双向链表

双向链表是链表的一种变体，与单链表相比，双向链表都可以轻松实现。以下是理解双向链表概念的重要术语。
• Next —— 链表中的每个链接都包含一个指向下一个链接的链接，该链接称为Next。
• Prev —— 链表中的每个链接都包含一个指向前一个称为Prev的链接。
• ## 双向链表表示 根据上面的说明，以下是要考虑的重点。
• 双链表包含一个名为first和last的链接元素。
• 每个链接包含一个数据字段和两个链接字段，分别称为next和prev。
• 每个链接都使用其下一个链接与其下一个链接链接。
• 每个链接都使用其上一个的链接与其上一个的链接链接。
• 最后一个链接带有一个空链接，以标记列表的结尾。
• ## 基本操作

以下是双向链表支持的基本操作。
• 插入 -在列表的开头添加一个元素。
• 删除 -删除列表开头的元素。
• 插入最后 -在列表的末尾添加一个元素。
• 最后删除-从列表末尾删除元素。
• 在以下位置插入 -在列表项之后添加元素。
• 删除 -使用键从列表中删除元素。
• 向前显示-以向前方式显示完整列表。
• 向后显示- 向后显示完整列表。
• ## 插入操作

以下代码演示了在双向链表开头的插入操作。
``````
//insert link at the first location
void insertFirst(int key, int data) {

struct node *link = (struct node*) malloc(sizeof(struct node));

if(isEmpty()) {
} else {
}

//point it to old first link

//point first to new first link
}
```
```
• ## 删除操作

以下代码演示了双向链表开头的删除操作。-
``````
//delete first item
struct node* deleteFirst() {

last = NULL;
} else {
}

}
```
```
• ## 在最后插入

以下代码演示了在双链表的最后位置的插入操作。
``````
//insert link at the last location
void insertLast(int key, int data) {

struct node *link = (struct node*) malloc(sizeof(struct node));

if(isEmpty()) {
} else {

//mark old last node as prev of new link
}

//point last to new last node
}
```
```
• ## 双向链表的C语言实现

``````
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;

struct node *next;
struct node *prev;
};

struct node *last = NULL;

struct node *current = NULL;

//is list empty
bool isEmpty() {
}

int length() {
int length = 0;
struct node *current;

for(current = head; current != NULL; current = current->next){
length++;
}

return length;
}

//display the list in from first to last
void displayForward() {

//start from the beginning

//navigate till the end of the list
printf("\n[ ");

while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}

printf(" ]");
}

//display the list from last to first
void displayBackward() {

//start from the last
struct node *ptr = last;

//navigate till the start of the list
printf("\n[ ");

while(ptr != NULL) {

//print data
printf("(%d,%d) ",ptr->key,ptr->data);

//move to next item
ptr = ptr ->prev;

}

}

//insert link at the first location
void insertFirst(int key, int data) {

struct node *link = (struct node*) malloc(sizeof(struct node));

if(isEmpty()) {
} else {
}

//point it to old first link

//point first to new first link
}

//insert link at the last location
void insertLast(int key, int data) {

struct node *link = (struct node*) malloc(sizeof(struct node));

if(isEmpty()) {
} else {

//mark old last node as prev of new link
}

//point last to new last node
}

//delete first item
struct node* deleteFirst() {

last = NULL;
} else {
}

}

//delete link at the last location

struct node* deleteLast() {

} else {
last->prev->next = NULL;
}

last = last->prev;

}

//delete a link with given key

struct node* delete(int key) {

struct node* previous = NULL;

//if list is empty
return NULL;
}

//navigate through list
while(current->key != key) {
//if it is last node

if(current->next == NULL) {
return NULL;
} else {
previous = current;

current = current->next;
}
}

//found a match, update the link
//change first to point to next link
} else {
current->prev->next = current->next;
}

if(current == last) {
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}

return current;
}

bool insertAfter(int key, int newKey, int data) {

//if list is empty
return false;
}

//navigate through list
while(current->key != key) {

//if it is last node
if(current->next == NULL) {
return false;
} else {
current = current->next;
}
}

struct node *newLink = (struct node*) malloc(sizeof(struct node));

if(current == last) {
} else {
}

return true;
}

void main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);

printf("\nList (First to Last): ");
displayForward();

printf("\n");
printf("\nList (Last to first): ");
displayBackward();

printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();

printf("\nList , after deleting last record: ");
deleteLast();
displayForward();

printf("\nList , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();

printf("\nList  , after delete key(4) : ");
delete(4);
displayForward();
}
```
```
如果我们编译并运行上述程序，它将产生以下结果-
``````
List (First to Last):
[ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ]

List (Last to first):
[ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ]
List , after deleting first record:
[ (5,40) (4,1) (3,30) (2,20) (1,10) ]
List , after deleting last record:
[ (5,40) (4,1) (3,30) (2,20) ]
List , insert after key(4) :
[ (5,40) (4,1) (7,13) (3,30) (2,20) ]
List , after delete key(4) :
[ (5,40) (4,13) (3,30) (2,20) ]
```
```