数据结构-单链表详解

线性表的链式存储结构成为单链表，借助指针来反映数据元素之间的逻辑关系。

（1）单链表中结点定义：

/** * 定义结点类型结构体，有一个data域和一个next域 */
typedef struct LNode {
   
	int data;  // 数据域
	struct LNode* next;  // 指向相同结点类型的指针，存放后继结点的地址
}LNode, * LinkList;

使用LNode *L;或LinkList L;定义一个指向头结点的指针，即头指针，L是用来指单链表的头指针，习惯上称为单链表L。（这两种定义方式是一样的，但通常用第二种）

• 注意区别：

  • 带头结点的单链表：（这里的Head相当于上面的L）
    
    判空：Head->next == NULL为真
  • 不带头结点的单链表：
    
    判空：Head == NULL为真

• 注：

  • 不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，且该结点内的数据通常不存储信息。
  • 引入头结点的优点：链表中所有位置的操作是一致的；无论链表是否为空，其头指针都指向了头结点，所以头指针始终是非空指针，因此，空表和非空表的处理也得到了统一。

初始化带头结点的链表

/** * 初始化，生成带有头结点的单链表 * @param L 引用类型，头指针 */
void InitLinkList(LinkList& L) {
   
	L = (LinkList)malloc(sizeof(LNode));
	if (L) {
      //内存分配成功
		L->next = NULL;
	}
}

头插法建立单链表

/** * 头插法建立单链表 * @param L 引用类型的头指针 * @param n 表示需要插入的元素个数 */
void HeadInsert_LinkList(LinkList& L, int n) {
   
	LNode* s;   //辅助指针s，用于指向新申请的结点空间，并将输入的数据存入s->data
	for (int i = 1; i <= n; ++i) {
   
		s = (LNode*)malloc(sizeof(LNode));  //申请新结点空间
		if (s)  //内存分配成功
		{
   
			/* scanf_s() —— 此功能特定于Microsoft编译器。它与scanf相同，只是它不会引起缓冲区过载。 它将输入输入到基于文本的控制台程序中，并将其放入变量中。后面不再重复说明 */
			scanf_s("%d", &s->data);  //输入需要插入的值
			/** * 头插法的关键步骤： */
			s->next = L->next;  //让s的next已知的L的next（最开始为NULL）
			L->next = s;        //再让头指针L的next指向新插入的结点s
		}
		
	}
}

利用头插法建立单链表，输入的数据的顺序与生成的链表中的元素的顺序相反。每个节点插入的时间复杂度为O(1)，总时间复杂度为O(n)。

尾插法建立单链表

/** * 尾插法建立单链表 * @param L 引用类型的头指针 * @param n 需要插入的元素的个数 */
void RailInsert_LinkList(LinkList& L, int n) {
   
	LNode* s, * r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
	r = L;   //r初始指向头结点
	for (int i = 1; i <= n; ++i) {
   
		s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
   
			scanf_s("%d", &s->data);
			/** * 尾插法的关键步骤 */
			r->next = s;  //直接让r的next指向新结点s
			r = s;        //再让r重新指向当前的尾结点
		}
		
	}
	r->next = NULL;   //最后，将r的next置空
}

尾插法建立单链表，输入的数据的顺序与生成的链表中的元素的顺序相同。每个结点插入的时间复杂度为O(1)，总时间复杂度为O(n)。

在单链表中插入一个结点

/** * 在单链表中插入一个元素 * @param L 单链表的头指针，代表单链表，使用引用型 * @param location 在第location个位置插入 * @param elem 插入的元素值 */
int InsertElem_LinkList(LinkList& L, int location, int elem) {
   
	LNode* p, * s;  //p用于遍历单链表，s用于指向新生成的结点空间，并存储插入的数据
	p = L;  //p初始指向头结点
	int j = 1;  //计数，帮助找到要插入的第i个位置
	
	while (p != NULL && j < location) {
   
		p = p->next;
		++j;
	}
	
	if (!p || j>location)  //插入的位置小于1或者大于表长+1
	{
   
		return 0;
	}
	s = (LNode*)malloc(sizeof(LNode));
	if (s)
	{
   
		s->data = elem;
	}

	if (s)
	{
   
		/* 插入的关键步骤：顺序不能颠倒 */
		s->next = p->next;  //先把第i-1个位置的next给到s的next
		p->next = s;        //再把s给到第i-1个位置的next，即给到第i个位置
	}
	return 1;
}

按顺序打印单链表

/** * 按顺序输出单链表中元素的值 * @param L 单链表的头指针 */
void Print_LinkList(LinkList L) {
   
	LNode* p = L->next;
	while (p != NULL) {
   
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

完成测试代码

#include <stdio.h>
#include <malloc.h>
/** * 定义结点类型结构体，有一个data域和一个next域 */
typedef struct LNode {
   
	int data;
	struct LNode* next;
}LNode, * LinkList;

/** * 初始化，生成带有头结点的单链表 * @param L 引用类型，头指针 */
void InitLinkList(LinkList& L) {
   
	L = (LinkList)malloc(sizeof(LNode));
	if (L) {
      //内存分配成功
		L->next = NULL;
	}
}

/** * 头插法建立单链表 * @param L 引用类型的头指针 * @param n 表示需要插入的元素个数 */
void HeadInsert_LinkList(LinkList& L, int n) {
   
	LNode* s;   //辅助指针s，用于指向新申请的结点空间，并将输入的数据存入s->data
	for (int i = 1; i <= n; ++i) {
   
		s = (LNode*)malloc(sizeof(LNode));  //申请新结点空间
		if (s)  //内存分配成功
		{
   
			/* scanf_s() —— 此功能特定于Microsoft编译器。它与scanf相同，只是它不会引起缓冲区过载。 它将输入输入到基于文本的控制台程序中，并将其放入变量中。后面不再重复说明 */
			scanf_s("%d", &s->data);  //输入需要插入的值
			/** * 头插法的关键步骤： */
			s->next = L->next;  //让s的next已知的L的next（最开始为NULL）
			L->next = s;        //再让头指针L的next指向新插入的结点s
		}
		
	}
}

/** * 尾插法建立单链表 * @param L 引用类型的头指针 * @param n 需要插入的元素的个数 */
void RailInsert_LinkList(LinkList& L, int n) {
   
	LNode* s, * r;  //s用于指向新申请的节点空间，r用于始终指向尾结点
	r = L;   //r初始指向头结点
	for (int i = 1; i <= n; ++i) {
   
		s = (LNode*)malloc(sizeof(LNode));
		if (s)
		{
   
			scanf_s("%d", &s->data);
			/** * 尾插法的关键步骤 */
			r->next = s;  //直接让r的next指向新结点s
			r = s;        //再让r重新指向当前的尾结点
		}
		
	}
	r->next = NULL;   //最后，将r的next置空
}

/** * 在单链表中插入一个元素 * @param L 单链表的头指针，代表单链表，使用引用型 * @param location 在第location个位置插入 * @param elem 插入的元素值 */
int InsertElem_LinkList(LinkList& L, int location, int elem) {
   
	LNode* p, * s;  //p用于遍历单链表，s用于指向新生成的结点空间，并存储插入的数据
	p = L;  //p初始指向头结点
	int j = 1;  //计数，帮助找到要插入的第i个位置
	
	while (p != NULL && j < location) {
   
		p = p->next;
		++j;
	}
	
	if (!p || j>location)  //插入的位置小于1或者大于表长+1
	{
   
		return 0;
	}
	s = (LNode*)malloc(sizeof(LNode));
	if (s)
	{
   
		s->data = elem;
	}

	if (s)
	{
   
		/* 插入的关键步骤：顺序不能颠倒 */
		s->next = p->next;  //先把第i-1个位置的next给到s的next
		p->next = s;        //再把s给到第i-1个位置的next，即给到第i个位置
	}
	return 1;
}

/** * 按顺序输出单链表中元素的值 * @param L 单链表的头指针 */
void Print_LinkList(LinkList L) {
   
	LNode* p = L->next;
	while (p != NULL) {
   
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

/** * 主函数 * @return 1，结束 */
int main() {
   
	LinkList L;
	InitLinkList(L);

	int n;
	
	// 头插法建立单链表
	scanf_s("%d" ,&n);
	HeadInsert_LinkList(L, n);
	Print_LinkList(L);

	InitLinkList(L);

	// 尾插法建立单链表
	scanf_s("%d", &n);
	RailInsert_LinkList(L, n);
	Print_LinkList(L);

	// 插入元素
	int i, elem;
	scanf_s("%d %d", &i, &elem);
	InsertElem_LinkList(L, i, elem);
	Print_LinkList(L);

	return 0;
}

创作不易，喜欢的话加个关注点个赞，谢谢谢谢谢谢！