链表的概念：

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。

每个结点包括两个部分：

一个是存储数据元素的数据域，

另一个是存储下一个结点地址的指针域。

而单链表的指针域只有一个指针，即指向后面结点的指针。

单链表的代码定义：为了方便代码演示，这里我选择int类型作为单链表数据的类型。

typedef int Type;

/*链表节点结构的声明*/

typedef struct 

{

Type data;    //数据域：用于存储数据

Node *next;    //指针域：用于指向下一个阶段

}Node;

/*整个链表结构的声明*/

typedef struct LinkList

{

Node *head;    //链表的头节点指针

Node *end;    //链表的尾结点指针

int lenth;    //链表的长度

}LL;

定义好单链表的结构后，我们就可以开始函数的实现了。

//初始化单链表

LL *list_init()

{

LL * temp = (LL *)malloc(sizeof(LL));

if (temp == NULL)

{

return NULL;

}

temp->head = NULL;    //链表头节点指针置空(初始化)

temp->end = NULL;    //链表尾结点指针置空(初始化)

temp->lenth = 0;    //链表长度置0(初始化)

return temp;

}

//2、初始化单链表节点

Node *node_init(Type val)

{

Node *temp = (Node *)malloc(sizeof(Node));

if (temp == NULL)

{

return NULL;

}

temp->data = val;//链表节点的数据域赋值

temp->next = NULL;//(*temp).next = NULL

return temp;

}

//单链表的打印输出

#define T "%d->"

void list_print(LL *list)

{

if (list == NULL)

{

printf("链表空间不存在！\n");

return;

}

if (list->head == NULL)

{

printf("链表为空！\n");

return;

}

for (Node *temp = list->head; temp != NULL; temp = temp->next)

{

printf(T, temp->data);

}

printf("NULL\n");

}

//递归逆序输出

void list_print2(Node * head)

{

if (head == NULL)

{

printf("NULL");

}

else

{

list_print2(head->next);

printf("<-%d", head->data);

}

}

    //单链表节点的尾端插入

void list_insert_end(LL *list, Type val)//尾插法

{

if (list == NULL)

{

printf("插入错误，链表空间不存在！\n");

}

if (list->head == NULL)//如果是空链表

{

list->head = list->end = node_init(val);//第一个链表节点，其既是头部也是尾部

list->lenth++;//链表长度+1

}

else

{

list->end->next = node_init(val);//创建一个新节点，连接到链表当前的末尾

list->end = list->end->next;//新节点成为新的尾部

list->lenth++;//链表长度+1

}

}

//指定位置插入

void list_insert(LL *list, int index, Type val)//index 指定位置

{

if (list == NULL)

{

printf("插入错误，链表空间不存在！\n");

return;

}

if (index > list->lenth + 1 || index <= 0)

{

printf("插入位置错误！\n");

return;

}

if (index == list->lenth + 1)//如果插入位置刚好比链表长度打一个

{

list_insert_end(list, val);//从尾部插入

return;

}

if (index == 1)//如果在当前头节点之前插入

{

Node * New = node_init(val);//创建新插入的节点

New->next = list->head;//新节点指向当前头节点

list->head = New;//新节点成为新的头部

list->lenth++;

return;

}

Node *temp = list->head;

for (int i = 1; i < index - 1; i++)

{

temp = temp->next;    //找到插入位置前一个节点

}

Node * New = node_init(val);    //创建新插入的节点

New->next = temp->next;    //新节点连接插入位置之后的节点

temp->next = New;    //链表插入位置之前的节点连接上新节点

list->lenth++;

}

//单链表节点的删除

Type list_delete(LL *list, int index)

{

if (list == NULL)

{

printf("删除错误，链表空间不存在！\n");

return 0;

}

if (index > list->lenth || index <= 0)

{

printf("删除位置错误！\n");

return 0;

}

if (index == 1)

{

Node *temp = list->head;//记录当前头部

list->head = list->head->next;//第二个节点成为新的头部

Type val = temp->data;

free(temp);

list->lenth--;

return val;

}

if (index == list->lenth)

{

Node *temp = list->head;

for (int i = 1; i < index - 1; i++)

{

temp = temp->next;    //找到删除位置前一个节点

}

Type val = temp->next->data;

free(temp->next);

temp->next = NULL;    //链表末尾指向空

list->end = temp;    //倒数第二个节点成为新的尾部

list->lenth--;

return val;

}

Node *temp1 = list->head;

Node *temp2;

for (int i = 1; i < index - 1; i++)

{

temp1 = temp1->next;//找到删除位置前一个节点

}

Type val = temp1->next->data;//记录被删除节点的数据

temp2 = temp1->next;//temp2指向被删除节点

temp1->next = temp2->next;//删除位置前的节点跳过被删除的节点，指向下下一个节点

free(temp2);//释放被删除节点

list->lenth--;

return val;

}

//获取单链表指定位置上的数据

Type list_get(LL *list, int index)

{

if (list == NULL)

{

printf("错误，链表空间不存在！\n");

return 0;

}

if (index > list->lenth || index <= 0)

{

printf("位置错误！\n");

return 0;

}

Node *temp = list->head;

for (int i = 1; i < index; i++)

{

temp = temp->next;

}

return temp->data;

}

//链表节点数据的修改

void list_modify(LL *list, int index, Type val)

{

if (list == NULL)

{

printf("错误，链表空间不存在！\n");

return;

}

if (index > list->lenth || index <= 0)

{

printf("位置错误！\n");

return;

}

Node *temp = list->head;

for (int i = 1; i < index; i++)

{

temp = temp->next;

}

temp->data = val;    //将对应位置节点上的值修改为指定的数据

}

//链表的销毁

void list_delete_all(LL **list)

{

if (*list == NULL)

{

printf("错误，链表空间不存在！\n");

return;

}

if ((*list)->head == NULL)

{

    free(*list);

}

Node *temp1 = (*list)->head, *temp2;

for (; temp1 != NULL;)    //循环释放链表中的各个数据节点

{

temp2 = temp1;

temp1 = temp1->next;

free(temp2);

}

printf("链表已清空！\n");

free(*list);    //释放整个链表

*list = NULL;

}