我们将形如A1,A2,…,AN的结构称之为表,这个表的大下是N,大小为0的表是空表。表可以采用简单的数组实现方式,但是数组实现表时还需要对表的大小进行最大值进行估计,通常估计的较大,这会造成存储空间浪费。另外,数组实现表时,其对于删除和插入的开销是昂贵的,例如在0位置插入,需要将整个数组后移一个位置。所以简单的数组一般不用来实现表。
为了避免插入和删除的开销,需要允许表可以存储在不连续的空间上,而链表就是这样的结构。
以下介绍了链表的C语言代码实现,代码链接。
0 基本概念
链表的基本样式如下图所示,在C语言中,我们可以用指针表示图中所示的箭头。如图所示,链表分为单向链表和双向链表(还有循环链表,这里未表),双向链表相对于单项链表,以倒序扫描链表的时候会更方便,但是增加了空间的需求和插入、删除的开销。下面将介绍双向链表的代码实现。
1 创建链表
上图所示的链表没有表头,而没有表头会带来问题:从第一个位置进行插入和删除都需要特殊的判断和处理。为解决这个问题,我们引入一个表头或哑节点。首先,我们定义每个节点的结构体为node,如下,两个指针分别指向前驱和后继节点,数据用void类型的指针表示,可以指向任意类型的数据。
1 | typedef struct node { |
定义表头或哑节点如下,其中两个指针分别指向链表的头节点和尾节点,带有数据为节点计数cnt,如下,这个头节点也就用来表征此链表,故而用list给其命名。
1 | typedef struct list { |
接下来创建一个链表,这很简单,就是一个空链表,没有数据节点,头和尾指针都指向NULL,如下图所示。
代码如下:
1 | list_t *list_create(void) |
2 插入元素
2.1 尾部插入
在链表尾部添加元素的逻辑如下所示,当在链表尾部添加一个节点时,有以下四个步骤:
- 1、将该节点的后继节点(node->next)设为空(NULL);
- 2、如果链表为空,即此节点为第一个节点,将链表头指针(list->head)指向此节点;若链表不为空,则将链表尾指针指向的节点的后继节点(list->tail->next)设为此节点;
- 3、将此节点的前驱节点设为链表的尾指针指向的节点;
- 4、将链表的尾指针指向此节点;
其基本逻辑如下图所示:
代码如下所示,函数参数为此链表及添加的数据,当代码返回0时添加成功,返回-1时失败。
1 | int list_append(list_t *list, void *data) |
2.2 头部插入
在链表头部添加元素的逻辑如下所示,当在链表头部添加一个节点时,有以下四个步骤:
- 1、将该节点的前驱节点(node->prev)设为空(NULL);
- 2、如果链表为空,即此节点为第一个节点,将链表尾指针(list->tail)指向此节点;若链表不为空,则将链表头指针指向的节点的前驱节点(list->head->prev)设为此节点;
- 3、将此节点的后继节点设为链表的头指针指向的节点;
- 4、将链表的头指针指向此节点;
其基本逻辑如下所示:
代码如下所示:
1 | int list_prepend(list_t *list, void *data) |
2.3 中间插入
在中间插入元素有两种格式,一种是在特定位置插入,另一种是在特定的node前(或后)插入,下面将代码实现这两种不同的插入方式。
2.3.1 在特定位置插入
类似于数组,我们将链表的位置定义为0~Count-1(Count表示链表的节点数),即我们可以将数据插入位置pos的范围为0~Count(取0时即插入到头,取Count时即表示插在末尾)。插入的逻辑如下:
- 1、如果pos为0,即调用list_prepend函数;如果pos为list->cnt,则调用list_append函数;并返回;
- 2、寻找到位置为pos的节点,记为f_node;
- 3、将插入节点(记为i_node)的前驱节点设为f_node的前驱节点,后继节点设置为f_node;
- 4、将f_node前驱节点的后继节点设为i_node;
- 5、将f_node的前驱节点设为i_node;
代码如下: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
34int list_insert_at(list_t *list, unsigned int pos, void *data)
{
int i;
node_t *f_node;
node_t *i_node;
if (!list || !data || pos > list->cnt) return -1;
/* step 1 */
if (pos == 0)
return list_prepend(list, data);
if (pos == list->cnt)
return list_append(list, data);
/* step 2 */
f_node = list->head;
for (i = 0; i < pos && f_node; i++)
f_node = f_node->next;
if (!f_node) return -1;
i_node = malloc(sizeof(node_t));
if (!i_node) return -1;
/* step 3-5 */
i_node->data = data;
i_node->prev = f_node->prev;
i_node->next = f_node;
f_node->prev->next = i_node;
f_node->prev = i_node;
list->cnt++;
return 0;
}
2.3.2 在特定节点前插入
有以下步骤:
- 1、判断特定节点是否是链表头节点,如果是,直接调用list_prepend函数,并直接返回;
- 2、将插入节点的前驱节点设为特定节点的前驱节点,后继节点设置为特定节点;
- 3、将特定节点前驱节点的后继节点设置为插入节点;
- 4、将特定节点的前驱节点设置为插入节点;
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int list_insert_before(list_t *list, node_t *node, void *data)
{
node_t *i_node;
if (!list || !node || !data)
return -1;
/* step 1 */
if (node == list->head)
return list_prepend(list, data);
i_node = malloc(sizeof(node_t));
if (!i_node) return -1;
/* step 2-4 */
i_node->data = data;
i_node->prev = node->prev;
i_node->next = node;
node->prev->next = i_node;
node->prev = i_node;
list->cnt++;
return 0;
}
2.3.3 在特定节点后插入
原理类似于2.3.2,有以下步骤:
- 1、判断特定节点是否是链表尾节点,如果是,直接调用list_append函数,并直接返回;
- 2、将插入节点的前驱节点设为特定节点,后继节点设置为特定节点的后继节点;
- 3、将特定节点后继节点的前驱节点设置为插入节点;
- 4、将特定节点的后继节点设置为插入节点;
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int list_insert_after(list_t *list, node_t *node, void *data)
{
node_t *i_node;
if (!list || !node || !data)
return -1;
/* step 1 */
if (node == list->tail)
return list_append(list, data);
i_node = malloc(sizeof(node_t));
if (!i_node) return -1;
/* step 2-4 */
i_node->data = data;
i_node->prev = node;
i_node->next = node->next;
node->next->prev = i_node;
node->next = i_node;
list->cnt++;
return 0;
}
3 删除(提取)元素
删除有许多中不同的操作,譬如删除已知节点并提取数据、删除对应数据的节点,下面就代码实现这两种删除或提取数据方式。
3.1 已知节点
对于链表中的已知节点,我们提取数据的同时删除节点。基本逻辑如下:
- 1、如果被删除节点是头节点,则将头指针指向该节点的后继节点;若不是头节点,则将该指针的前驱节点的后继节点设为该节点的后继节点;
- 2、如果被删除节点是尾节点,则将尾指针指向该节点的前驱节点;若不是尾节点,则将该指针的后继节点的前驱节点设为该指针的前驱节点;
代码如下:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25void *list_retrieve_data(list_t *list, node_t *node)
{
void *data;
if (!list || !node)
return NULL;
/* step 1 */
if (node == list->head)
list->head = node->next;
else
node->prev->next = node->next;
/* step 2 */
if (node == list->tail)
list->tail = node->prev;
else
node->next->prev = node->prev;
list->cnt--;
data = node->data;
free(node);
return data;
}
3.2 已知位置
对于链表中已知位置的节点,先找到该位置的节点,再调用list_retrieve_data函数删除该节点,代码如下:
1 | void *list_retrieve_data_at(list_t *list, unsigned int pos) |
3.3 删除数据
对相关数据的删除,应当传入对应数据的指针,遍历指针找到该数据的节点后,再调用list_retrieve_data函数删除该节点,成功返回0,失败返回-1,代码如下。list_for_each_entry可遍历链表,详见5.2。
1 | int list_remove_data(list_t *list, void *data) |
3.4 销毁整个链表
当我们想要销毁整个链表的时候,我们需要删除所有的节点并释放内存,最后再释放头节点的内存,有如下代码。以下用法有点危险的就是,如果data所在内存是通过动态申请的堆空间,则以下用法很可能造成data数据的内存泄漏,建议当data内存通过动态申请得到时,通过循环list_retrieve_data函数取出数据后一一释放内存后再调用list_destory函数。
1 | void list_destory(list_t *list) |
4 查找
4.1 特定位置查找
下面给出已知位置,返回对应节点的数据,与list_retrieve_data_at函数的区别在于其不删除节点,只提取数据,代码如下:
1 | void *list_get_data(list_t *list, unsigned int pos) |
特殊地,当我们想取头或者尾的数据时有以下代码:
1 | void *list_get_head(list_t *list) |
4.2 自定义方法查找
用户可以将函数指针作为查找参数,自行构造match函数,用于匹配查找,具体形式如下,首先在list.h文件中声明一个类型:
1 | typedef int (*match_t)(void *, void *); |
然后在源文件list.c中添加如下代码:
1 | void *list_find(list_t *list, void *key, match_t match) |
5 其它功能
5.1 返回链表大小
在初始化时,我们将链表大小(list->cnt)初始化为0,当添加数据时,会将链表大小加1,删除时会减1,因此可以通过该数值表征链表大小,代码如下。当链表不存在时,返回-1;当链表存在时,返回链表大小(0表示链表无数据节点,只有头节点)。
1 | int list_size(list_t *list) |
5.2 链表遍历
在上述代码中,我们已经用到了链表遍历的函数,即list_for_each_entry。其定义如下所示,pos表示数据(之所以不用data表示,是因为会将node成员data识别为此data),node表示节点,这两个参数都是遍历过程中的变量,list表示被遍历的表。
1 |
|
5.3 安全地遍历链表
在5.2中的链表遍历中,如果我们在操作过程中删除了此节点,将不能继续向下遍历,此时,我们可以采用以下的安全遍历方法,将下一节点的指针信息暂存在nex(之所以不用next表示,是因为会将node成员next识别为此next)指针中,使得遍历可以继续走下去。
1 |
|
6 链表实现队列
队列是一种先进先出的数据结构,利用以上链表,可以简单地实现队列(栈亦可)功能,如以下所示,可以实现队列的创建、入队、出队和销毁。首先创建一个类似于头节点的队列头节点,结构定义完全可以相同,然后利用链表的一系列函数即可实现功能。
1 | typedef struct queue { |