我們在單鏈表中，有了next指針，這個指針是用來指向下一個節(jié)點的，如果我們需要查找下一個結點的時間復雜度為o(1),如果我們需要查找上一個節(jié)點的時候，那么時間復雜度就變?yōu)閛(n)了，需要從頭進行遍歷一遍；這時我們就會想：如果可以向前查找就方便了許多，因此我們引入了雙向鏈表。

二.雙向鏈表的定義

雙向鏈表：是在單鏈表的每個節(jié)點中，再設置一個指向前驅結點的指針域。

顧名思義就是鏈表由單向的變成了雙向的，每一個節(jié)點由原來的一個指針變?yōu)閮蓚€指針，一個用來指向直接后繼，另一個用來指向直接前驅。

三.雙向鏈表與單鏈表對比

通過對比可以更好認識二者的聯(lián)系與區(qū)別。

3.1圖示對比

單鏈表：

雙向鏈表：

3.2代碼對比

單鏈表代碼如下：

typedef struct Node{ //定義單鏈表結點類型
	int data; //數(shù)據(jù)域，可以是別的各種數(shù)據(jù)類型
	struct Node *next; //指針域
}LNode, *LinkList;

雙向鏈表代碼如下：

typedef struct DulNode{
	int data;			// 	數(shù)據(jù)域
	struct DulNode *prior;		//  向前的指針
	struct DulNode *next;		//  向后的指針
}DulNode,*DuLinkList;

四.雙向鏈表的操作

雙向鏈表是單鏈表中擴展出來的結構，所以有很多的操作是和單鏈表相同的，如求長度，查找元素，獲取一個元素，這里我們對雙向鏈表進行創(chuàng)建，插入，刪除，銷毀的一系列操作。

4.1雙向鏈表的創(chuàng)建

雙向鏈表在初始化時，要給首尾兩個節(jié)點分配內存空間。成功分配后，需要將首節(jié)點的prior指針和尾節(jié)點的next指針都指向NULL，這是十分關鍵的一步，因為這是之后用來判斷空表的條件。并且當鏈表為空時，要將首節(jié)點的next指向尾節(jié)點，尾節(jié)點的prior指向首節(jié)點。

pElem CreatList(){
	pElem head = (pElem)malloc( sizeof(eElem) );
	assert( head != NULL );		//進行斷言
	head->next = head->prior = NULL；//初始化鏈表指針置空
	return head;
}

4.2雙向鏈表的插入

雙向鏈表的插入其實并不復雜，只是在原有單鏈表的基礎上多了連接一個向前的指針而已。但是需要注意的是操作的順序很重要，不可以寫反了。

以下面這個為例，假設存儲元素e的結點為s，要實現(xiàn)將結點s插入到結點p和p->next之間

核心代碼就只有以下四行：

s->prior=p; //把p賦值給s的前驅
s->next=p->next;// 把p->next賦值給s的后繼
p->next->prior=s;// 把s賦值給p->next的前驅
p->next=s; //把s賦值給p的后繼

切記順序不可以記錯在寫代碼的時候可以將操作步驟畫出來，理清實施步驟的順序。

4.3雙向鏈表的刪除

如果將插入操作的原理理解后，那么刪除就很好理解了。

刪除只需要兩個步驟：

核心代碼只有三行：

p->prior->next=p->next; //把p->next賦值給p->prior的后繼
p->next->prior=p->prior;//把p->prior賦值給p->next的前驅
free(p); //釋放結點

4.4雙向鏈表的銷毀

銷毀一個雙向鏈表的操作同單鏈表的相似。指針不斷向后運動，每運動一個結點，釋放上一個結點。

代碼如下：

void DestroyList( pElem head ){
	pElem tmp;
	while( head->next != NULL ){
		tmp = head;		//  指針不斷后移
		head = head->next;
		free(tmp);
	}
	free(head);
}

五.總結

雙向鏈表相比于單鏈表來說，是更復雜一些的，畢竟多了一個prior指針，對于插入和刪除需要特別注意這兩種操作的核心思想以及操作順序。另外雙向鏈表，帶來了方便，可以有效提高算法的時間性能。

六.全部代碼

這里引用一位大佬寫的代碼，將頭插法和尾插法創(chuàng)建表都寫了，寫的很細節(jié)，很清楚大家可以參考一下。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int status;
typedef int elemtype;
typedef struct node{
    elemtype data;
    struct node * next;
    struct node * prior;
}node;
typedef struct node* dlinklist;
status visit(elemtype c){
    printf("%d ",c);
}
/*雙向鏈表初始化*/
status initdlinklist(dlinklist * head,dlinklist * tail){
    (*head)=(dlinklist)malloc(sizeof(node));
    (*tail)=(dlinklist)malloc(sizeof(node));
    if(!(*head)||!(*tail))
        return ERROR;
    /*這一步很關鍵*/ 
    (*head)->prior=NULL;
    (*tail)->next=NULL;
    /*鏈表為空時讓頭指向尾*/
    (*head)->next=(*tail);
    (*tail)->prior=(*head);
}
/*判定是否為空*/
status emptylinklist(dlinklist head,dlinklist tail){
    if(head->next==tail)
       return TRUE;
    else
       return FALSE;
} 
/*尾插法創(chuàng)建鏈表*/ 
status createdlinklisttail(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pmove=tail,pinsert;
    pinsert=(dlinklist)malloc(sizeof(node));
    if(!pinsert)
         return ERROR;
    pinsert->data=data;
    pinsert->next=NULL;
    pinsert->prior=NULL;
    tail->prior->next=pinsert;
    pinsert->prior=tail->prior;
    pinsert->next=tail;
    tail->prior=pinsert;
} 
/*頭插法創(chuàng)建鏈表*/ 
status createdlinklisthead(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pmove=head,qmove=tail,pinsert;
    pinsert=(dlinklist)malloc(sizeof(node));
    if(!pinsert)
        return ERROR;
    else{
        pinsert->data=data;
        pinsert->prior=pmove;
        pinsert->next=pmove->next;
        pmove->next->prior=pinsert;
        pmove->next=pinsert;
    }
}
/*正序打印鏈表*/ 
status traverselist(dlinklist head,dlinklist tail){
    /*dlinklist pmove=head->next;
    while(pmove!=tail){
        printf("%d ",pmove->data);
        pmove=pmove->next;
    }
    printf("\n");
    return OK;*/
    dlinklist pmove=head->next;
    while(pmove!=tail){
        visit(pmove->data);
        pmove=pmove->next;
    }
    printf("\n");
}
/*返回第一個值為data的元素的位序*/
status locateelem(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pmove=head->next;
    int pos=1;
    while(pmove&&pmove->data!=data){
        pmove=pmove->next;
        pos++;
    }
    return pos;
}
/*返回表長*/
status listlength(dlinklist head,dlinklist tail){
    dlinklist pmove=head->next;
    int length=0;
    while(pmove!=tail){
        pmove=pmove->next;
        length++;
    }
    return length;
}
/*逆序打印鏈表*/
status inverse(dlinklist head,dlinklist tail){
    dlinklist pmove=tail->prior;
    while(pmove!=head){
        visit(pmove->data);
        pmove=pmove->prior;
    }
    printf("\n");
}
/*刪除鏈表中第pos個位置的元素，并用data返回*/
status deleteelem(dlinklist head,dlinklist tail,int pos,elemtype *data){
    int i=1;
    dlinklist pmove=head->next;
    while(pmove&&i<pos){
        pmove=pmove->next;
        i++;
    }
    if(!pmove||i>pos){
        printf("輸入數(shù)據(jù)非法\n");
        return ERROR;
    }
    else{
        *data=pmove->data;
        pmove->next->prior=pmove->prior;
        pmove->prior->next=pmove->next;
        free(pmove);
    }
}
/*在鏈表尾插入元素*/
status inserttail(dlinklist head,dlinklist tail,elemtype data){
    dlinklist pinsert;
    pinsert=(dlinklist)malloc(sizeof(node));
    pinsert->data=data;
    pinsert->next=NULL;
    pinsert->prior=NULL;
    tail->prior->next=pinsert;
    pinsert->prior=tail->prior;
    pinsert->next=tail;
    tail->prior=pinsert;
    return OK;
} 
int main(void){
    dlinklist head,tail;
    int i=0;
    elemtype data=0;
    initdlinklist(&head,&tail);
    if(emptylinklist(head,tail))
        printf("鏈表為空\n");
    else
        printf("鏈表不為空\n");
    printf("頭插法創(chuàng)建鏈表\n"); 
    for(i=0;i<10;i++){
        createdlinklisthead(head,tail,i);
    }
    traverselist(head,tail);
    for(i=0;i<10;i++){
        printf("表中值為%d的元素的位置為",i); 
        printf("%d位\n",locateelem(head,tail,i));
    }
    printf("表長為%d\n",listlength(head,tail));
    printf("逆序打印鏈表");
    inverse(head,tail);
    for(i=0;i<10;i++){
        deleteelem(head,tail,1,&data);
        printf("被刪除的元素為%d\n",data);
    }
    traverselist(head,tail);
    if(emptylinklist(head,tail))
        printf("鏈表為空\n");
    else
        printf("鏈表不為空\n");
        printf("尾插法創(chuàng)建鏈表\n");
    for(i=0;i<10;i++){
        //inserttail(head,tail,i);
        createdlinklisttail(head,tail,i);
    }
    traverselist(head,tail);
    printf("逆序打印鏈表");
    inverse(head,tail);
}

到此這篇關于C語言雙向鏈表的原理與使用操作的文章就介紹到這了,更多相關C語言雙向鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: