数据结构 双向链表及其基本操作_双向链表的基本操作

一.引入

我们在单链表中，有了next指针，这个指针是用来指向下一个节点的，如果我们需要查找下一个结点的时间复杂度为o(1),如果我们需要查找上一个节点的时候，那么时间复杂度就变为o(n)了，需要从头进行遍历一遍；这时我们就会想：如果可以向前查找就方便了许多，因此我们引入了双向链表。

二. 双向链表的定义

双向链表：是在单链表的每个节点中，再设置一个指向前驱结点的指针域。

顾名思义就是链表由单向的变成了双向的，每一个节点由原来的一个指针变为两个指针，一个用来指向直接后继，另一个用来指向直接前驱。

三.双向链表与单链表对比

通过对比可以更好认识二者的联系与区别。

3.1图示对比

单链表：

双向链表：

3.2代码对比

单链表代码如下：

typedef struct Node{ //定义单链表结点类型
	int data; //数据域，可以是别的各种数据类型
	struct Node *next; //指针域
}LNode, *LinkList;
1
2
3
4

双向链表代码如下：

typedef struct DulNode{
	int data;			// 	数据域
	struct DulNode *prior;		//  向前的指针
	struct DulNode *next;		//  向后的指针
}DulNode,*DuLinkList;
1
2
3
4
5

四.双向链表的操作

双向链表是单链表中扩展出来的结构，所以有很多的操作是和单链表相同的，如求长度，查找元素，获取一个元素，这里我们对双向链表进行创建，插入，删除，销毁的一系列操作。

4.1双向链表的创建

双向链表在初始化时，要给首尾两个节点分配内存空间。成功分配后，需要将首节点的prior指针和尾节点的next指针都指向NULL，这是十分关键的一步，因为这是之后用来判断空表的条件。并且当链表为空时，要将首节点的next指向尾节点，尾节点的prior指向首节点。

pElem CreatList(){
	pElem head = (pElem)malloc( sizeof(eElem) );
	assert( head != NULL );		//进行断言
	head->next = head->prior = NULL；//初始化链表指针置空
	return head;
}
1
2
3
4
5
6

4.2双向链表的插入

双向链表的插入其实并不复杂，只是在原有单链表的基础上多了连接一个向前的指针而已。但是需要注意的是操作的顺序很重要，不可以写反了。
以下面这个为例，假设存储元素e的结点为s，要实现将结点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的后继
1
2
3
4

切记顺序不可以记错 在写代码的时候可以将操作步骤画出来，理清实施步骤的顺序。

4.3双向链表的删除

如果将插入操作的原理理解后，那么删除就很好理解了。
删除只需要两个步骤：

核心代码只有三行：

p->prior->next=p->next; //把p->next赋值给p->prior的后继
p->next->prior=p->prior;//把p->prior赋值给p->next的前驱
free(p); //释放结点
1
2
3

4.4双向链表的销毁

销毁一个双向链表的操作同单链表的相似。指针不断向后运动，每运动一个结点，释放上一个结点。

代码如下：

void DestroyList( pElem head ){
	pElem tmp;
	while( head->next != NULL ){
		tmp = head;		//  指针不断后移
		head = head->next;
		free(tmp);
	}
	free(head);
}
1
2
3
4
5
6
7
8
9

五.总结

双向链表相比于单链表来说，是更复杂一些的，毕竟多了一个prior指针，对于插入和删除需要特别注意这两种操作的核心思想以及操作顺序。另外双向链表，带来了方便，可以有效提高算法的时间性能。

六.全部代码

这里引用一位大佬写的代码，将头插法和尾插法创建表都写了，写的很细节，很清楚大家可以参考一下。

#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;
} 

/*尾插法创建链表*/ 
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;
} 

/*头插法创建链表*/ 
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("输入数据非法\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("头插法创建链表\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("尾插法创建链表\n");
    for(i=0;i<10;i++){
        //inserttail(head,tail,i);
        createdlinklisttail(head,tail,i);
    }
    traverselist(head,tail);
    printf("逆序打印链表");
    inverse(head,tail);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194