图解无头单向非循环链表和带头双向循环链表_无头单向非循环链表与带头双向循环链表的优缺点

链表是一种重要的数据结构,其概念：链表是一种 物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链
接次序实现的 。
这里介绍两种链表:

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

单链表(单向不带头)

数据节点和头结点

typedef int Data;        //数据类型
typedef struct lists{
       //自定义单链表结构体
	Data _data;
	struct lists* _next;
}lists;

//自定义头结点
typedef struct firstlist{
   //用来找到并操作链表,必须从头开始
	struct lists* _head;
}firstlist;
1
2
3
4
5
6
7
8
9
10
11
12

新增节点函数和初始化

//结构体初始化
void init(firstlist* flist){
   
	if (flist == NULL){
   
		return flist;
	}
	flist->_head = NULL;   //数据设为空
}

lists* xinzeng(Data _data){
   //将一个数据传入一个新链表,返回新链表的地址
	lists* newlist = (lists*)malloc(sizeof(lists));
	newlist->_data = _data;
	newlist->_next = NULL;
	return newlist;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

基本操作

1.尾插

//尾插
void weicha(firstlist* lit,Data data){
   //将data尾插到lit链表中
	//传firstlist是因为知道头结点地址就可以操作链表了
	if (lit == NULL){
   //如果是空链表直接返回null
		return;
	}
	//空链表插入第一个数据
	if (lit->_head == NULL){
   
		lit->_head = xinzeng(data);
	}
	else{
   //不是空链表则需要遍历
		lists* list = lit->_head;
		//因为_head是第一个元素的地址,所以要lists*
		while (list->_next != NULL){
   
			list = list->_next;
		}
		list->_next = xinzeng(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

2.尾删

//尾删
void weishan(firstlist* flist){
   
	if (flist == NULL||flist->_head==NULL){
   
		return;
	}
	//用两个变量one 和two来操作
	lists* one = flist->_head;
	lists* two = NULL;
	if (one->_next != NULL){
   
		two = one;
		one = one->_next;
	}
	free(one);
	if (two == NULL){
   //这种是只有头节点,two就没变
		flist->_head = NULL;
	}
	else{
   
		two->_next = 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

3.头插

//头插
void toucha(firstlist* flist,Data data){
   
	if (flist == NULL){
   
		return;
	}
	if (flist->_head == NULL){
   
		flist->_head = xinzeng(data);
	}
	else{
   
		lists* b = xinzeng(data);
		b->_next = flist->_head;
		flist->_head = b;	
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.头删

//头删
void toushan(firstlist* list){
   
	if (list==NULL){
   
		return;
	}
	if (list->_head == NULL){
   
		return;
	}
	else{
   
		struct lists* next = list->_head->_next;
		free(list->_head);
		list->_head = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.任意位置新增节点

//在哪新增一个节点
void jiaru(lists* a,Data data){
   //用不到头节点所以直接操作
	lists* list = 
1
2
3