数据结构与算法（链表）

风中的云彩

发布于 2024-11-07 21:52:06

610

文章被收录于专栏：C/C++的自学之路

我可以接受失败，但绝对不能接受未奋斗过的自己。

前言

这是我学习数据结构的第三份笔记，有关链表的知识。后期我会继续将数据结构知识的笔记补全。 上一期笔记有关顺序表，没看过的同学可以去看看： 有关顺序表的笔记

链表

链表的概念

1. 链表是⼀种物理存储结构上非连续、非顺序的存储结构。 2. 链表是线性表的一种，所以它一定在逻辑结构上是线性的。 3. 数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 4. 链表实际上由一个个节点和头指针组成。

链表的分类

1. 链表的结构非常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构。 2. 虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：单链表和双向带头循环链表。

无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构。
带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

结点的概念

1. 结点的组成主要有两个部分：当前结点要保存的数据和下⼀个结点的地址（指向下一个节点的指针）。 2. 链表中每个结点都是独立申请的，即需要插入数据时才去申请⼀块结点的空间。 3. 我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。 4. 两个节点之间的地址不一定是连续的。

头指针

1. 我们在创建一个链表时，其实是创建了一个指向这个链表的头指针。 2. 我们使用指向不同链表的头指针来区分不同链表。 3. 由于我们用头指针来表示链表，所以我们在修改链表时候，传入的是头指针的地址。 4. 如果是单链表，那么头指针指向第一个节点；如果是双链表，那么头指针指向头节点。

头节点

1. 头节点在数据结构中，特别是在链表中，有着特殊的作用。它的主要目的是简化链表操作的边界条件处理。 2. 因为头节点的存在，所以不需要单独处理空链表或者在第一个元素上插入、删除的情况。 3. 头节点和第一个节点是两个概念。

单链表（不带头单向不循环链表）

定义单链表

typedef int LTDataType
typedef struct SListNode
{
	LTDataType data; //节点数据
	struct SListNode* next; //指针变量指向下一个节点
}SListNode;
//SListNode==Single List Node 单链表节点

创建新的节点

SListNode* AddSListNode(SLTDataType x)
{
	SListNode* node=(SListNode*)malloc(sizeof(SListNode));
    //链表在物理结构上可以是非线性的，所以只需要直接开辟新的节点就行，所以用malloc。
    //这里开辟一个节点空间，所以用SListNode* node。
    //而线性表是开辟一个动态数组空间，所以是int* node。
	node->data = x;
	node->next = NULL;
	return node;//返回一个指向新节点的指针
}

打印单链表

void PrintSListNode(SListNode* phead)//不需要对原来的链表进行修改，所以只要传值。
{
    assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
    //打印链表的话，至少要求链表里面有节点
	SListNode* purc = phead;
	while (purc != NULL)//去遍历链表
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
	printf("NULL\n");
}

尾插单链表

void BackPushSListNode(SListNode** pphead, SLTDataType x)
//一条链表需要用最前面的头指针来表示，又由于需要对于链表进行修改，所以传入头指针的地址。
{
    //插入的时候不需要一定要求链表里面有节点，所以不用assert()断言。
    //但是需要分有节点和无节点进行讨论
	SListNode* newnode = AddSListNode(x);
	SListNode* purc = *pphead;//一般不能用头节点直接去遍历。需要新命名一个节点专门去遍历
	if (*pphead == NULL)//如果链表里面没有节点
	{
		*pphead = newnode;
	}
	else//如果链表里面有节点
	{
		while (purc->next != NULL)
		{
			purc = purc->next;
		}
		purc->next = newnode;
	}
}

头插单链表

void FrontPushSListNode(SListNode** pphead, SLTDataType x)
{
	SListNode* newnode = AddSListNode(x);
    if (*pphead == NULL)//如果链表里面没有节点
	{
		*pphead = newnode;
	}
	else//如果链表里面有节点
    {
	    newnode->next = *pphead;//把新节点的指针指向原来链表中的第一个节点
	    *pphead = newnode;//把头指针指向新节点
    }
}

单链表指定位置前插入节点

void InsertSListNode(SListNode** pphead, SListNode* pos, SLTDataType x)
//在指定位置pos之前插入新节点
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
    assert(pos);
	SListNode* newnode=AddSListNode(x);
	SListNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

单链表指定位置后插入节点

void SListNodeInsert(SListNode* pos, SLTDataType x)
//在指定位置之后插入新节点
{
    assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
	assert(pos);
	SListNode* newnode = AddSListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

尾删单链表

void BackPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	SListNode* ptail = *pphead;
	SListNode* prev = NULL;
	if (ptail->next == NULL)//链表中只有一个节点时
	{
		free(ptail);
		ptail = NULL;
	}
	else//链表中不只有一个节点时
	{
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
        //此时，ptail保存的是最后一个节点的地址
        //此时，prev保存的是倒数第二个节点的地址
		prev->next = NULL;//确保倒数第二个节点的指针指向空
		free(ptail);//释放最后一个节点的地址
		ptail = NULL;//把ptail指向NULL，防止形成野指针
	}
}

头删单链表

void FrontPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	if ((*pphead)->next == NULL)//链表中只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}

指定删除单链表

void DeleteSListNode(SListNode** pphead, SListNode* pos)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	assert(pos);
	SListNode* prev = *pphead;
    if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
    else
    {
	    while (prev->next != pos)
	    {
		    prev = prev->next;
	    }
	    prev->next = pos->next;
	    free(pos);
	    pos = NULL;
    }
}

搜索单链表节点

SListNode* SearchSListNode(SListNode* phead, SLTDataType x)
{
	assert(phead);//搜索链表时候，需要确保链表里面至少有一个节点
	SListNode* purc = phead;
	while (purc)
	{
		if (purc->data == x)
		{
			printf("找到了。\n");
			return purc;
		}
		else
		{
			purc = purc->next;
		}
	}
	printf("没找到。\n");
}

销毁单链表

void DestroySListNode(SListNode** pphead)
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	SListNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur!=NULL)
		{
			SListNode* next = pcur->next;
			free(pcur);
			pcur = next;
		}
	}
	*pphead = NULL;
}

单链表实现代码

<test.h>文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SLTNode* next;
}SListNode;
void PrintSListNode(SListNode* phead);
void BackPushSListNode(SListNode** pphead, SLTDataType x);
SListNode* AddSListNode(SLTDataType x);
void FrontPushSListNode(SListNode** pphead, SLTDataType x);
void BackPopSListNode(SListNode** pphead);
void FrontPopSListNode(SListNode** pphead);
SListNode* SearchSListNode(SListNode* phead, SLTDataType x);
void InsertSListNode(SListNode** pphead, SListNode* pos, SLTDataType x);
void STLNodeSListNode(SListNode** pphead, SListNode* pos, SLTDataType x);
void DeleteSListNode(SListNode** pphead, SListNode* pos);
void DestroySListNode(SListNode** pphead);

<test.c>文件

#include "test.h"
void PrintSListNode(SListNode* phead)//不需要对原来的链表进行修改，所以只要传值。
{
    assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
    //打印链表的话，至少要求链表里面有节点
	SListNode* purc = phead;
	while (purc != NULL)//去遍历链表
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
	printf("NULL\n");
}

SListNode* AddSListNode(SLTDataType x)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	//链表在物理结构上可以是非线性的，所以只需要直接开辟新的节点就行，所以用malloc。
	//这里开辟一个节点空间，所以用SListNode* node。
	//而线性表是开辟一个动态数组空间，所以是int* node。
	node->data = x;
	node->next = NULL;
	return node;//返回一个指向新节点的指针
}

void BackPushSListNode(SListNode** pphead, SLTDataType x)
//一条链表需要用最前面的头指针来表示，又由于需要对于链表进行修改，所以传入头指针的地址。
{
    //插入的时候不需要一定要求链表里面有节点，所以不用assert()断言。
    //但是需要分有节点和无节点进行讨论
	SListNode* newnode = AddSListNode(x);
	SListNode* purc = *pphead;//一般不能用头节点直接去遍历。需要新命名一个节点专门去遍历
	if (*pphead == NULL)//如果链表里面没有节点
	{
		*pphead = newnode;
	}
	else//如果链表里面有节点
	{
		while (purc->next != NULL)
		{
			purc = purc->next;
		}
		purc->next = newnode;
	}
}

void FrontPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	if ((*pphead)->next == NULL)//链表中只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}

void BackPopSListNode(SListNode** pphead)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	SListNode* ptail = *pphead;
	SListNode* prev = NULL;
	if (ptail->next == NULL)//链表中只有一个节点时
	{
		free(ptail);
		ptail = NULL;
	}
	else//链表中不只有一个节点时
	{
		while (ptail->next != NULL)
		{
			prev = ptail;
			ptail = ptail->next;
		}
        //此时，ptail保存的是最后一个节点的地址
        //此时，prev保存的是倒数第二个节点的地址
		prev->next = NULL;//确保倒数第二个节点的指针指向空
		free(ptail);//释放最后一个节点的地址
		ptail = NULL;//把ptail指向NULL，防止形成野指针
	}
}

void FrontPopSListNode(SListNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)//链表中只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* second = (*pphead)->next;
		free(*pphead);
		*pphead = second;
	}
}

SListNode* SearchSListNode(SListNode* phead, SLTDataType x)
{
	assert(phead);//搜索链表时候，需要确保链表里面至少有一个节点
	SListNode* purc = phead;
	while (purc)
	{
		if (purc->data == x)
		{
			printf("找到了。\n");
			return purc;
		}
		else
		{
			purc = purc->next;
		}
	}
	printf("没找到。\n");
}

void InsertSListNode(SListNode** pphead, SListNode* pos, SLTDataType x)
//在指定位置pos之前插入新节点
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
    assert(pos);
	SListNode* newnode=AddSListNode(x);
	SListNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	newnode->next = pos;
	prev->next = newnode;
}

void SListNodeInsert(SListNode* pos, SLTDataType x)
//在指定位置之后插入新节点
{
    assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	//指定位置插入节点的话，至少要求链表里面有节点
	assert(pos);
	SListNode* newnode = AddSListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void DeleteSListNode(SListNode** pphead, SListNode* pos)
{
	assert(*pphead);//删除链表时候，需要确保链表里面至少有一个节点
	assert(pos);
	SListNode* prev = *pphead;
    if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
    else
    {
	    while (prev->next != pos)
	    {
		    prev = prev->next;
	    }
	    prev->next = pos->next;
	    free(pos);
	    pos = NULL;
    }
}

void DestroySListNode(SListNode** pphead)
{
	assert(*pphead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	SListNode* pcur = *pphead;
	while (pcur)
	{
		if (pcur!=NULL)
		{
			SListNode* next = pcur->next;
			free(pcur);
			pcur = next;
		}
	}
	*pphead = NULL;
}

int main()
{
	SListNode* plist = NULL;
	BackPushSListNode(&plist, 2);
	BackPushSListNode(&plist, 3);
	BackPushSListNode(&plist, 4);
	FrontPushSListNode(&plist, 1);
	//Back_Pop_STLNode(&plist);
	//Front_Pop_STLNode(&plist);
	SListNode* pos1 = SearchSListNode(plist, 3);
	InsertSListNode(&plist, pos1, 9);
	SListNodeInsert(pos1, 8);
	DeleteSListNode(&plist, pos1);
	//Destroy_STLNode(&plist);
	PrintSListNode(plist);
	return 0;
}

1. 单链表在已知一个节点的情况下，如果需要找到上一个节点，则需要从头开始遍历；如果需要找到下一个节点，则根据指针可以直接找到。

双向链表（带头双向循环链表）

定义双向链表

typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

创建新的节点

ListNode* CreateListNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

插入头节点

void InitListNode(ListNode** pphead)
//由于要改变phead指针的指向，所以要传入phead的地址，即使用ListNode** pphead。
{
	*pphead = CreateListNode(-1);//头指针指向头节点（不存储有效数据的节点）
}

打印双向链表

void PrintListNode(ListNode* phead)
{
    assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
}

尾插双向链表

void BcakPushListNode(ListNode* phead, DataType x)
//由于phead已经指向头节点，所以不再需要改变phead指向，所以使用ListNode* phead。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	ListNode* prev = phead;
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;//尾节点的表示：phead->prev
	phead->prev = newnode;
}

头插双向链表

void FrontPushListNode(ListNode* phead, DataType x)
//头插指的是，往头节点后面插入一个节点（第一个节点之前）。
//如果往头节点前面插入一个节点，那么本质上是尾插。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

判断双向链表是否为空

bool IsEmpty(ListNode* phead)
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	return (phead->next != phead);//除去头节点外，必须有第一个节点才算非空双向链表。
}

尾删双向链表

void BcakPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _prev = phead->prev->prev;
	ListNode* _pop = phead->prev;
	_prev->next = phead;
	phead->prev = _prev;
	free(_pop);
	_pop = NULL;
}

头删双向链表

void FrontPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _second = phead->next->next;
	ListNode* _first = phead->next;
	phead->next = _second;
	_second->prev = phead;
	free(_first);
	_first = NULL;
}

双向链表任意位置查找节点

ListNode* FindListNode(ListNode* phead, DataType x)
{
	assert(IsEmpty(phead));//查找链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		if (purc->data == x)
		{
			return purc;
		}
		purc = purc->next;
	}
	return NULL;
}

指定位置之后插入节点

void ListNodeInsert(ListNode* pos, DataType x)
{
    assert(IsEmpty(phead));//指定位置插入节点的话，至少要求链表里面那个位置上有节点
	assert(pos);//确保是一个节点地址
	ListNode* newnode = CreateListNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

指定位置删除节点

void ListNodePop(ListNode* pos)
{
	assert(pos);//确保是一个节点地址
	assert(IsEmpty(pos));//指定位置删除节点的话，至少要求链表里面那个位置上有节点
	ListNode* _prev = pos->prev;
	ListNode* _next = pos->next;
	_prev->next = _next;
	_next->prev = _prev;
	free(pos);
	pos=NULL;
}

销毁双向链表

void DestroyListNode(ListNode** pphead)
{
	assert(IsEmpty(*pphead));
    //要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* purc = (*pphead)->next;
	while (purc != *pphead)
	{
		ListNode* next = purc->next;
		free(purc);
		purc = next;
	}
	free(purc);
	purc = NULL;
	*pphead = NULL;
}

双链表实现代码

<list.h>文件

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

//创建新的节点
ListNode* CreateListNode(DataType x);

//初始化节点
void InitListNode(ListNode** pphead);

//尾插
void BcakPushListNode(ListNode* phead, DataType x);

//头插
void FrontPushListNode(ListNode* phead, DataType x);

//打印链表
void PrintListNode(ListNode* phead);

//判断链表是否为空
bool IsEmpty(ListNode* phead);

//尾删
void BcakPopListNode(ListNode* phead);

//头删
void FrontPopListNode(ListNode* phead);

//查找节点
ListNode* FindListNode(ListNode* phead, DataType x);

//任意位置插入节点
void ListNodeInsert(ListNode* pos, DataType x);

//任意位置删除节点
void ListNodePop(ListNode* pos);

//销毁链表
void DestroyListNode(ListNode** pphead);

<test.c>文件

#include "list.h"

ListNode* CreateListNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;
	return newnode;
}

void InitListNode(ListNode** pphead)//由于要改变phead指针的指向，所以要传入phead的地址，即使用ListNode** pphead。
{
	*pphead = CreateListNode(-1);//头指针指向头节点（不存储有效数据的节点）
}

void BcakPushListNode(ListNode* phead, DataType x)
//由于phead已经指向头节点，所以不再需要改变phead指向，所以使用ListNode* phead。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	ListNode* prev = phead;
	newnode->next = phead;
	newnode->prev = phead->prev;
	phead->prev->next = newnode;//尾节点的表示：phead->prev
	phead->prev = newnode;
}

void FrontPushListNode(ListNode* phead, DataType x)
//头插指的是，往头节点后面插入一个节点（第一个节点之前）。
//如果往头节点前面插入一个节点，那么本质上是尾插。
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* newnode = CreateListNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;
}

void PrintListNode(ListNode* phead)
{
    assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		printf("%d\n", purc->data);
		purc = purc->next;
	}
}

bool IsEmpty(ListNode* phead)
{
	assert(phead);//要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	return (phead->next != phead);//除去头节点外，必须有第一个节点才算非空双向链表。
}

void BcakPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _prev = phead->prev->prev;
	ListNode* _pop = phead->prev;
	_prev->next = phead;
	phead->prev = _prev;
	free(_pop);
	_pop = NULL;
}

void FrontPopListNode(ListNode* phead)
{
	assert(IsEmpty(phead));//打印链表的话，至少要求链表里面有节点
	ListNode* _second = phead->next->next;
	ListNode* _first = phead->next;
	phead->next = _second;
	_second->prev = phead;
	free(_first);
	_first = NULL;
}

ListNode* FindListNode(ListNode* phead, DataType x)
{
	assert(IsEmpty(phead));//查找链表的话，至少要求链表里面有节点
	ListNode* purc = phead->next;
	while (purc != phead)
	{
		if (purc->data == x)
		{
			return purc;
		}
		purc = purc->next;
	}
	return NULL;
}

void ListNodeInsert(ListNode* pos, DataType x)
{
    assert(IsEmpty(phead));//指定位置插入节点的话，至少要求链表里面那个位置上有节点
	assert(pos);//确保是一个节点地址
	ListNode* newnode = CreateListNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

void ListNodePop(ListNode* pos)
{
	assert(IsEmpty(phead));//指定位置删除节点的话，至少要求链表里面那个位置上有节点
	assert(pos);//确保是一个节点地址
	ListNode* _prev = pos->prev;
	ListNode* _next = pos->next;
	_prev->next = _next;
	_next->prev = _prev;
	free(pos);
	pos=NULL;
}

void DestroyListNode(ListNode** pphead)
{
	assert(IsEmpty(*pphead));
    //要求phead!=NULL,否则直接断言报错。因为后面需要对phead进行解引用操作。
	ListNode* purc = (*pphead)->next;
	while (purc != *pphead)
	{
		ListNode* next = purc->next;
		free(purc);
		purc = next;
	}
	free(purc);
	purc = NULL;
	*pphead = NULL;
}

顺序表与单链表的区别

1. 如果要求频繁的查找，不需要进行大面积插入删除，则用顺序表。 2. 如果不要求频繁的查找，而需要进行大面积插入删除，则用链表。

致谢

感谢您花时间阅读这篇文章！如果您对本文有任何疑问、建议或是想要分享您的看法，请不要犹豫，在评论区留下您的宝贵意见。每一次互动都是我前进的动力，您的支持是我最大的鼓励。期待与您的交流，让我们共同成长，探索技术世界的无限可能！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-04，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构与算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度

数据结构与算法（链表）

数据结构与算法（链表）

前言

链表

链表的概念

链表的分类

结点的概念

头指针

头节点

单链表（不带头单向不循环链表）

定义单链表

创建新的节点

打印单链表

尾插单链表

头插单链表

单链表指定位置前插入节点

单链表指定位置后插入节点

尾删单链表

头删单链表

指定删除单链表

搜索单链表节点

销毁单链表

单链表实现代码

<test.h>文件

<test.c>文件

双向链表 （带头双向循环链表）

定义双向链表

创建新的节点

插入头节点

打印双向链表

尾插双向链表

头插双向链表

判断双向链表是否为空

尾删双向链表

头删双向链表

双向链表任意位置查找节点

指定位置之后插入节点

指定位置删除节点

销毁双向链表

双链表实现代码

<list.h>文件

<test.c>文件

顺序表与单链表的区别

致谢

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

双向链表（带头双向循环链表）