深入理解单链表：数据结构的基石-EW帮帮网

单链表

一.基础概念
二、单链表的创建
- 2.1定义节点的结构体
- 2.2结点的创建
- 2.3将链表中的数据打印
三、单链表的核心操作
- 3.1尾插数据
- 3.2头插数据
- 3.3头删数据
- 3.4尾删数据
- 3.5查找数据
- 3.6目标位置前插入数据
- 3.7删除目标位置的节点
四、单链表的优势与局限
- 优势
- 局限

一.基础概念

单链表是一种线性数据结构，它由一系列节点组成。每个节点包含两个部分：数据域和指针域。数据域用于存储具体的数据元素，指针域则存储指向下一个节点的内存地址，通过这种方式将各个节点连接成一条 “链”。链表的起始节点被称为头节点，而最后一个节点的指针域通常设置为 NULL，以此标识链表的结束。

二、单链表的创建

2.1定义节点的结构体

为方便后续修改链表数据的便利性，将int更名。

typedef int SLTDataType;
struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
};
typedef struct SListNode SLTNode;

2.2结点的创建

这个函数负责在内存中分配空间，并初始化节点的数据域和指针域。

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2.3将链表中的数据打印

便利后续观察

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

三、单链表的核心操作

在这里由于是对结构体指针进行操作，为了能对指针修改，参数传的是二级指针。

3.1尾插数据

尾插法是将新节点插入到链表的尾部。需要遍历链表找到最后一个节点，然后将最后一个节点的指针指向新节点。

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾节点的指针
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		// 尾节点，链接新节点
		tail->next = newnode;
	}

3.2头插数据

是一种将新节点插入到链表头部的方法。新节点的指针直接指向原头节点，然后将新节点设为头节点。

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.3头删数据

将头节点的所指向的下一个节点储存，以便释放内存。

void SListPopFront(SLTNode** pphead)
{
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

为了避免内存泄漏，需要释放原头节点所占用的内存空间。

3.4尾删数据

尾删数据时，较为复杂。
当此时链表为空时，则直接退出程序即可。
当链表有多个节点时，设置两个指针，一个存储尾节点，一个存储尾节点的前一个节点。进行遍历链表，找出尾节点释放置空即可。

void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

3.5查找数据

原理也是遍历链表，找出所需数据，这里不做过度赘述。

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

3.6目标位置前插入数据

当链表为空时，直接创建一个新的节点即可。
当链表不为空时，创建新节点后遍历链表，找出目标位置。
目标位置前一个节点指向新节点，新节点只想之前目标位置。

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SLTNode* newnode = BuySListNode(x);
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

3.7删除目标位置的节点

同理先判断链表是否为空，后遍历链表删除位置节点。

void SListErase(SLTNode** pphead, SLTNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

四、单链表的优势与局限

优势

动态内存分配：单链表在运行时可以根据实际需求动态分配和释放内存，无需预先确定数据结构的大小。这使得它在处理数据量不确定的场景时非常灵活，避免了像数组那样可能出现的内存浪费或不足的问题。
高效的插入和删除：在链表中进行插入和删除操作时，只需要修改相关节点的指针，而不需要像数组那样移动大量元素。特别是在频繁进行插入和删除操作的场景中，单链表的效率优势尤为明显。

局限

随机访问困难：由于单链表的节点在内存中不是连续存储的，无法通过索引直接访问特定位置的节点。要访问链表中的某个节点，必须从链表头开始依次遍历，这导致随机访问的时间复杂度高达 O(n)，相比之下数组的随机访问时间复杂度为O(1)。
额外的内存开销：每个节点除了存储数据本身外，还需要额外的空间来存储指向下一个节点的指针。这在一定程度上增加了内存的使用量，对于内存资源紧张的系统可能会产生影响。

深入理解单链表：数据结构的基石

单链表