数据结构基础之双循环链表--双链表

双链表的结点结构

typedef struct DLNode { 
	elementType     data;       // 数据域 
	struct DLNode  *prior ;    // 前向指针域 
	struct DLNode  *next;      // 后向指针域
} dNode;

双循环链表的初始化

void initialList(dNode*& L){
	L = new node;
	L->prior = L;
	L->next = L;
}

双链表的插入算法

bool listInsert(dNode* L, int i, elementType x){
	dNode* p = L->next;
	dNode* s;
	int k = 1;
	
	while (k != i && p != L){
		k++;
		p = p->next;
	}
	
	if (p == L && k != i)
		return false;
		
	else {
		s = new dNode;
		s->data = x;
		s->next = p;
		s->prior = p->prior;
		p->prior = s;
		s->prior->next = s;
		 
		return true;
	}
	
} 

双链表的删除算法

bool listDelete(dNode* L, int i, elementType &x){
	dNode* p = L->next;
	int k = 1;
	
	while (k!=i && p != L){
		k++;
		p = p->next;
	}
	
	if (p==L)
		return false;
	else {
		p->prior->next = p->next;
		p->next->prior = p->prior;
		x = p->data;
		
		delete p;
		return true;
	}
}