[数据结构]实现双向链表

作者： 华丞臧.
专栏：【数据结构】
各位读者老爷如果觉得博主写的不错，请诸位多多支持(点赞+收藏+关注)。如果有错误的地方，欢迎在评论区指出。

---

---

一、带头双向循环链表

在前面单向链表的学习中，不难发现单向链表有不少缺点，如改变头结点时需要传二级指针，尾删和指定位置操作时间复杂为O(N)效率较低。

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

二、带头双向循环链表接口实现

#include 
#include 
#include 
#include 

typedef int LTDataType;

typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;


//初始化
ListNode* ListInit();

// 双向链表打印
void ListPrint(ListNode* phead);

// 动态申请一个结点
ListNode* BuySListNode(LTDataType x);

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);

// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);

// 双向链表尾删
void ListPopBack(ListNode* phead);

// 双向链表头删
void ListPopFront(ListNode* phead);

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);

// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);

//判空
bool ListEmpty(ListNode* phead);

//链表长度
size_t ListSize(ListNode* phead);

// 双向链表销毁
void ListDestory(ListNode* plist);


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

2.1 双向链表的初始化、打印和销毁

初始化函数当中需要在堆上申请创建一个头结点，然后把头结点地址返回；需要注意头结点phead的next和prev指针要指向phead自己。

销毁双向链表时，注意主函数当中用来保存头结点的结构体指针plist并没有在销毁函数当中被改变，需要在主函数当中置为NULL指针,否则plist就是野指针。

//初始化
ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	phead->next = phead->prev = phead;
	return phead;
}

// 双向链表打印
void ListPrint(ListNode* phead)
{
	assert(phead);

	ListNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");

}

// 双向链表销毁
void ListDestory(ListNode* phead)
{
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		ListNode* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	free(phead);
}
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

2.2 动态申请结点

在堆上申请一块空间用来存放新插入的结点，返回申请的内存地址。

// 动态申请一个结点
ListNode* BuySListNode(LTDataType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = newNode->prev = NULL;
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.3 双向链表尾插和头插

双向链表中有一个指向前一个结点的指针prev，有一个指向下一个结点的指针next；并且头指向尾、尾指向头形成循环；这样在进行尾插时就不需要遍历链表，只需要通过头结点就可以找到尾结点，其时间复杂度为O(1)。

带头结点链表的头插不会改变链表的头结点也就不需要二级指针，其时间复杂度也是O(1)。
注意当链表为空时，不需要进行删除操作，所以断言一下看链表是否为空。

// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);//断言phead不为空

	ListNode* cur = phead->prev;
	ListNode* newNode = BuySListNode(x);

	cur->next = newNode;
	phead->prev = newNode;

	newNode->next = phead;
	newNode->prev = cur;
}



// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	//申请节点
	ListNode* newNode = BuySListNode(x);

	newNode->next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next->prev = newNode;
}

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

2.4 双向链表的尾删和头删

单向链表的尾删需要遍历找到尾结点的前一个结点；而双向循环链表的尾删可以通过头结点找到尾结点和尾结点的前一个结点，不需要遍历链表就可以进行尾删操作，其时间复杂度时O(1)。

带头结点链表的头删不会改变链表的头结点也就不需要二级指针，其时间复杂度也是O(1)

// 双向链表尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	
	ListNode* tail = phead->prev->prev;

	free(tail->next);

	phead->prev = tail;
	tail->next = phead;
}

// 双向链表头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));//断言链表不为空
	
	ListNode* next = phead->next->next;

	free(phead->next);
	phead->next = next;
	next->prev = phead;
}
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

2.5 双向链表的查找

遍历链表，把对应结点的地址返回。

// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* cur = phead->next;

	//遍历
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.6 双向链表指定位置之前插入和指定位置删除

指定位置的操作需要和查找配合使用，在pos之前插入比之单向链表无疑简单很多，不需要遍历链表就可以找到前一个结点，通过pos结点的prev指针找到前一个结点，实现指定位置之前插入，其时间复杂度为O(1)。

同样的，指定位置删除也不需要遍历链表，可以通过pos结点的prev和next指针找到前后结点，就可以实现指定位置删除，其时间复杂度为O(1)。

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);

	ListNode* newNode = BuyListNode(x);

	newNode->next = pos;
	pos->prev->next = newNode;
	newNode->prev = pos->prev;
	pos->prev = newNode;
}

// 双向链表删除pos位置的结点
void ListErase(ListNode* pos)
{
	assert(pos);

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.7 链表判空和链表长度

带头双向循环链表为空时，通过初始化函数可以得知头结点phead指向phead形成循环，也就是说链表为空时头结点下一个结点还是头结点即（phead->next == phead）。
求双向链表的长度一可以在结果体中加一个size表示链表的长度，二可以遍历链表计算链表的长度把长度返回也可以得到链表的长度大小。

//判空
bool ListEmpty(ListNode* phead)
{
	assert(phead); 

	return phead->next == phead;
}

//链表长度
size_t ListSize(ListNode* phead)
{
	assert(phead);

	size_t size = 0;
	ListNode* cur = phead->next;
	//遍历
	while (cur != phead)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.8 测试

测试带头双向循环链表接口实现的正确性。

#include "List.h"

void Test1()
{
	ListNode* plist = ListInit();

	//尾插
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPrint(plist);

	//头插
	ListPushFront(plist, 10);
	ListPushFront(plist, 20);
	ListPushFront(plist, 30);
	ListPushFront(plist, 40);
	ListPrint(plist);

	//尾删
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);

	//头删
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);

	//在pos位置之前插入
	ListInsert( ListFind(plist,10), 50);
	ListPrint(plist);

	//删除pos位置
	ListErase(ListFind(plist, 1));
	ListPrint(plist);

	ListDestory(plist);
	plist = NULL;
}

int main()
{
	Test1();
	return 0;
}
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

程序运行结果：