【数据结构】双向链表详解

当我们学习完单链表后，双向链表就简单的多了，双向链表中的头插，尾插，头删，尾删，以及任意位置插，任意位置删除比单链表简单，今天就跟着小张一起学习吧！！

双向链表的分类

双向不带头链表

双向带头循环链表

还有双向带头不循环链表，双向不带头循环链表，着重使用双向带头循环链表，带头也就是有哨兵位。

双向带头循环链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

双向循环链表的接口实现

ListNode* ListCreate(int x)//创建新结点
ListNode* createhead()//创建哨兵位
void ListPushBack(ListNode* phead, int x)//尾插
void SListPrint(ListNode* phead)//打印链表
void SListPushFront(ListNode* phead, int x)//头插
void SListPopBack(ListNode* phead)//尾删
void SListPopFront(ListNode* phead)//头删
void SListInsert(ListNode* pos, int x)//pos前插
void SListErase(ListNode* pos)//删除pos;
ListNode* SListFind(ListNode* phead,int x)//查找链表中第一个x

1
2
3
4
5
6
7
8
9
10
11

0.结点结构体创建

typedef struct ListNode
{
	int data;//数据
	struct ListNode* next;//下个结点地址
	struct ListNode* prev;//上个结点地址
}ListNode;
1
2
3
4
5
6

1.创建一个新结点

ListNode* ListCreate(int x)//创建新结点
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//给新结点申请空间
	if (newnode == NULL)
	{
		perror("malloc error");//没申请到，malloc返回NULL给newnode
		
	}
	newnode->data = x;//新结点的数据给x
	newnode->next = NULL;//新结点的下一个结点地址为空
	newnode->prev = NULL;//新结点的上一个结点地址为空
	return newnode;//新结点的地址返回回去
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.创建哨兵位

该哨兵位作为链表的头结点，不存数据

ListNode* createhead()
{
	ListNode* head = ListCreate(-1);//哨兵位结点的数据随便给个-1
	head->next = head;
	head->prev = head;
	return head;//返回哨兵位的头结点地址
}
1
2
3
4
5
6
7

当没有带数据的新结点时，先让他上一个结点地址，和下一关结点地址都存入head自己的地址

3.尾插

void ListPushBack(ListNode* phead, int x)//尾插
{
	ListNode* newnode = ListCreate(int x);
	ListNode* tail = phead->prev;//记录尾结点的地址
	newnode->prev =tail;//新结点的prev存放尾结点的地址-1
	newnode->next = phead;//新结点的next存放头结点哨兵位的地址->2
	phead->prev = newnode;//头结点的prev存放新结点的地址->4
	tail->next = newnode;//尾结点的next存放新节点的地址->3

}
1
2
3
4
5
6
7
8
9
10

分析：
由于使用tail记录了尾结点的地址，所以1，2，3，4可以任意切换顺序，如果没有记录，记得先将新结点的prev,next,先保存，然后在修改head->prev, head->prev->next;防止修改过程中，尾结点的地址丢失。

同样适用于在哨兵位后插新结点

4.打印双链表

void SListPrint(ListNode* phead)//打印链表
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->", cur->data);
		cur = cur->next;
    }
	printf("\n");


}
1
2
3
4
5
6
7
8
9
10
11
12

分析：定义一个指针cur遍历整个链表，由于是循环链表，肯定会指向哨兵位，哨兵位结点的数据不使用，所以cur指针从头节点哨兵位的下一个结点开始遍历，直到cur==phead,循环结束，每次打印cur->data,然后移动cur到下一个结点。

5.头插

void SListPushFront(ListNode* phead, int x)//头插
{
	ListNode* newnode = ListCreate(x);
	
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;

}
1
2
3
4
5
6
7
8
9
10

分析：
注意：先保存newnode->next;和newnode->prev;
此时如果先进行4的话，phead->next的地址就变成了newnode,之前的phead->next地址丢失掉。
还有一种方法是先保存* next=phead->next;然后1，2，3，4，顺序可以调换。

6.尾删

void SListPopBack(ListNode* phead)//尾删
{
	ListNode* last = phead->prev->prev;//记录尾结点的上一个结点的地址
	phead->prev = last;//头节点哨兵位的prev存入last的地址
	last->next = phead;//last的next存入phead的地址

}
1
2
3
4
5
6
7

分析：当要删除尾结点，我们可以先记录尾结点的上一个结点的地址，因为要删除尾结点，改变就是将尾结点的上一个结点last的next存phead的地址，phead的prev存入的是last的地址
除哨兵位还有一个结点的尾删剩下一个哨兵位头结点，同样适用上面的代码

7.头删

void SListPopFront(ListNode* phead)//头删
{
	ListNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
}
1
2
3
4
5
6

分析：先保存哨兵位的下一个结点地址到next,然后将phead的next中存入next->next;将next->next->prev存入phead的首地址

8.pos指针指向的结点前插

void SListInsert(ListNode* pos, int x)//pos前插
{
	ListNode* newnode = ListCreate(x);//申请新结点将地址存放在newnode变量中
	newnode->next = pos;//新结点的下一个结点保存pos指针指向节点的地址
	newnode->prev = pos->prev;//新结点的prev保存pos指针指向的节点的上一个节点的地址
	pos->prev->next=newnode;//pos指针指向的节点的前一个结点的next保存newnode指针指向的结点
	pos->prev = newnode;//pos指针指向的结点的prev保存newnode指针指向结点的地址
}
1
2
3
4
5
6
7
8

分析：

9.删除pos指针指向的结点

void SListErase(ListNode* pos)//删除pos;
{
	ListNode* last = pos->prev;//记录pos指针指向结点的前一个结点地址
	ListNode* next = pos->next;//记录pos指针指向结点的后一个结点地址
	last->next = next;//操作1
	next->prev = last;//操作2

}
1
2
3
4
5
6
7
8

分析：

10.查找链表第一个出现的x

ListNode* SListFind(ListNode* phead,int x)
{
	ListNode* cur = phead->next;//cur指针先指向phead的下一个结点的位置
	while (cur != phead)//循环遍历
	{
		if (cur->data == x)//第一次找到
		{
			return cur;返回结点数据等于x的地址



		}
		cur = cur->next;//cur指针指向下一个结点





	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

分析：类似于打印打印链表，遍历循环，从phead->next开始遍历，当cur不等于phead继续循环，如果cur->datax,就return cur的内容，也就是datax的结点地址，循环结束没有找到的话，就是该链表没有等于x的结点返回NULL;

11.双向链表的销毁

void Destroy(ListNode* phead)
{
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
1
2
3
4
5
6
7
8
9
10
11
12

分析，定义一个指针cur先指向phead的下一个结点，开始遍历，先保存cur指向结点的下一个结点的地址到next,然后释放掉cur指针指向的空间，然后让cur指向已经保存在next中下一个结点的地址，依次循环释放掉所有的结点，循环结束，释放掉哨兵位。

12.完整源码

#include 
#include 
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
ListNode* ListCreate(int x)//创建新结点
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc error");
		//return;
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
ListNode* createhead()
{
	ListNode* head = ListCreate(-1);
	head->next = head;
	head->prev = head;
	return head;
}
void ListPushBack(ListNode* phead, int x)//尾插
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	ListNode* tail = phead->prev;
	newnode->prev =tail;
	phead->prev = newnode;
	tail->next = newnode;
	newnode->next = phead;
	

}
void SListPrint(ListNode* phead)//打印链表
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d->",cur->data);
		cur = cur->next;
    }
	printf("\n");


}
void SListPushFront(ListNode* phead, int x)//头插
{
	ListNode* newnode = ListCreate(x);
	
	newnode->next = phead->next;
	phead->next->prev = newnode;
	newnode->prev = phead;
	phead->next = newnode;

}
void SListPopBack(ListNode* phead)//尾删
{
	ListNode* last = phead->prev->prev;
	phead->prev = last;
	last->next = phead;

}
void SListPopFront(ListNode* phead)//头删
{
	ListNode* next = phead->next;
	phead->next = next->next;
	next->next->prev = phead;
}
void SListInsert(ListNode* pos, int x)//pos前插
{
	ListNode* newnode = ListCreate(x);
	

	newnode->next = pos;
	newnode->prev = pos->prev;
	pos->prev->next=newnode;
	pos->prev = newnode;
}
void SListErase(ListNode* pos)//删除pos;
{
	ListNode* last = pos->prev;
	ListNode* next = pos->next;
	last->next = next;
	next->prev = last;

}
ListNode* SListFind(ListNode* phead,int x)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;



		}
		cur = cur->next;





	}
	return NULL;
}
//双链表的销毁
void Destroy(ListNode* phead)
{
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}
int main()
{
	ListNode* list;
	list = createhead();
	printf("尾插:");
    ListPushBack(list,1);
	ListPushBack(list,2);
	ListPushBack(list,3);
	ListPushBack(list,4);
	SListPrint(list);
	printf("头插:");
	SListPushFront(list, 8);
	SListPushFront(list, 7);
	SListPushFront(list, 6);
	SListPushFront(list, 5);
	SListPrint(list);
	printf("尾删:");
	SListPopBack(list);
	SListPopBack(list);
	SListPrint(list);
	printf("头删:");
	SListPopFront(list);
	SListPopFront(list);
	SListPopFront(list);
	SListPrint(list);
	printf("插入pos指向结点前面:");
	SListInsert(list->next->next, 1000);
	SListPrint(list);
	printf("删除pos指向的结点:");
	SListErase(list->next->next);
	SListPrint(list);
	printf("查找第一个x的位置并打印出来:");
	ListNode* p=SListFind(list, 8);
	printf("%d", p->data);
	printf("修改查找到的结点:\n");
	p->data = 10000;
	SListPrint(list);
	printf("销毁打印销毁后哨兵位的下一个结点的数据,如果为随机值说明已经被销毁：");
	Destroy(list);
	printf("%d",list->data);
	
	
}
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

13.编译运行