雙向連結清單

• ✍通俗定義：

就是線上性表的鍊式存儲中，每個實體節點增加一個指向後繼節點的指針域 和一個指向前驅節點的指針域 

          它長這樣兒：

• ✍優缺點：

優點（與單連結清單相比雙向連結清單）：
       1. 從任一節點出發可以 快速找到與其相鄰的前（驅）後（繼）節點
       2.從任一節點出發可以通路其他節點。
缺點：增加删除節點複雜（其實就複雜一點點）
           

• ✍基本操作：

1. ❤定義：❤

   typedef struct Dnode{
         Elemtype data;
         struct Dnode *prior;//指向前驅節點的指針 
         struct Dnode *next;//指向後繼節點的指針
   }Dlinklist;
              

2. ❤建立（初始化）：❤

                            下面介紹建立雙連結清單的兩種方法（與單連結清單建表方式類似）：

                           1.頭插法：CreateListH()    （如下圖）

                           2.尾插法：CreateListR() （小夥伴們*這個尾插法示意圖太難找了，不過還能容易想象，每次在最後位置插入）

頭插法

//頭插法
void CreateListH(Dlinklist *&L,Elemtype a[],int n){
	Dlinklist *s;int i;
	L=(Dlinklist *)malloc(sizeof(Dlinklist));
	L->prior=L->next=NULL;
	//建立n個節點逐個插入到頭節點的後面 
	for(i=0;i<n;i++){
	s=(Dlinklist *)malloc(sizeof(Dlinklist));
	s->data=a[i];
	s->next=L->next;//先把後繼接上
	//分情況 l有無後繼
	if(L->next!=NULL){
		L->next->prior=s;//L有後繼時 先把L的 後繼節點的前驅 設為s 
		}
	//把s挂在L後面
	L->next=s; 
	s->prior=L;	
	}
} 
           

//尾插法
void CreateListR(Dlinklist *&L,Elemtype a[],int n){
	Dlinklist *s,*r;  int i;
	L=(Dlinklist *)malloc(sizeof(Dlinklist));
	r=L;//尾指針初始化為頭指針
	//建立n個節點逐個插入到尾節點的後面 
	for(i=0;i<n;i++){
	s=(Dlinklist *)malloc(sizeof(Dlinklist));
	s->data=a[i];
	r->next=s;
	s->prior=r;
	r=s;//尾插時一定要記得更新尾指針，r永遠指向最後一個節點 
	} 
	r->next=NULL;//并且尾指針的指針域設為NULL 
}
           

3.❤插入删除：//和單連結清單相比，雙連結清單主要是插入和删除運算不同// ❤

普通雙向連結清單插入示意圖

雙向循環連結清單插入結點圖示i

//插入結點
    bool Listinsert(Dlinklist *&L,int i;Elemtype e){
	int j=0;
	Dlinklist *p=L,*s;//p指向頭結點
	//查找第i-1個結點*p,即插入位置的前驅結點，也即在p結點後插入 
	while(j<i-1&&p!=NULL){
		j++;
		p->next;
	} 
	if(p==NULL){
		//未找到第i-1個結點
		return false; 
	}
	else{
		s=(Dlinklist *)malloc(sizeof(Dlinklist));
	    s->data=e;
	    s->next=p->next;//先把s後面挂上p的後繼 
	    if(p->next!=NULL){
		//如果p不是尾結點 ，則需要将p的後繼節點的前驅更新為s 
	    p->next->prior=s;
		} 
		//把p後挂上s 
		s->prior=p;
		p->next=s;
		return true;
	} 	
}
           

普通雙向連結清單删除結點示意圖

雙向循環連結清單删除結點示意圖

//删除節點
bool ListDelete(Dlinklist *&L,int i,Elemtype &e){
	int j=0; Dlinklist *p=L,*q;
	//同樣也是周遊尋找删除節點的前驅 
	while(j<i-1 && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL){//表中不存在第i-1個結點 
		return false;
	} 
	else{
		q=p->next;//此時用q表示所需删除的節點
		if(q==NULL){//表中不存在第I個結點 
		return false;}	
		e=q->data;
		p->next=q->next;
		if(q->next!=NULL){//若删除結點不是尾結點， 則需更新删除結點的後繼節點的前驅 
			q->next->prior=p;
		}
		free(q);//釋放q
		return true; 
        }
} 
           

4.❤轉置（逆置）：把連結清單資料倒序❤

void Reverse(Dlinklist *&L){
	Dlinklist *p=L->next,*q; 
		L->next=NULL;//相當于把L從第一個結點開始截取成一個新的無頭結點的雙向連結清單 
	while(p!=NULL){
		q=p->next;
	    p->next=L->next;//先把後繼接上
	    //分情況 l有無後繼(實質上隻有插入第一個節點時才屬于無後繼，直接挂)
	   if(L->next!=NULL){
		L->next->prior=p;//L有後繼時（也即從插入第二個節點開始）就需要先把L的 後繼節點的前驅 設為s 
		}
		L->next=p;
		p->prior=L;
		//以上與頭插建表類似
		p=q;//循環往後逐個周遊 
	} 	
}
}
           

• ✍正經緻謝：