526互联

2.单向链表

发布时间 2023-05-31 22:19:18作者: CodeMagicianT

1.为什么需要链表？

  链表是一种灵活的数据结构，它允许在内存中动态地存储和操作元素。以下是一些需要使用链表的原因：

1. 动态数组的缺点：数组的大小是在程序运行时固定的，如果需要添加或删除元素，就需要重新分配内存并复制数据。这会导致大量的内存浪费和性能问题。而链表可以动态地调整大小，只需要增加或删除节点即可。

2. 插入和删除操作的效率：在链表中插入和删除元素比在数组中高效得多。因为链表中的节点不需要移动整个数组，只需要修改指针指向即可。这使得链表在处理大量数据时具有更高的效率。

3. 随机访问的效率：链表的随机访问效率较低，因为需要从头结点开始遍历整个链表才能找到目标元素。但是，链表可以通过哈希表等数据结构来优化随机访问效率。

4. 适用场景：链表适用于那些需要频繁插入和删除元素的场景，例如缓存、队列、栈等数据结构。此外，链表还可以用于实现一些高级算法，如广度优先搜索(BFS)和深度优先搜索(DFS)。

总之，链表是一种非常有用的数据结构，它可以在某些情况下提供比数组更好的性能和灵活性。

2.链表基本概念

链表(Linked List)是一种数据结构，它允许在单个内存位置中存储多个元素。与数组不同，链表中的元素不是连续存储的，而是通过指针相互连接。链表的主要优点是动态地添加和删除元素，而不需要像数组那样需要预先分配固定大小的空间。

链表的基本概念包括：

1. 头结点(Head Node):链表的第一个节点通常被称为头结点。头结点本身不存储实际的数据，它仅用于指向链表的下一个节点。

2. 尾节点(Tail Node):链表的最后一个节点通常被称为尾节点。尾节点同样不存储实际的数据，它仅用于指向链表的第一个节点的前一个节点。

3. 指针(Pointer):指针是一个变量，它存储另一个变量的地址。在链表中，指针用于连接各个节点。每个节点包含一个指向下一个节点的指针，这样可以形成一个单向链。

4. 访问(Accessing):要访问链表中的某个元素，首先需要找到该元素所在的节点。然后，可以通过解引用指针来访问该节点的数据部分。例如，如果有一个指向头结点的指针p,可以使用*p来访问头结点的数据部分。

5. 插入(Insertion):在链表中插入一个新元素时，需要先找到合适的位置。可以将新元素插入到头结点之后、尾节点之前的位置，或者尾节点之后的位置。具体操作取决于所选位置是否为空闲状态。插入操作可能涉及修改指针的指向，以便将新元素链接到正确的位置。

6. 删除(Deletion):从链表中删除一个元素时，需要找到该元素所在的节点。然后，可以将该节点的指针设置为其后继节点的指针，从而删除该节点。删除操作可能涉及修改指针的指向，以便更新整个链表的结构。

3.链表的形成方式

链表是由包含数据的多个结点前后连接形成的链式结构
1.结点：
每一个结点是一小片连续的、存放了数据的内存空间，是形成链表的基本单元
2.结点的构成：
每个结点由两方面内容组成：
（1）数据域：
真正要处理的数据，可以是单个基本类型的数据，也可以是多个不同类型的数据共同构成。
（2）指针域：
一般用来存放另一结点的首地址，即指针域是用来指向另一个结点的（或者赋值为NULL，即不指向任何结点。）

4.简单链表的形成

链表正是通过指针域将各个结点有机地联接成一个整体。设有A、B、C、D四个结点，按下图形成链表
注意
（1）head：设计的头部指针, 指向链表头结点
（2）NULL：尾部结点的指针域为空，不指向任何结点。
（3）前一节点的指针域存放下一结点的首地址

节点结构体：

//节点结构体
struct LinkNode
{
	//数据域
	void * data;
	//指针域
	struct LinkNode * next;
};

链表结构体

//链表结构体
struct LList
{
	//头节点
	struct LinkNode pHeader;
	//链表长度
	int m_size;
};

//不让用户直接访问LList
typedef void * LinkList;

————————————————
版权声明：本文为CSDN博主「刘鑫磊up」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/liu17234050/article/details/110502629

5.链表的操作

5.1初始化链表

LinkList init_LinkList()
{
	 struct LList * myList = malloc(sizeof(struct LList));

	 if (myList == NULL)
	 {
		 return NULL;
	 }

	 myList->pHeader.data = NULL;
	 myList->pHeader.next = NULL;
	 myList->m_size = 0;

	 return myList;
}

//初始化链表
LinkList mylist = init_LinkList();

5.2链表的插入操作

//需要做插入操作的链表是list，插入位置是pos，插入的数据是data
void insert_LinkList(LinkList list, int pos, void * data)
	if (list == NULL)
	{
		return;
	}
	if ( data == NULL)
	{
		return;
	}
	//将list还原成 struct LList数据类型
	struct LList * myList = list;
	if (pos < 0 || pos > myList->m_size)
	{
		//无效位置 强制做尾插
		pos = myList->m_size;
	}

	//找到插入节点的前驱节点位置
	struct LinkNode * pCurrent = &myList->pHeader;

	for (int i = 0; i < pos;i++)
	{
		pCurrent = pCurrent->next;
	}
	//pCurrent 要插入节点的前驱

	//创建新节点

    struct LinkNode * newNode = malloc(sizeof(struct LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	//建立节点关系
	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

	//更新链表长度
	myList->m_size++;
}

//准备数据
struct Person p1 = { "亚瑟", 18 };
struct Person p2 = { "妲己", 20 };
struct Person p3 = { "安琪拉", 19 };
struct Person p4 = { "凯", 21 };
struct Person p5 = { "孙悟空", 999 };
struct Person p6 = { "李白", 999 };

//插入数据
insert_LinkList(mylist, 0, &p1);
insert_LinkList(mylist, 0, &p2);
insert_LinkList(mylist, -1, &p3);
insert_LinkList(mylist, 0, &p4);
insert_LinkList(mylist, 1, &p5);
insert_LinkList(mylist, 0, &p6);

5.3链表的遍历操作

//遍历链表
void foreach_LinkList(LinkList list, void(*myForeach)(void *))
{
	if (list ==NULL)
	{
		return;
	}

	struct LList * mylist = list;

	struct LinkNode* pCurrent = mylist->pHeader.next;

	for (int i = 0; i < mylist->m_size;i++)
	{
		myForeach(pCurrent->data);
		pCurrent = pCurrent->next;
	}
}

//遍历
struct Person
{
	char name[64];
	int age;
};

void myPrintPerson(void * data)
{
	struct Person * p = data;
	printf("姓名：%s  年龄：%d\n", p->name, p->age);
}

foreach_LinkList(mylist, myPrintPerson);

5.4链表的删除操作

//删除链表  按位置
void removeByPos_LinkList(LinkList list, int pos)
{
	if ( list == NULL)
	{
		return;
	}

	struct LList * mylist = list;

	if (pos < 0 || pos > mylist->m_size - 1)
	{
		return;
	}

	//找到待删除节点的前驱节点
	struct LinkNode * pCurrent = &mylist->pHeader;
	for (int i = 0; i < pos;i++)
	{
		pCurrent = pCurrent->next;
	}

	//记录待删除的节点
	struct LinkNode * pDel = pCurrent->next;

	//重新建立节点关系
	pCurrent->next = pDel->next;

	free(pDel);
	pDel = NULL;

	//更新链表长度
	mylist->m_size--;
}


//按照值删除链表
void removeByValue_LinkList(LinkList list, void* data, int(*myCompare)(void*, void*))
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	struct LList* mylist = list;
	//创建两个辅助指针
	struct LinkNode* pPrev = &mylist->pHeader;
	struct LinkNode* pCurrent = pPrev->next;

	for (int i = 0; i < mylist->m_size; i++)
	{
		//pCurrent->data  data 将两个指针比较利用回调 交给用户
		if (myCompare(pCurrent->data, data))
		{
			pPrev->next = pCurrent->next;

			free(pCurrent);
			pCurrent = NULL;

			mylist->m_size--;
			break;
		}

		//没找到 辅助指针后移
		pPrev = pCurrent;
		pCurrent = pCurrent->next;
	}
}

5.5清空链表

//清空链表
void clear_LinkList(LinkList list)
{
	if (list == NULL)
	{
		return;
	}

	struct LList* mylist = list;

	struct LinkNode* pCurrent = mylist->pHeader.next;

	for (int i = 0; i < mylist->m_size; i++)
	{
		struct LinkNode* pNext = pCurrent->next;
		free(pCurrent);
		pCurrent = pNext;
	}

	mylist->pHeader.next = NULL;
	mylist->m_size = 0;
}

5.6返回链表长度

//返回链表长度
int  size_LinkList(LinkList list)
{
	if (list == NULL)
	{
		return -1;
	}

	struct LList* mylist = list;

	return mylist->m_size;
}

5.7销毁链表

//销毁链表
void destroy_Linklist(LinkList list)
{
	if (list == NULL)
	{
		return;
	}

	//清空链表
	clear_LinkList(list);
	free(list);
	list = NULL;
}

5.8完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//节点结构体
struct LinkNode
{
	//数据域
	void* data;
	//指针域
	struct LinkNode* next;
};

//链表结构
struct LList
{
	//头结点
	struct LinkNode pHeader;
	//链表长度
	int m_size;
};

typedef void* LinkList;

//初始化链表
LinkList init_LinkList()
{
	struct LList* myList = malloc(sizeof(struct LList));

	if (myList == NULL)
	{
		return NULL;
	}

	myList->pHeader.data = NULL;
	myList->pHeader.next = NULL;
	myList->m_size = 0;

	return myList;
}

//插入链表
void insert_LinkList(LinkList list, int pos, void* data)
{
	if (list == NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}

	//将list还原成struct LList数据类型
	struct LList* myList = list;
	if (pos < 0 || pos > myList->m_size)
	{
		//无效位置 强制做尾插
		pos = myList->m_size;
	}

	//找到插入节点的前驱节点位置
	struct LinkNode* pCurrent = &myList->pHeader;
	
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;//通过循环找到待插入位置的前驱节点
	}
	//pCurrent要插入节点的前驱
	
	//创建新节点
	struct LinkNode* newNode = malloc(sizeof(struct LinkNode));
	newNode->data = data;
	newNode->next = NULL;

	//建立节点关系
	newNode->next = pCurrent->next;
	pCurrent->next = newNode;

	//更新链表长度
	myList->m_size++;
}

//遍历链表
void foreach_LinkList(LinkList list, void(* myForeach)(void *))
{
	if (list == NULL)
	{
		return;
	}

	struct LList* mylist = list;

	struct LinkNode* pCurrent = mylist->pHeader.next;//头结点数据域没必要访问

	for (int i = 0; i < mylist->m_size; i++)
	{
		myForeach(pCurrent->data);
		pCurrent = pCurrent->next;
	}
}

//测试
struct Person
{
	char name[64];
	int age;
};

void myPrintPerson(void* data)
{
	struct Person* p = data;
	printf("姓名：%s，年龄：%d\n", p->name, p->age);
}
void test01()
{
	//准备数据
	struct Person p1 = { "亚瑟", 18 };
	struct Person p2 = { "妲己", 20 };
	struct Person p3 = { "安其拉", 19 };
	struct Person p4 = { "凯", 21 };
	struct Person p5 = { "孙悟空", 899 };
	struct Person p6 = { "李白", 899 };

	//初始化链表
	LinkList mylist = init_LinkList();

	//插入数据insert
	insert_LinkList(mylist, 0, &p1);
	insert_LinkList(mylist, 0, &p2);
	insert_LinkList(mylist, -1, &p3);
	insert_LinkList(mylist, 0, &p4);
	insert_LinkList(mylist, 1, &p5);
	insert_LinkList(mylist, 0, &p6);

	//李白 凯 孙悟空 妲己 亚瑟 安其拉
	//遍历
	foreach_LinkList(mylist, myPrintPerson);
}

int main()
{
	test01();
	system("pause");
	return EXIT_SUCCESS;
}

参考资料来源：

黑马程序员