双链表
双链表是链表的一种变体，与单链表相比，双链表可以双向导航，向前和向后都更容易。以下是理解双向链表概念的重要术语。
Link-链表的每个链接都可以存储一个称为元素的数据。
Next-链表的每个链接都包含一个指向名为 Next 的下一个链接的链接。
Prev-链表的每个链接都包含一个指向上一个链接的链接，称为 Prev。
LinkedList-链接列表包含指向名为 First 的第一个链接和名为 Last 的最后一个链接的连接链接。
双向链表表示
根据上图，以下是需要考虑的重点。
双向链表包含一个名为 first 和 last 的链接元素。
每个链接都带有一个数据字段和两个称为 next 和 prev 的链接字段。
每个链接都使用其下一个链接与其下一个链接相链接。
每个链接都使用其上一个链接与其上一个链接相链接。
最后一个链接带有一个为空的链接，以标记列表的结尾。
基本操作
以下是列表支持的基本操作。
插入-在列表的开头添加一个元素。
删除-删除列表开头的元素。
末尾添加-在列表末尾添加一个元素。
删除最后一个-从列表末尾删除一个元素。
项后添加-在列表项之后添加一个元素。
删除-使用键从列表中删除一个元素。
向前显示-向前显示完整列表。
向后显示-向后显示完整列表。
插入操作
以下代码演示了在双向链表开头的插入操作。
示例
//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
删除操作
以下代码演示了双向链表开头的删除操作。
示例
//delete first item
struct node* deleteFirst() {
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == null) {
last = null;
} else {
head->next->prev = null;
}
head = head->next;
//return the deleted link
return tempLink;
}
在操作结束时插入
以下代码演示了在双向链表最后位置的插入操作。
示例
//insert link at the last location
void insertLast(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
