博客

双向链表的定义

什么是双向链表？

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双链表的存储结构如下：



在单链表中有一个数据域和指针域，数据域用来存储相关数据，指针域用来存储下一个元素的地址，将其连接起来。而在双链表中则是有两个指针域，一个向前连接，一个向后连接。

双向链表的结构

typedef struct DulNode{
	ElemType data; //数据域
	struct DulNode *prior, *next; //前指针，后指针
}DulNode, *DulLinkList;

双向链表的基本操作

双链表的插入

bool ListInsert_Dul(DulinkList &L,int i,ElemType e){
	if(!(p = getElem_Dul(L,i)){
		return 0;
	}
	DulNode* s = new DulNode;  //创建一个新表s
	s -> data = e;	
	s -> prior = p -> prior;
	p -> prior -> next = s;
	s -> next = p;
	p -> prior = s;
	return 1;
}

双链表的删除

bool Listdelete_Dul(DulinkList &L,int i,ElemType &e){
	if(!(p = getElem_Dul(L,i)){
		return 0;
	}
	e = p -> data;
	p -> prior -> next = p -> next;
	p -> next -> prior = p -> prior;
	delete p;
	return 1;
}