一、双向带头循环链表

构成

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

1.函数的定义和结构体的创建——list.h

#include
#include
#include
typedef  int datatype;
struct listNode
{
	datatype val;
	struct listNode* prev;
	struct listNode* next;
};
 struct listNode* stackinit();
 void  stackpushback(struct listNode* phead, datatype x);
 void stackprint(struct listNode* phead);
 void stackpopback(struct listNode* phead);
 void stackpushfront(struct listNode* phead, datatype x);
 void stackpopfront(struct listNode* phead);
 struct listNode*stackfind (struct listNode* phead,datatype x);
 void stackinsert(struct listNode* pos, datatype x);
 void stackdestroy(struct listNode* phead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.函数的调用——list.c

#include"list.h"
int main()
{
	struct listNode* phead= stackinit();//这里为了不使用二级指针，将结构体指针返回
	stackpushback(phead, 1);
	stackpushback(phead, 2);
	stackpushback(phead, 3);
	stackpushback(phead, 4);
	stackpopback(phead);
	stackpushfront(phead,5);
	stackpopfront(phead);
	stackprint(phead);
	struct listNode*pos=stackfind(phead, 2);
	stackinsert(pos, 4);
	stackprint(phead);
	struct listNode* pos2 = stackfind(phead, 2);
	stackerase(pos2);
	stackprint(phead);
	stackdestroy(phead);
	phead = NULL;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. 双向带头循环链表与单链表的传递参数区别

1.单链表：
单链表因为没有头节点的存在，导致在尾插时会改变链表的头节点
所以需要传递二级指针的地址即二级指针。
2.双向带头循环链表：
初始化头指针时，是需要传递二级指针，只不过用函数传回结构体指针的方式代替了，
而在后续接口则不需要传递二级指针，因为后来都是在头指针的基础上进行的，而头节点本身不会存储有效数据，并不会改变头节点本身。

4.双向带头循环链表的接口

1.初始化

struct listNode* stackinit()//初始化头节点
{
	struct listNode* phead = (struct listNode*)malloc(sizeof(struct listNode));
	phead->next = phead;//带哨兵位的头节点
	phead->prev = phead;
}
1
2
3
4
5
6

2.尾插

void stackpushback(struct listNode* phead, datatype x)//尾插
{
	struct listNode* tail = phead->prev;//tail为最后一个节点
	struct listNode* newnode = (struct listNode*)malloc(sizeof(struct listNode));
	newnode->val = x;
	tail->next = newnode;
	newnode->prev=tail;
	newnode->next = phead;
	phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

3.尾删

void stackpopback(struct listNode* phead)//尾删
{
	assert(phead);
	assert(phead->next != phead);//当只剩下头节点时 phead->next才会指向phead
	struct listNode* tail = phead->prev;
	struct listNode* cur = tail->prev;//rur为最后一个节点的前一个节点
	cur->next = phead;
	phead->prev = cur;
	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

4.头插

void stackpushfront(struct listNode* phead, datatype x)//头插
{
	struct listNode* newnode = (struct listNode*)malloc(sizeof(struct listNode));
	newnode->val = x;
	struct listNode* cur = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = cur;
	cur->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

5.头删

void stackpopfront(struct listNode* phead)//头删
{
	assert(phead);
	assert(phead->next != phead);//链表为空时
	struct listNode* prev = phead->next;
	struct listNode* next = phead->next->next;//找到第一个节点后的一个节点
	phead->next = next;
	next->prev = phead;
	free(prev);
	prev = NULL;
	
}
1
2
3
4
5
6
7
8
9
10
11
12

6.查找位置

struct listNode* stackfind(struct listNode* phead, datatype x)//查找位置
{
	struct listNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;//如果找到了返回结构体
		}
		cur = cur->next;
	}
	return NULL;//如果找不到就返回NULL
}
1
2
3
4
5
6
7
8
9
10
11
12
13

7.指定 在pos之前插入

void stackinsert(struct listNode* pos, datatype x)//指定插 在pos之前插入
{
	assert(pos);
	struct listNode* prev = pos->prev;
	struct listNode* newnode = (struct listNode*)malloc(sizeof(struct listNode));
	newnode->val = x;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;

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

8.指定删

void stackerase(struct listNode* pos)//指定删
{
	assert(pos);
	struct listNode* prev = pos->prev;
	struct listNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
1
2
3
4
5
6
7
8
9
10

9.内存销毁

void stackdestroy(struct listNode* phead)//内存销毁
{
	struct listNode* cur = phead->next;
	while (cur != phead)
	{
		struct listNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;//因为此时传过来是一级指针不能影响会传回去的phead 所以可以手动在外面置NULL
}

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

10.打印

void stackprint(struct listNode* phead)//打印
{
	struct listNode* cur = phead->next;
	while (cur != phead)//此时因为是循环链表 ，所以不要写成NULL
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}

1
2
3
4
5
6
7
8
9
10
11

三、链表与顺序表的不同点

1.顺序表：
在物理上是连续的
优点： 支持随机访问。
缺点：(1)任意位置插入或者删除时，可能需要挪动元素，效率低。
(2)在动态开辟空间时，会造成一定的浪费。

2.链表：
逻辑上是来连续的，物理上的不连续。
优点:(1)任意位置插入或者删除，不会挪动元素，只会改变指针指向，(2)没有容量的概念，不会造成空间浪费。
缺点：不支持随机访问