我们知道在C语言里数组可以存储大量相同数据类型的数据，但是数组有个很明显的缺点就是大小固定不够灵活，我们必须知道数据量的大小，很多时候我们并不知道数据量有多少，这个时候数组就明显不适合了。现在需要一种数据结构能灵活存储数据，随时可以存储和删除数据，而且并不需要估计数据量多少。单链表能满足我们的需求，且是一种最简单的链状数据结构。下面我们看一下链表结点是如何定义的。
typedef struct list {
struct list* next;
int data;
}list_t;
这里我们通过typedef自定义一个结构体数据类型list_t，在list_t里我们定义了一个next指针用于指向下一个结点，这里我要说明一下为什么next指针要定义成struct list类型，而且为什么可以这样用，后面的数据结构学习，我们会大量这样使用。在我们定义next指针之前已经声明了结构体list，相当于做了前置声明，既然已经声明了，那么自然就可以使用了。
现在我们声明一些链表操作函数，插入、删除、查找某个位置的结点、删除某个结点、销毁链表，打印链表结点数据。
extern list_t *new_list_node(int data); //新建一个结点
extern list_t *list_add(list_t *list, int data); //头插法插入一个结点
extern void list_destroy(list_t *list); //销毁链表
extern list_t *list_delete_node(list_t *list, list_t *node); //删除某个链表
extern list_t *list_delete(list_t *list, int data); //删除某个位置的结点
extern list_t *list_index_of(list_t *list, int index); //查找某个位置的结点
extern void list_print(list_t *list); //打印链表数据
可以看到很多链表函数我们都会返回一个list_t类型指针，其实这个是链表头结点。操作函数如何实现主要看个人风格，有的人喜欢传入二级指针形参达到修改链表的目的，当然也可以。
单链表操作函数实现- 新建链表结点
list_t* new_list_node(int data) {
list_t* node = (list_t*)malloc(sizeof(list_t));
if (!node) {
return NULL;
}
node->data = data;
node->next = NULL;
return node;
}
在链表结点函数定义里，我们通过malloc申请一块结点内存，接下来就是对结点进行初始化，next指针一定要置为NULL。
- 链表插入结点
list_t *list_add(list_t* list, int data) {
if (!list) {
return NULL;
}
list_t* node = new_list_node(data);
node->next = list; //采用头插法插入结点
return node;
}
每插入一个链表结点都要申请一块结点内存，并将数据存储在结点里。在这里我们采用头插法将结点插入链表，头插法则是每次从链表头部插入一个结点，只需要O(1)时间复杂度。每插入一个新结点node都需要将node的next指针指向链表头结点，那么node就变成了链表头结点，最后将node结点返回作为链表头。
- 销毁链表
void list_destroy(list_t* list) {
//空链表无需销毁
if (!list) {
return;
}
list_t* head = list; //将头结点保存到head
while (head != NULL) {
list = list->next; //循环遍历链表
free(head); //释放结点内存
head = NULL;
head = list; //head重新保存链表头结点（这里很关键！！！）
}
}
销毁操作一定要用另外一个指针保存即将被销毁的结点，然后链表头结点不断的遍历。
- 删除指定结点
list_t *list_delete_node(list_t* list, list_t* node) {
if (!list) {
return NULL;
}
if (!node) {
return list;
}
list_t* head = list;
list_t* prev = NULL;
while (list != NULL && list != node) {
prev = list; //保存目标结点的前一个结点
list = list->next;
}
//找不到目标结点
if(list == NULL){
return head;
}
//目标结点是头结点
if (list == head) {
head = head->next; //目标结点的下一个结点是头结点
free(list); //销毁目标结点
list = NULL;
}
//目标结点是尾结点，尾结点的next指针是NULL
else if(list->next == NULL){
prev->next = NULL; //目标结点的前一个结点next指针置为NULL
free(list); //释放目标结点
list = NULL;
}
//目标结点是中间结点
else {
prev->next = list->next; //目标结点的前一个结点的next指针指向目标结点的下一个结点
list->next = NULL;
free(list); //释放目标结点
list = NULL;
}
return head; //返回链表头结点
}
删除结点时有几个需要注意的地方：
- 需要一个指针保存目标结点的上一个结点
- 需要充分考虑目标结点是头结点还是尾结点还是链表的中间结点。
- 删除指定值的结点
list_t *list_delete(list_t* list, int data) {
if (!list) {
return NULL;
}
list_t* head = list;
list_t* prev = NULL;
//遍历查找目标结点
while (list != NULL && list->data != data) {
prev = list; //保存目标结点的前一个结点
list = list->next;
}
//找不到目标结点
if (!list) {
return head;
}
//目标结点是头结点
if (list == head) {
head = head->next; //原头结点的下一个结点变为新的头结点
free(list); //释放目标结点
list = NULL;
}
//目标结点是尾部结点
else if (list->next == NULL) {
prev->next = NULL; //目标结点的前一个结点next指针置为NULL
free(list); //销毁目标结点
list = NULL;
}
//目标结点是中间结点
else {
prev->next = list->next; //目标结点的前一个结点的next指针指向目标结点的下一个结点
free(list);
list = NULL;
}
return head; //返回头结点
}
- 查找指定位置的结点
list_t *list_index_of(list_t* list, int index) {
if (!list || index < 0) {
return NULL;
}
int list_index = 0;
while (list != NULL && list_index < index) {
list_index ;
list = list->next;
}
return list;
}
- 打印链表结点数据
void list_print(list_t* list) {
if (list == NULL) {
return;
}
while (list != NULL) {
printf("%d, ", list->data);
list = list->next;
}
printf("\n");
}
最后我们写一个小程序验证我们的链表实现是否正确
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
int main(int argc, char* argv[]) {
list_t* list = new_list_node(1); //新建链表头结点
//插入结点
list = list_add(list, 2);
list = list_add(list, 5);
list = list_add(list, 6);
list = list_add(list, 10);
list = list_add(list, 16);
list = list_add(list, 15);
list_print(list); //打印链表
list = list_delete(list, 10);
list_print(list); //打印链表
list_t* node = list_index_of(list, 3); //找到索引3的链表结点（索引从0开始）
printf("node->data = %d\n", node->data);
list = list_delete_node(list, node); //删除结点
list_print(list); //打印链表
list_destroy(list); //销毁链表
list = NULL;
return 0;
}
编译运行输出：
15, 16, 10, 6, 5, 2, 1,
15, 16, 6, 5, 2, 1,
node->data = 5
15, 16, 6, 2, 1,
链表实现代码完全正确。
