最优链表&&链表与顺序表的优缺点.

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟

🚒前言

    链表有几种结构
1.单向或者双向
2.带头或者不带头
3.循环或者不循环
这样算下来也就是八种结构

其中，最重要的就是单链表和双向带头循环链表（最优链表）
下面是双向带头循环链表的结构

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
	
}LTNode;
1
2
3
4
5
6
7
8

---

一、⛄头文件中需要提供的相关接口

//void ListInit(LTNode**pphead);
LTNode* ListInit();

void ListPrint(LTNode* phead);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPushBack(LTNode*phead,LTDataType x);
void ListPopBack(LTNode* phead);
void ListPopFront(LTNode* phead);
bool ListEmpty(LTNode*phead);
void ListInsert(LTNode* pos, LTDataType x);
void ListErase(LTNode* pos);
int ListSize(LTNode* phead);
void ListDestroy(LTNode*phead);
1
2
3
4
5
6
7
8
9
10
11
12
13

---

二、⛄初始化返回结构体的优势

    返回结构体更方便，在C语言中，避免了需要用二级指针去操控的问题

LTNode* CreateListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("CreateListNode::malloc");
		exit(-1);
	}
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

//void ListInit(LTNode**pphead)
//{
//	*pphead = CreateListNode(-1);
//	(*pphead)->next = *pphead;
//	(*pphead)->prev = *pphead;
//}

//在初始化的时候就malloc哨兵位
LTNode* ListInit()
{
	LTNode*phead = CreateListNode(-1);
	phead->next = phead;
	phead->prev = phead;
	return 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

---

三、⛄为什么这里只传一级指针就可以了呢？

在不带头的单链表中，是必须传二级指针的，因为我们知道，传一级指针是对传过来的参数的拷贝(&plist),所以想对第一个结点进行增添，修改和删除的话，并不会影响原结点的值，这只是临时的拷贝，那么带头了之后传一级就可以搞定呢？？

   void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* tail = phead->prev;
	LTNode* newnode = CreateListNode(x);
	newnode->next = tail->next;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;*/
	ListInsert(phead, x);
}
1
2
3
4
5
6
7
8
9
10
11

    传一级指针只是说不能改变phead指向的结构体的值，phead后面的结构体还是可以改变的，因为，虽然是临时拷贝，但是->next指向的结构体是一样的，除了phead指向的结构体外，其他的都能改变，因为后面的是准确的找到了，而不是说是临时拷贝，就因为不能通用，所以传二级指针,但当带了头之后，这个问题也就迎刃而解

---

四、⛄相关代码的实现

其实，增添删除只需要完成Insert和Erase就可以了，其他的都只需要复用这两个函数

void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("-1->");
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("-1\n");
}

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* tail = phead->prev;
	LTNode* newnode = CreateListNode(x);
	newnode->next = tail->next;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;*/
	ListInsert(phead, x);
}
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	/*LTNode* newnode = CreateListNode(x);
	LTNode* head = phead->next;
	newnode -> next = head;
	head->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;*/
	ListInsert(phead->next, x);

}

bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}

//链表为空就有问题了
void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));//真就没事，假就报错
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;
	free(tail);
}
//void ListPopFront(LTNode* phead)；
//一样的思路



//在pos位置之前插入x
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* newnode = CreateListNode(x);
	posPrev->next = newnode;
	newnode->next = pos;
	newnode->prev = posPrev;
	pos->prev = newnode;
}
//删除pos位置
void ListErase(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);
	pos = NULL;
	prev->next = next;
	next->prev = prev;	

}


//前面的插入删除都是O(1)，这个倒成了O(N)，不太好，所以封装成一个结构体
int ListSize(LTNode* phead)
{
	assert(phead);
	int count=0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		cur = cur->next;
		++count;
	}
	return count;
}



void ListDestroy(LTNode* phead)
{
	LTNode* cur = phead->next;
	while (cur!=phead)
	{
		LTNode* des=cur;
		cur = cur->next;
		free(des);
		des = NULL;
	}
	free(phead);
	phead = NULL;
}
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

---

五、⛄顺序表和链表的优缺点！！！

顺序表：
优点：
1.下标的随机访问（因为内存地址连续）
2.缓存利用率高（CPU高速缓存命中率高）
缺点：
1.头部或者中间想要增添或者删除，需要挪动数据，效率太低
2.扩容的问题
   a.首先，扩容就有一定程度的消耗，realloc扩容有两种可能，一是当前位置后面的空间足够，直接扩容，这个还好，二是当前位置后面的空间不够了，需要在堆区重新找一块足够的空间来进行扩容，并把现在的数据拷贝过去，再释放掉，如果数据太大，消耗是很大很大的。
   b.扩容一般是扩充1.5倍或2倍，没有被使用的空间也就造成了浪费。

链表（主要是带头双向循环）：
优点：
1.按需申请释放空间
2.插入删除的时间内复杂度都是O(1);
缺点：
1.不支持下标的随机访问，因为空间不连续
2.缓存利用率低（CPU高速缓存命中率低）

从中可以看出，链表和顺序表是相辅相成的

---

六、⛄真心流露

        😶‍🌫️😶‍🌫️😶‍🌫️。创作不易，如果看到这里，觉得有什么帮助的话，还请多多支持。