双向链表链表的实现

引言

上一篇博客讲到单链表的结点中只有一个指向下一个节点的指针，只能按顺序访问，不能逆向访问。双向链表满足双向访问的需求，不只可以得到结点的下一个指针域，也可以得到前一个指针域，更加方便的查询修改。

一、双向链表

相较于单链表，双向链表有两个指针域：直接前驱的指针域和直接后继指针域。

优缺点：

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