引言

上一篇博客講到單鏈表的結點中只有一個指向下一個節點的指針，只能按順序訪問，不能逆向訪問。雙向鏈表滿足雙向訪問的需求，不只可以得到結點的下一個指針域，也可以得到前一個指針域，更加方便的查詢修改。

一、雙向鏈表

相較于單鏈表，雙向鏈表有兩個指針域：直接前驅的指針域和直接后繼指針域。

優缺點：

（1）可以實現順序訪問和逆序訪問；

（2）增加了一個指針域，增加了空間開銷。

雙向鏈表圖示：

二、雙向鏈表代碼實現

DList.h

#PRagma once#define ElemType int/*雙向循環鏈表存儲結構*/typedef struct Node{	ElemType data; //數據域	struct Node *next;//后繼指針域	struct Node *prio;//前驅指針域}DNode,*DList;/*雙向循環鏈表的操作*/DNode* buyNode(ElemType val);//創建一個節點bool initSize(DList &L);//初始化bool insert_head(DList &L, ElemType val);//頭插法bool insert_tail(DList &L, ElemType val);//尾插法bool deleteList(DList &L, ElemType val);//刪除元素Node* searchElem(DList &L, ElemType val);//查找元素int GetLength(DList &L);//獲取鏈表的長度bool displayList(DList &L);//輸出鏈表的元素void ClearList(DList &L);//清除鏈表void Destroy(DList &L);//摧毀鏈表DList.cpp
#include <iostream>#include "DList.h"using namespace std;DNode* buyNode(ElemType val)//創建一個節點{	DNode *p = (DNode*)malloc(sizeof(DNode));	if (NULL == p) return NULL;//申請結點失敗	memset(p, 0, sizeof(DNode));	p->data = val;	p->prio = p->next = NULL;	return p;}bool initSize(DList &L)//初始化{	L = buyNode(0);//初始化一個結點	return true;}bool insert_head(DList &L, ElemType val)//頭插法{	DNode* p = buyNode(val);//購買結點	p->next = L->next;//新結點后繼指針指向頭結點后一個	L->next = p;//頭結點后繼指針指向新結點	p->prio = L;//新結點前驅指針指向頭結點	if (p->next != NULL)//如果新結點后繼有結點	{		p->next->prio = p;//結點的前驅指向新節點	}	return true;}bool insert_tail(DList &L, ElemType val)//尾插法{	DNode *p = buyNode(val);	DNode *q = L;	for (; q!= NULL; q = q->next) {}//q指向最后一個結點	p->next = q->next;//新結點后繼指向為NULL	p->prio = q;//新結點前驅指向最后一個結點	q->next = p;//最后一個結點后繼指向新節點	return true;}Node* searchElem(DList &L, ElemType val)//查找元素{	DNode *p = L->next;	while (p != NULL)	{		if (p->data == val)//匹配		{			return p;		}		p = p->next;	}	return NULL;}bool deleteList(DList &L, ElemType val)//刪除元素{	DNode *p = searchElem(L, val)->prio;//確定要刪除節點的前驅	if (p == NULL)	{		return false;	}	DNode *q = p->next;//保留該結點	p->next = p->next->next;//該結點前驅的后繼指向該結點的后繼	if (p->next != NULL)	{		p->next->prio = p;//更改后繼的前驅	}	free(q);	return true;}int GetLength(DList &L)//獲取鏈表的長度{	int count = 0;	DNode *p = L->next;	while (p != NULL)	{		count++;		p = p->next;	}	return count;}bool displayList(DList &L)//輸出鏈表的元素{	DNode *p = L->next;	while (p != NULL)	{		cout << p->data << " ";		p = p->next;	}	cout << endl;	return true;}void ClearList(DList &L)//清除鏈表{	Destroy(L);}void Destroy(DList &L)//摧毀鏈表{	DNode *p = L->next;	DNode *q;	L->next = NULL;	while (p != NULL)	{		q = p->next;		free(p);		p = q;	}}
//main.cpp
#include <iostream>#include "DList.h"using namespace std;int main(){	DList List;	initSize(List);	for (int i = 0; i < 10; ++i)	{		insert_head(List,i);	}	/*	for (int i = 0; i < 10; ++i)	{		insert_tail(List, i, i);	}	*/	displayList(List);	deleteList(List, 5);	displayList(List);	if (searchElem(List, 6))		cout << "elem 6 is found" << endl;	cout << "List length is " << GetLength(List) << endl;	Destroy(List);	return 0;}