雙向鏈表

雙向鏈表是鏈表變型，相比於單鏈表導航或者是向前和向後的兩種方式。以下是重要的術語來理解雙向鏈表的概念

• Link − 鏈表的每個鏈路存儲數據稱爲一個元素。

• Next − 鏈表的每個鏈接包含一個鏈接到下一個被稱爲下一個(Next)。

• Prev − 鏈表的每個鏈接包含一個鏈接，稱爲上一個鏈接(Prev)。

• LinkedList − LinkedList包含連接鏈接到名爲首先第一個鏈接，並稱爲最後的最後一個鏈接(Last)。

雙向鏈表表示

按照如上圖中所示，以下是要考慮的重要問題。

• 雙向鏈表包含一個名爲第一個（first）和最後一個鏈接(last)元素。
• 每個鏈路負責數據字段和LINK域被稱爲下一個(Next)。
• 每一個Link鏈接，其利用其下一個鏈接指向下一個鏈接。
• 每一個Link鏈接使用其上一個鏈接指向上一個鏈接。
• 最後一個鏈接帶有鏈接的空標記列表的末尾。

基本操作

下面是一個列表支持的基本操作。

• 插入 − 在列表的開頭添加的元素。

• 刪除− 刪除在列表開頭的元素。

• 插入最後 − 在列表的末尾添加元素。

• 刪除最後 − 刪除列表的末尾的元素。

• 插入之後− 列表中的項目後添加元素。

• 刪除 − 用鍵從列表中刪除一個元素。

• 正向顯示 − 以向前的方式顯示完整列表。

• 後向顯示 − 向後的方式顯示完整列表。

插入操作

下面的代碼演示了插入操作，從一個雙向鏈表的開始。

//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;
}

要查看 C編程語言的實現，請點擊 。