链表的概念：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：
一个是存储数据元素的数据域，
另一个是存储下一个结点地址的指针域。
而单链表的指针域只有一个指针，即指向后面结点的指针。
单链表的代码定义：为了方便代码演示，这里我选择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;
}
