数据结构与算法——单链表（上）

我不是呆头

发布于 2025-12-20 10:11:23

1200

链表的解释

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

“车头” ：plist是个变量，存储的是个地址，说明他是个指针 “车厢” ：相当于一个结点，不同于顺序表的是，它不仅存储数据，还存储了一个地址（或是个指针，因为指针存储地址）。

这是两个不同类型的数据，只有结构体才能保存不同类型的数据 ————>由图知，每个结点由需要存储的数据和保存下一个结点的地址的指针组成

struct SListNode //S->Single   SListNode 由结点组成的单链表
{
	int data;//存储的数据
	struct SListNode* next;//指向下一个结点的指针
}

每个结点都是个独立的空间

单链表的打印

//手动构造链表
void test01()
{
	//创建结点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));//malloc申请空间不用去增容，此处是申请一个结点大小的空间
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));

	node1->data = 1;
	node2->data = 2;
	node3->data = 3;
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	SLTNode* list = node1;
	SLTPrint(list);//实参  //形参的改变需要影响实参的时候才需要传地址，这里不需要改变第一个结点所以不用传址调用
}

创建一个打印函数

void SLTPrint(SLTNode* phead) //形参
{
	SLTNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d -> ", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}

phead指向头结点，但是为什么又要用pcur去遍历？因为我们需要一个值一直指向头结点，如果用phead遍历后，没有指向头结点的指针且要插入一个结点需要从头结点遍历，所以我们需要创建一个pcur

单链表的数据插入

尾插

把数据存在链表里面，必须给这个数据申请一个结点，然后往链表里面去插入如图：为数据8创建一个结点，然后往链表里面插，这样4的next指针不指向NULL而是指向保存8这个结点的地址，就是指向newnode，所以首先要找到4这个结点，利用ptail遍历找尾

循环条件：（ptail—>next ！= NULL ）

链表为空：plist = NULL newnode 就是头结点，不用找尾

//创建结点
SLTNode* SLTbuyNode(SLTDataType x)
{
	//根据x创建新结点
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)  //pphead为&plist ，*pphead则是plist，**pphead则是*plist，就是结点
{
	assert(pphead);
	SLTNode* newnode = SLTbuyNode(x);

	//链表为空
	if (*pphead == NULL) //plist等于空的时候
	{
		*pphead = newnode;
	}
	else
	{
		//找尾结点
		SLTNode* ptail = *pphead;  
		while (ptail->next != NULL)
		{
			ptail = ptail->next;
		}
		//找到了尾结点 ptail newnode
		ptail->next = newnode;
	}
}

void test02()
{
	//创建空链表
	SLTNode* plist = NULL; 
	SLTPrint(plist);
	SLTPushBack(&plist, 1); //plist是指向结点地址的指针，&plist则是指向结点地址指针的地址
	SLTPrint(plist);
}

int main()
{
	// test01();
	test02();
	return 0;
}

时间复杂度：O(n)

头插

newnode——>next 需要指向第一个结点，头插操作完成了，但是对链表来说还需要从头结点来遍历，还需要将phead移到新结点下面

void test02()
{
	//创建空链表
	SLTNode* plist = NULL; 
	SLTPrint(plist);
	//SLTPushBack(&plist, 1); //plist是指向结点地址的指针，&plist则是指向结点地址指针的地址
	SLTPushFront(&plist, 1);
	SLTPushFront(&plist, 2);
	SLTPushFront(&plist, 3);
	SLTPushFront(&plist, 4);
	SLTPrint(plist);
}

int main()
{
	// test01();
	test02();
	return 0;
}

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTbuyNode(x);
	//链表为空和不为空一样
	newnode->next = *pphead;
	*pphead = newnode;
}

时间复杂度：O(1)

尾删

不仅要找到尾结点删掉，还要找到前一个结点把他的存储下一个结点地址的指针给为NULL 先让prev的指针指向NULL，然后删掉尾结点 prev一定是ptail的前一个结点 注意：只有一个结点和多个结点的操作是不同的一个结点只需要直接释放掉然后赋NULL

//尾删
void SLTPPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* ptail = *pphead;//指向第一个结点
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev和ptail都找到
		prev->next = NULL;
		free(ptail);//释放掉
		ptail = NULL;
	}
}

时间复杂度：O(n)

头删

phead指向第一个结点，第二个结点变成新的结点，所以在删除之前，将头结点的下一个结点存下来，然后将头结点删掉，让phead走到next 只有一个结点的情况：和多结点一样

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next; //头结点的下一个结点存下来，然后将头结点删掉
	free(*pphead);
	*pphead = next;
}