[数据结构与算法]猿创征文｜数据结构-单链表详解（含完整代码）

??引语

数据结构-顺序表详解上一篇文章我写的是线性表的顺序存储，它有一个缺点就是当我们进行插入和删除时，需要移动大量的元素，显然会耗费大量的时间，那有没有办法解决呢？今天这篇文章将会给你带来答案！

😍1.线性表的链式存储结构

?? 1.1定义

🐕 线性表链式存储结构的特点是： 用任意一组存储单元存储线性表的数据元素（这组存储单元可以是连续，也可以是不连续的）。这就意味着这些元素可以存储在内存未被占用的任意位置。

🐖 因此为了表示每个数据元素a(i)与其直接后继元素数据元素a(i+1)之间的逻辑关系，对数据元素a(i)来说，除了存储其本身信息外，还需要存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息构成数据元素a(i)的存储映像，称为节点（node) 。它包括两个域：其中存储数据元素信息的域称为数据域 ；存储直接后继存储位置的域称为指针域 。指针域中存储的信息称为指针或链。

🐱n个节点（ai的存储映像）连接成一个链表,即为线性表的链式存储结构。又由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。

🐵单链表正是通过每个节点的指针域将线性表中的数据元素按其逻辑次序链接在一起，如下图
该图片来源于《大话数据结构–作者程杰》

🙈图片解释：

??1.2首元节点+头节点+头指针

💕1.2.1首元节点

首元节点指链表中存储第一个数据元素a1的节点（简称第一节点）。

💕1.2.2头节点

头节点是在首元节点之前附设的一个节点，其指针域指向首元节点。头节点的数据域可以不存储任何信息，也可以存储与数据元素类型相同的其他附加信息。
头节点的作用：
（1） 便于首元节点的处理
（2） 便于空表和非表的统一处理

💕1.2.3头指针

头指针是指向链表第一个节点的指针。若链表设有头节点，则头指针所指节点为线性表的头节点；若链表没有头节点，则头指针所指向节点为线性表的首元节点。

??1.3单链表基本操作的实现

💕1.3.1 定义和节点的存储结构

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define OK 1
#define ERROR 0
typedef int ElemType;   /*ElemType的类型根据实际情况而定*/
typedef int Status;

/*线性表单链表的存储结构*/
typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node;
typedef struct Node* LinkList;  /*定义LinkList*/

💕1.3.2 初始化

【算法步骤】

①生成新节点作为头节点，用头指针L指向头节点。
②头节点的指针域置空。

【算法描述】【伪代码】

/*初始化*/
Status InitList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(Node));    //创建头节点，并使头指针指向该节点
	if (!(*L))
		return ERROR;     //内存分配失败，返回ERROR
	(*L)->next = NULL;
	return OK;
}

💕1.3.3 读取

【算法步骤】

• ①用指针p指向首元节点，用j做计数器初值赋值为1
• ②从首元节点开始依次顺着链域next向下访问，只要指向当前节点的指针p不为空（NULL），并且没有到达序号为i的节点，则循环执行以下操作：
• p指向下一个节点；
• 计数器j相应加1
• ③退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i>n&&i<=0）,取值失败返回ERROR；
  否则取值成功，此时j=i时，p所指的节点就是要找的第i个节点，用参数e保存当前节点的数据域，返回OK

【算法描述】【伪代码】

/*读取*/
/*初始条件:顺序线性表L已存在，i>=1&&i<=ListLength(L)*/
/*操作结果:用e返回L中第i个元素的值*/
Status GetElem(LinkList L, int i, ElemType* e)
{
	int j;
	LinkList p;         /*声明一节点p*/
	p = L->next;        /*让p指向链表L的第一个节点*/
	j = 1;              /*j为计数器*/
	while (p && j < i)     /*p不为空，j不等于i，循环继续*/
	{
		p = p->next;          /*让p指向下一节点*/
		++j;             
	}
	if (!p || j > i)  return ERROR;   /*第i个元素不存在*/
	*e = p->data;
	return OK;
}

【算法分析】

该算法基本操作比较j和i并后移指针p，while语句执行次数与读取位置i有关；当（i>=1&&i<=n）,执行次数为i-1；当i>n,执行次数为n。

最好的情况：0次。
最坏的情况：n次。
时间复杂度为：O(n)。

💕1.3.4 查找

🤦?♀?（1）根据数据值查找地址

【算法步骤】

①用指针p指向首元节点。
②从首元节点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p所指节点的数据域不等于给定值e，则循环执行以下操作：p指向下一个节点。
③返回p。若查找成功，p此时指向节点的地址值，若查找失败，则p的值为NULL。

【算法描述】

//根据数据查找地址
LinkList LocateElem(LinkList L, ElemType e)
{ //在带头节点的单链表L中查找值为e的元素
	LinkList p;
	p = L->next;      //初始化，p指向首元节点
	while (p && p->data != e)    //顺链域向后找直到p为空或者p所指向的节点的数据域等于e
	{
		p = p->next;             //p指向下一个节点
	}
	return p;                    //查找成功返回值为e的节点地址p，查找失败p为NULL
}

【算法分析】

主要时间耗费在while语句执行次数（i-1）上，而执行次数与e的值有关。

最好的情况：执行0次。
最坏的情况：执行n次。
时间复杂度：O(n)。

🤦?♂?（2）根据数据值查找位序

【算法描述】

①用指针p指向首元节点。
②从首元节点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p所指节点的数据域不等于给定值e，则循环执行以下操作：p指向下一个节点,j加1。
③若p为空指针，返回ERROR；否则返回位序j。

【算法描述】【伪代码】

//根据数据查找位序
Status GetLocate(LinkList L, ElemType e)
{
	int j;
	LinkList p;         /*声明一节点p*/
	p = L->next;        /*让p指向链表L的第一个节点*/
	j = 1;              /*j为计数器*/
	while ((p->data) != e&&(p->next)!=NULL)
	{
		p = p->next;          /*让p指向下一节点*/
		++j;
	}
	if (!p )  return ERROR;   /*第i个元素不存在*/
	return j;                /*返回位序*/
}

【算法分析】

主要时间耗费在while语句执行次数（i-1）上，而执行次数与e的值有关。
最好的情况：执行0次。
最坏的情况：执行n次。
时间复杂度：O(n)。

💕1.3.5 插入

【算法步骤】

将值为e的新节点插入表的第i个位置，即插入节点ai-1与ai之间
①查找节点ai-1并由指针p指向该节点
②生成一个新节点s
③将新节点s的数据域置为e
④将新节点s的指针域指向节点ai
⑤将节点p的指针域指向新节点*s

【算法描述】【伪代码】

/*插入*/
/*初始条件:顺序线性表L已存在，i>=1&&i<=ListLength(L)*/
/*操作结果:在L中第i个位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert(LinkList* L, int i, ElemType e)
{
	int j;
	LinkList p, s;
	p = *L;
	j = 1;
	while (p && j < i)     /*p不为空，j不等于i，循环继续*/
	{
		p = p->next;          /*让p指向下一节点*/
		++j;
	}
	if (!p || j > i)  return ERROR;   /*第i个元素不存在*/
	s = (LinkList)malloc(sizeof(Node));   /*生成新节点*/
	s->data = e;
	s->next = p->next;        /*将p的后继节点赋给s的后继*/
	p->next = s;              /*将s赋给p的后继*/
	return OK;
}

【算法分析】

主要时间耗费在while语句执行次数（i-1）上，而执行次数与插入位置i有关。

最好的情况：执行0次。
最坏的情况：执行n-1次。
时间复杂度：O(n)。

💕1.3.6 删除

【算法步骤】

删除单链表的第i个节点ai的具体过程
①查找节点ai-1并由指针p指向该节点
②临时保存待删除节点ai的地址在q中，以备释放
③将节点*p的指针域指向ai的直接后继节点
④释放节点ai的空间

【算法描述】【伪代码】

/*删除*/
/*初始条件:顺序线性表L已存在，i>=1&&i<=ListLength(L)*/
/*操作结果:删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, q;
	p = *L;
	j = 1;
	while (p->next && j < i)   /*遍历寻找第i个元素*/
	{
		p = p->next;
		++j;
	}
	if (!(p->next || j > i))  return ERROR;   /*第i个元素不存在*/
	q = p->next;
	p->next = q->next;                /*将q后继赋给p的后继*/
	*e = q->data;                    /*将q中的数据赋给*e*/
	free(q);                         /*让系统回收该节点，释放内存*/
	return OK;
}

【算法分析】

主要时间耗费在while语句的执行次数上，而执行次数与删除位置i有关。

最好的情况：执行0次。
最坏的情况：执行n次。
时间复杂度：O(n)。

💕1.3.7 整表创建

🤦?♂?（1）头插法

线性表（a,b,c,d,e）头插法创建过程，因为每次插入在链表的头部，所以应该逆位序输入数据，依次输入e、d、c、b、a,输入顺序与线性表的逻辑是相反的。

【算法步骤】

①创建一个只有头节点的空链表。
②根据待创建链表包括的元素个数n，循环n次执行以下操作：

• 生成一个新节点*p
• 输入元素值赋给新节点*p的数据域
• 将新节点*p插入到头节点之后

【算法描述】【伪代码】

/*第一种形式*/
/*头插法*/
/*自己输入n个元素的值，建立带表头节点的单链线性表L（头插法）*/
void CreateListHead(LinkList* L, int n)
{
	LinkList p;
	int i;
	//srand(time(0));                   /*初始化随机种子*/
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                       /*先建立一个带头结点的单链表*/
	for (i = 0;i < n;i++)
	{
		p = (LinkList)malloc(sizeof(Node));  /*生成新节点*/
		scanf("%d", &(p->data));
		//p->data = rand() % 100 + 1;          /*随机生成100以内的数字*/
		p->next = (*L)->next;               
		(*L)->next = p;                    /*插入到表头*/
	}
}


/*第二种形式*/
/*头插法*/
/*随机产生n个元素的值，建立带表头节点的单链线性表L（头插法）*/
void CreateListHead(LinkList* L, int n)
{
	LinkList p;
	int i;
	srand(time(0));                   /*初始化随机种子*/
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                       /*先建立一个带头结点的单链表*/
	for (i = 0;i < n;i++)
	{
		p = (LinkList)malloc(sizeof(Node));  /*生成新节点*/
		//scanf("%d", &(p->data));
		p->data = rand() % 100 + 1;          /*随机生成100以内的数字*/
		p->next = (*L)->next;               
		(*L)->next = p;                    /*插入到表头*/
	}
}

【算法分析】
显然时间复杂度为O(n)。

🤦?♀?（2）尾插法

线性表（a,b,c,d,e）尾插法创建过程，读入数据顺序与线性表中的逻辑顺序是相同的。

【算法步骤】

①创建一个只有头节点的空链表
②为指针初始化，指向头节点
③根据创建链表的元素个数n，循环n次执行以下操作：

• 生成一个新节点
• 输入元素赋给新节点*p的数据域
• 将新节点p插入尾节点r之后
• 尾指针指向新的尾节点*p

【算法描述】【伪代码】

/*第一种形式*/
/*尾插法*/
/*自己输入n个元素的值，建立带表头节点的单链线性表L（尾插法）*/
void CreateListTail(LinkList* L, int n)
{
	LinkList p, r;
	int i;
	//srand(time(0));       /*初始化随机种子*/
	*L = (LinkList)malloc(sizeof(Node));     /*为整个线性表*/
	r = *L;              /* *r为指向尾部的节点*/
	for (i = 0;i < n;i++)
	{
		p = (Node*)malloc(sizeof(Node));  /*生成新节点*/
		scanf("%d", &(p->data));
		//p->data = rand() % 100 + 1;      /*随机生成100以内的数字*/
		r->next = p;                      /*将表尾终端节点指向新节点*/
		r = p;                            /*将当前的新节点定义为标为终端节点*/
	}
	r->next = NULL;                       /*表示当前链表结束*/
}


/*第二种形式*/
/*尾插法*/
/*随机产生n个元素的值，建立带表头节点的单链线性表L（尾插法）*/
void CreateListTail(LinkList* L, int n)
{
	LinkList p, r;
	int i;
	srand(time(0));       /*初始化随机种子*/
	*L = (LinkList)malloc(sizeof(Node));     /*为整个线性表*/
	r = *L;              /* *r为指向尾部的节点*/
	for (i = 0;i < n;i++)
	{
		p = (Node*)malloc(sizeof(Node));  /*生成新节点*/
		p->data = rand() % 100 + 1;      /*随机生成100以内的数字*/
		r->next = p;                      /*将表尾终端节点指向新节点*/
		r = p;                            /*将当前的新节点定义为标为终端节点*/
	}
	r->next = NULL;                       /*表示当前链表结束*/
}

【算法分析】
显然时间复杂度为O(n)。

??1.4 完整代码实现

//单链表的实现

/*线性表单链表的存储结构*/
typedef struct Node
{
	ElemType data;
	struct Node* next;
}Node;

typedef struct Node* LinkList;  /*定义LinkList*/

/*初始化*/
Status InitList(LinkList* L)
{
	*L = (LinkList)malloc(sizeof(Node));    //创建头节点，并使头指针指向该节点
	if (!(*L))
		return ERROR;     //内存分配失败，返回ERROR
	(*L)->next = NULL;
	return OK;
}

/*读取*/
/*初始条件:顺序线性表L已存在，i>=1&&i<=ListLength(L)*/
/*操作结果:用e返回L中第i个元素的值*/
Status GetElem(LinkList L, int i, ElemType* e)
{
	int j;
	LinkList p;         /*声明一节点p*/
	p = L->next;        /*让p指向链表L的第一个节点*/
	j = 1;              /*j为计数器*/
	while (p && j < i)     /*p不为空，j不等于i，循环继续*/
	{
		p = p->next;          /*让p指向下一节点*/
		++j;             
	}
	if (!p || j > i)  return ERROR;   /*第i个元素不存在*/
	*e = p->data;
	return OK;
}

//根据数据查找位序
Status GetLocate(LinkList L, ElemType e)
{
	int j;
	LinkList p;         /*声明一节点p*/
	p = L->next;        /*让p指向链表L的第一个节点*/
	j = 1;              /*j为计数器*/
	while ((p->data) != e&&(p->next)!=NULL)
	{
		p = p->next;          /*让p指向下一节点*/
		++j;
	}
	if (!p )  return ERROR;   /*第i个元素不存在*/
	return j;                /*返回位序*/
}

//根据数据查找地址
LinkList LocateElem(LinkList L, ElemType e)
{ //在带头节点的单链表L中查找值为e的元素
	LinkList p;
	p = L->next;      //初始化，p指向首元节点
	while (p && p->data != e)    //顺链域向后找直到p为空或者p所指向的节点的数据域等于e
	{
		p = p->next;             //p指向下一个节点
	}
	return p;                    //查找成功返回值为e的节点地址p，查找失败p为NULL
}


/*插入*/
/*初始条件:顺序线性表L已存在，i>=1&&i<=ListLength(L)*/
/*操作结果:在L中第i个位置之前插入新的数据元素e，L的长度加1*/
Status ListInsert(LinkList* L, int i, ElemType e)
{
	int j;
	LinkList p, s;
	p = *L;
	j = 1;
	while (p && j < i)     /*p不为空，j不等于i，循环继续*/
	{
		p = p->next;          /*让p指向下一节点*/
		++j;
	}
	if (!p || j > i)  return ERROR;   /*第i个元素不存在*/
	s = (LinkList)malloc(sizeof(Node));   /*生成新节点*/
	s->data = e;
	s->next = p->next;        /*将p的后继节点赋给s的后继*/
	p->next = s;              /*将s赋给p的后继*/
	return OK;
}

/*删除*/
/*初始条件:顺序线性表L已存在，i>=1&&i<=ListLength(L)*/
/*操作结果:删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(LinkList* L, int i, ElemType* e)
{
	int j;
	LinkList p, q;
	p = *L;
	j = 1;
	while (p->next && j < i)   /*遍历寻找第i个元素*/
	{
		p = p->next;
		++j;
	}
	if (!(p->next || j > i))  return ERROR;   /*第i个元素不存在*/
	q = p->next;
	p->next = q->next;                /*将q后继赋给p的后继*/
	*e = q->data;                    /*将q中的数据赋给*e*/
	free(q);                         /*让系统回收该节点，释放内存*/
	return OK;
}


void print(LinkList L)
{
	if (L->next == NULL)
		printf("链表为空！\n");
	Node* s;
	s = L->next;
	while (s != NULL)
	{
		printf("%d ", s->data);
		s = s->next;
	}
	printf("\n");
}


/*单链表的整表创建*/

/*头插法*/
/*随机产生n个元素的值，建立带表头节点的单链线性表L（头插法）*/
void CreateListHead(LinkList* L, int n)
{
	LinkList p;
	int i;
	srand(time(0));                   /*初始化随机种子*/
	*L = (LinkList)malloc(sizeof(Node));
	(*L)->next = NULL;                       /*先建立一个带头结点的单链表*/
	for (i = 0;i < n;i++)
	{
		p = (LinkList)malloc(sizeof(Node));  /*生成新节点*/
		//scanf("%d", &(p->data));
		p->data = rand() % 100 + 1;          /*随机生成100以内的数字*/
		p->next = (*L)->next;               
		(*L)->next = p;                    /*插入到表头*/
	}
}

/*尾插法*/
/*随机产生n个元素的值，建立带表头节点的单链线性表L（尾插法）*/
void CreateListTail(LinkList* L, int n)
{
	LinkList p, r;
	int i;
	srand(time(0));       /*初始化随机种子*/
	*L = (LinkList)malloc(sizeof(Node));     /*为整个线性表*/
	r = *L;              /* *r为指向尾部的节点*/
	for (i = 0;i < n;i++)
	{
		p = (Node*)malloc(sizeof(Node));  /*生成新节点*/
		p->data = rand() % 100 + 1;      /*随机生成100以内的数字*/
		r->next = p;                      /*将表尾终端节点指向新节点*/
		r = p;                            /*将当前的新节点定义为标为终端节点*/
	}
	r->next = NULL;                       /*表示当前链表结束*/
}

int main()
{
	LinkList L;
	int ret;             //接收返回值
	ret = InitList(&L);
	if (ret)
	{
		printf("链表初始化成功！\n");
	}
	else
	{
		printf("链表初始化失败！\n");
		return 0;                    //失败结束程序
	}
	int n = 0;
	do
	{
		printf("请输入链表的长度->：");
		scanf("%d", &n);                     //输入初始化链表长度
		if (n <= 0)
			printf("链表的长度必须大于0，请重新输入！\n");
	} while (n <= 0);
	CreateListHead(&L, n);                   //整表创建
	print(L);                                //打印初始化链表
	int i = 0;                               //输入插入位置
	int e = 0;                               //插入的值
	printf("请输入要插入的位置和元素值->：");
	scanf("%d %d", &i, &e);
	   //插入操作
	if (ListInsert(&L, i, e))
	{
		print(L);
	}
	else
	{
		printf("插入位序不合法，插入失败！\n");
	}
	//删除操作
	printf("请输入要删除的位置->：");
	scanf("%d", &i);
	if (ListDelete(&L, i, &e))
	{
		print(L);
		printf("删除了第%d个值为%d的元素!\n", i, e);
	}
	else
	{
		printf("删除位序不合法，删除失败！\n");
	}
	//读取操作
	printf("请输入查找的位置>：");
	scanf("%d", &i);
	if (GetElem(L, i, &e))
	{
		printf("第%d个元素的值为%d\n", i, e);
	}
	else
	{
		printf("查找位序不合法，查找失败！\n");
	}
	//查找操作
	printf("请输入查找的元素>：");
	scanf("%d", &e);
	if (GetLocate(L, e))
	{
		printf("在链表中的位序为%d\n", GetLocate(L, e));
	}
	else
	{
		printf("该链表中无%d\n", e);
	}
	printf("请输入查找的元素>：");
	scanf("%d", &e);
	if (LocateElem( L,  e))
	{
		printf("在链表中的存储地址为%p", GetLocate(L, e));
	}
	else
	{
		printf("该链表中无%d\n", e);
	}
	return 0;
}

结果图：