双向链表

• 双向链表
• 双向循环链表
• • • 双向链表的插入
    • 双向链表的删除

双向链表

在单链表的每个结点里再增加一个指向其前驱的指针

双向链表的结构定义：

//DuLNode (DoubleLNode)
typedef struct DuLNode{
	Elemtype	data;
	struct DoubleLNode	*prior, *next;
}DuLNode, *DuLinkList

 
 

双向循环链表

• 让头结点的前驱指针指向链表的最后一个结点
• 让最后一个结点的后继指针指向头结点
• 当循环双链表为空表时，其头结点的prior域和next域都等于L

对称性：

//设指针p指向某一结点
p -> prior -> next = p = p -> next -> prior

 
 

双向链表的插入

1. s -> next = p -> prior;
2. p -> prior -> next = s;
3. s -> next = p;
4. p -> prior = s;

void ListInsert_DuL(DuLinkList &L, int i, Elemtype e){
//在带头结点的双向循环链表L中第i个位置之前插入元素e
	if(!(p = GetElemP_Dul(L,i)))		//判断插入位置是否合理
		return ERROR;
	s = new DuLNode;
	s -> data = e;
	s -> prior = p -> prior;
	p -> prior -> next = s;
	s -> next = p;
	p -> prior = s;
	return OK;
}// ListInsert_DuL

 
 

双向链表的删除

1. p -> prior -> next = p -> next;
2. p -> next -> prior = p -> prior;

void ListDelete_DuL(DuLink &L. int i, ElemType &e){
//删除带头结点的双向循环链表L的第i个元素， 并用e返回
	if(!(p = GetElemP_DuL(L, i)))		//判断删除位置是否合理
		return ERROR;
	e = p -> data;
	p -> prior -> next = p -> next;
	p -> next -> prior = p -> prior;
	free(p);
		return OK;
}//ListDelete_DuL