【数据结构】单链表、双链表

P_M_P

发布于 2024-01-18 19:09:55

1180

发布于 2024-01-18 19:09:55

文章被收录于专栏：P_M_P学习笔记

💡链表的概念和结构

概念：

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

以单链表为例：

可以看出：

1.链式结构在逻辑上是连续的，但是在物理上不一定连续 2.现实中的节点一般都是从堆上申请出来的 3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

💡链表的分类

虽然说有8种链表结构，但是现实中主要使用的只有两种结构：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

💡无头单向非循环链表的实现

单链表的尾部插入

这里需要注意的是，插入时可能头节点为空，要改变指针，所以要传二级指针

//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = node;//改变结构体指针，即指向结构体的指针
		return;
	}
	//说明链表不为空，找尾
	SLNode* pcur = *pphead;
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	pcur->next = node;//改变结构体成员，pcur->next通过指针结构体的pcur指针访问结构体的next成员
}

单链表的头部插入

//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	//新节点跟头节点连起来
	node->next = *pphead;
	//让新的节点称为头节点
	*pphead = node;
}

单链表的尾部删除

删除时因为要释放空间，所以要传递二级指针

//尾删
void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	//第一个节点不能为空
	assert(*pphead);
	//只有第一个节点的情况
	if ((*pphead)->next == NULL)
	{
		//直接把头节点删除
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//有多个节点的情况
		//找尾节点和尾节点的前一个节点
		SLNode* prev = NULL;
		SLNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev的指针不再指向ptail,而是指向ptail的下一个节点
		prev->next = ptail->next;
		free(ptail);
		//打印链表的函数里会判断是否为NULL
		ptail = NULL;
	}
}

单链表的头部删除

//头删
void SLPopFront(SLNode** pphead)
{
	assert(*pphead);
	assert(pphead);
	SLNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}

在指定位置插入前数据

//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead);
	//约定链表不能为空，pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLBuyNode(x);
	//pos是头节点，头插
	if (pos == *pphead)
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	// prev->node->pos
	node->next = pos;
	prev->next = node;
}

在指定位置之后插入数据

//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* node = SLBuyNode(x);
	//pos node pos->next
	node->next = pos->next;
	pos->next = node;
	return;
}

删除结点

//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//如果pos是头节点
	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}

销毁链表

//销毁链表
void SLDesTroy(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* pcur = *pphead;
	while (pcur->next != NULL)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

slist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SLPrint(SLNode* phead)
{
	//循环打印
	SLNode* pcur = phead;
	while (pcur != NULL)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//创建的新节点
SLNode* SLBuyNode(SLDataType x) {
	SLNode* node = (SLNode*)malloc(sizeof(SLNode));
	node->data = x;
	node->next = NULL;
	return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = node;//改变结构体指针，即指向结构体的指针
		return;
	}
	//说明链表不为空，找尾
	SLNode* pcur = *pphead;
	while (pcur->next)
	{
		pcur = pcur->next;
	}
	pcur->next = node;//改变结构体成员，pcur->next通过指针结构体的pcur指针访问结构体的next成员
}
//头插
void SLPushFront(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* node = SLBuyNode(x);
	//新节点跟头节点连起来
	node->next = *pphead;
	//让新的节点称为头节点
	*pphead = node;
}
//尾删
void SLPopBack(SLNode** pphead)
{
	assert(pphead);
	//第一个节点不能为空
	assert(*pphead);
	//只有第一个节点的情况
	if ((*pphead)->next == NULL)
	{
		//直接把头节点删除
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//有多个节点的情况
		//找尾节点和尾节点的前一个节点
		SLNode* prev = NULL;
		SLNode* ptail = *pphead;
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		//prev的指针不再指向ptail,而是指向ptail的下一个节点
		prev->next = ptail->next;
		free(ptail);
		//打印链表的函数里会判断是否为NULL
		ptail = NULL;
	}
}
//头删
void SLPopFront(SLNode** pphead)
{
	assert(*pphead);
	assert(pphead);
	SLNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}
//查找第一个为x的节点
SLNode* SLFind(SLNode** pphead, SLDataType x)
{
	assert(pphead);
	SLNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
//在指定位置之前插入数据
void SLInsert(SLNode** pphead, SLNode* pos, SLDataType x)
{
	assert(pphead);
	//约定链表不能为空，pos也不能为空
	assert(pos);
	assert(*pphead);
	SLNode* node = SLBuyNode(x);
	//pos是头节点，头插
	if (pos == *pphead)
	{
		node->next = *pphead;
		*pphead = node;
		return;
	}
	//找pos的前一个节点
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	// prev->node->pos
	node->next = pos;
	prev->next = node;
}
//在指定位置之后插入数据
void SLInsertAfter(SLNode* pos, SLDataType x)
{
	assert(pos);
	SLNode* node = SLBuyNode(x);
	//pos node pos->next
	node->next = pos->next;
	pos->next = node;
	return;
}
//删除pos节点
void SLErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	//如果pos是头节点
	if (pos == *pphead)
	{
		*pphead = (*pphead)->next;
		free(pos);
		return;
	}
	SLNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//删除pos之后节点
void SLEraseAfter(SLNode* pos)
{
	assert(pos&&pos->next);
	//pos pos->next pos->next->next
	SLNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
//销毁链表
void SLDesTroy(SLNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	SLNode* pcur = *pphead;
	while (pcur->next != NULL)
	{
		SLNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

💡带头双向循环链表的实现

list.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType _data;
	struct ListNode* _next;
	struct ListNode* _prev;
}ListNode;

//创建的新节点
ListNode* SLBuyNode(LTDataType x);
//链表的初始化
void InitList(ListNode** pHead);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

list.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
ListNode* SLBuyNode(LTDataType x) {
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->_data = x;
	node->_next = NULL;
	node->_prev = NULL;
	return node;
}
//初始化
void InitList(ListNode** pHead)
{
	*pHead = SLBuyNode(-1);
	(*pHead)->_next = (*pHead);
	(*pHead)->_prev = (*pHead);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	printf("哨兵位");
	while (cur!=pHead)
	{
		printf("%d<=>", cur->_data);
		cur = cur->_next;
	}
	printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* node = SLBuyNode(x);
	//方法一
	//ListNode* tail = pHead->_prev;
	//tail->_next = node;
	//node->_prev = tail;
	//pHead->_prev = node;
	//node->_next = pHead;
	//方法二
	node->_prev = pHead->_prev;
	pHead->_prev->_next = node;
	node->_next = pHead;
	pHead->_prev = node;
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next != pHead);
	ListNode* del = pHead->_prev;
	ListNode* next = pHead->_prev->_prev;
	pHead->_prev = next;
	next->_next = pHead;
	free(del);
	del = NULL;
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* node = SLBuyNode(x);
	node->_next = pHead->_next;
	pHead->_next->_prev = node;
	pHead->_next = node;
	node->_prev = pHead;
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(pHead->_next != pHead);
	ListNode* del = pHead->_next;
	ListNode* next = del->_next;
	pHead->_next = next;
	next->_prev = pHead;
	free(del);
	del = NULL;
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* cur = pHead->_next;
	while (cur != pHead)
	{
		if (cur->_data == x)
		{
			return cur;
		}
		cur = cur->_next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* node = SLBuyNode(x);
	ListNode* prev = pos->_prev;
	prev->_next = node;
	node->_prev = prev;
	node->_next = pos;
	pos->_prev = node;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* del = pos;
	ListNode* prev = pos->_prev;
	prev->_next = pos->_next;
	pos->_next->_prev = prev;
	free(del);
	del = NULL;
}
void ListDestory(ListNode* pHead)
{
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(pHead);
}

💡链表和顺序表的对比

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要移动元素，效率低，O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低