【数据结构单链表】超详细理解&&例题&&错题

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

Sunfor_sun

1565人浏览 · 2024-10-30 12:00:00

Sunfor_sun · 2024-10-30 12:00:00 发布

数据结构单链表

前言
一、单链表的结构和概念
二、单链表的基本操作
三、单链表用C语言的代码实现
四、单链表的分类
五、单链表的优缺点
- 1.优点
- 2.缺点
六、单链表的算法题整理
后记

你好，这里是新人 Sunfor

这篇是我最近对于数据结构单链表的学习心得和错题整理
有任何错误欢迎指正，欢迎交流！
会持续更新，希望对你有所帮助，我们一起学习，一起进步

前言

一、单链表的结构和概念

1.单链表的定义

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

2.单链表中的结点

如上图所示，链表中的结点主要有两个部分：当前结点要保存的数据和保存的下一个结点的地址（指针变量）
plist 保存的是第一个结点的地址,我们称plist此时指向第一个结点,如果我们希望plist指向第二个结点,只需要修改plist保存的地址
链表中每个结点都是独立申请的,当我们需要插入数据时才去申请一块结点的空间,我们需要通过指针变量来保存下一个结点的位置才能找到下一个结点

3.单链表的性质

链表机构在逻辑上是连续的,在物理结构上不一定连续

结点一般是从堆上申请的

从堆上申请来的空间,是按照一定策略分配出来的,每次申请的空间可能连续,可能不连续

二、单链表的基本操作

插入结点,删除结点,查找结点,遍历链表
这些基本操作等会我们在单链表用C语言实现的过程中便会体现

三、单链表用C语言的代码实现

类比于我们之前实现顺序表,同样是多文件操作

SList.h:主要存放代码实现过程中需要的头文件,同时充当目录

SList.c:函数的具体功能的实现

text.c:测试函数的功能,包含主函数

SList.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//定义链表的结构
typedef int SLTDataType;//方便类型的随时替换

typedef struct SListNode{
	SLDataType data;//数据
	struct SListNode* next;//指针记录下一个结点的地址
}SLTNode;

//打印
void SLTPrint(SLTNode* phead);//把头结点传递过去

//插入
void SLTPushBack(SLTNode** pphead,SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead,SLTDataType x);//头插

//删除
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删

//查找
void SLTFind(SLTNode* phead,SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x);

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos,SLTDataType x);

//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos);

//删除pos之后的结点
void SLTErase(SLTNode* pos);

//销毁链表
void SListDestroy(SLTNode** pphead);

SList.c

#include"SList.h"//包含头文件

void SLTPrint(SLTNode* phead)
{
	SLTNode* pcur = phead;//新设一个pcur指针用来遍历链表
	while(pcur)//pcur不为空就一直循环
	{
		printf("%d->",pcur->data);
	}
	printf("NULL\n");
}

//申请新结点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//动态申请一块空间
	if(node == NULL)
	{
		perror("malloc fail!");
		exit(1);//退出
	}
	//成功申请一个结点
	node->data = x;
	node->next = NULL;
}

//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x)
{
	//pphead为指向链表的头结点的指针,这样设计的目的是为了在函数内部可以修改链表的头指针
	assert(pphead);
	//pphead-->%plist
	//*pphead-->plist

	SLTNode* newnode = SLTBuyNode(x);
	if(*pphead == NULL)//如果为空 直接把赋值给新结点
	{
		*pphead = newnode;
	}
	else
	{
		//找尾结点
		SLTNode* pcur = *pphead;
		while(pcur->next)//pcur的下一个指针不为空,就一直往下找
		{
			pcur=pcur->next;//pcur继续往下遍历
		}
		pcur->next = newnode;//找到就把newnode赋值过去
	}
	
}

//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

//尾删
void SLTPopBack(SLTNode** pphead)
{
	//链表不能为空
	assert(pphead && *pphead);
	//处理只有一个结点的情况
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//找出prev和ptail
		SLTNode* prev = *pphead;
		SLTNode* ptail = NULL;
		while(ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		prev->next = NULL;
		free(ptail);
		ptail = NULL;
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* next = (*pphead)->next;//先把头结点的下一个结点记录下来
	free(*pphead);
	*pphead = next;
	
}

//查找
SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{
	assert(pphead);
	SLTNode* pcur = phead;
	while(pcur)
	{
		if(pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead,SLTNode* pos,SLTDataType x)
{
	assert(pphead);
	assert(pos);
	
	if(pos == *pphead)//类似于头插
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* newnode = SLTBuyNode(x);
		//找到pos的前一个结点
		SLTNode* prev = *pphead;
		while(prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos,SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos结点
void SLTErase(SLTNode** pphead,SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if(pos == *pphead)//类似于头删
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while(prev->next = pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
	
}

//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
	
}

//销毁链表
void SListDestroy(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

text.c

#define _CRT_SECURE_NO_WARNINGS 
#include"SList.h"
//创建一个链表，并打印链表

void createSList()
{
	//链表是由一个一个的结点组成
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

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

	//第一个结点的地址作为参数传递过去
	SLTNode* plist = node1;
	SLTPrint(plist);
}

void SListTest01()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);//1->2->3->4->NULL

	//SLTPushBack(NULL, 3);
	//SLTPushFront(&plist, 1);
	//SLTPushFront(&plist, 2);
	//SLTPushFront(&plist, 3);
	//SLTPushFront(&plist, 4);
	//SLTPrint(plist); //4->3->2->1->NULL

	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//SLTPopBack(&plist);
	//SLTPrint(plist);
	//
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);
	//SLTPopFront(&plist);
	//SLTPrint(plist);

	//SLTNode* find = SLTFind(plist, 4);
	//if (find == NULL)
	//{
	//	printf("未找到！\n");
	//}
	//else
	//{
	//	printf("找到了！\n");
	//}
	//SLTInsert(&plist, find, 11);//4->3->2->11->1->NULL
	//SLTInsertAfter(find, 11);
	//SLTPrint(plist);////1->11->2->3->4->NULL

	//SLTErase(&plist, find);// 1->2->3->NULL
	//SLTEraseAfter(find);

	//SLTPrint(plist);
	SListDestroy(&plist);
	SLTPrint(plist);
}

struct ListNode {
	int val;
	struct ListNode* next;
};

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
	//创建新链表
	ListNode* newHead, * newTail;
	newHead = newTail = NULL;
	//遍历原链表
	ListNode* pcur = head;
	while (pcur)
	{
		//找值不为val的节点，往新链表中进行尾插
		if (pcur->val != val)
		{
			//链表为空
			if (newHead == NULL)
			{
				newHead = newTail = pcur;
			}
			else
			{
				//链表不为空
				newTail->next = pcur;
				newTail = newTail->next;
			}
		}
		pcur = pcur->next;
	}
	return newHead;
}

void test01()
{
	ListNode* n1 = (ListNode*)malloc(sizeof(ListNode));
	n1->val = 1;
	ListNode* n2 = (ListNode*)malloc(sizeof(ListNode));
	n2->val = 6;
	ListNode* n3 = (ListNode*)malloc(sizeof(ListNode));
	n3->val = 1;
	ListNode* n4 = (ListNode*)malloc(sizeof(ListNode));
	n4->val = 6;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	//1->6->1->6

	ListNode* plist = n1;
	//构造一个链表
	removeElements(plist, 6);
	//1->1
}

int main()
{
	//createSList();
	//SListTest01();
	test01();
	return 0;
}

四、单链表的分类

根据结构：

简单单链表：每个结点包含数据和指向下一个结点的指针

带头结点的单链表：在链表前增加一个头结点，方便操作

根据连接方式：

单向链表：每个结点只指向下一个结点，无法向前遍历

循环单链表：最后一个结点指向头结点，形成一个环，可以从任意结点开始遍历

根据数据存储：

有序单链表：结点按特定顺序排列，方便查找

无序单链表：结点没有特定顺序，适合快速插入和删除

根据结点的数量：

固定长度单链表：结点数量在创建时固定，后续无法扩展

动态单链表：结点数量可以动态增删，根据需要进行内存分配

五、单链表的优缺点

1.优点

动态大小：单链表可以根据需要动态增加或减少结点，灵活性强，而不需要事先定义大小

插入和删除效率高：在链表中，插入和删除操作只需要改变相应结点的指针，不需要移动其他元素，因此时间复杂度为O(1)

节省内存：单链表不需要为每个元素分配连续的内存块，只需要为每个结点分配内存，因此在内存使用上更加灵活，适合不确定大小的情况

无需预留空间：链表在创建时不需要预留额外的空间来处理扩容的问题，这使得内存使用更加高效

简化实现特定算法：某些算法可以更容易地用链表实现，因为链表的插入和删除操作更加直接

方便实现双向遍历：虽然单链表本身是单向的，但可以很容易地扩展为双向链表，以支持双向链表，适应更多场景

不受容量限制：理论上，链表地长度仅受限于系统可用内存，因此可以处理比数组更大地数据集

2.缺点

查找效率低：单链表的查找操作需要从头结点开始逐个遍历，平均时间复杂度为O(n)，不如数组的O(1)访问效率

额外的内存开销：每个结点除了存储数据外，还需要存储指向下一个结点的指针，这在结点数量较多时会造成额外的内存消耗

无法随机访问：与数组不同，单链表不支持直接通过索引访问元素，需要从头结点开始遍历

反向遍历困难：单链表是单向的，因此无法直接从后往前遍历，如果需要反向遍历，需要额外的空间或其他数据结构

缓存局部性差：由于链表结点在内存中可能不是连续存储，访问结点时可能导致更多的缓存未命中，影响性能

内存碎片化：频繁的插入和删除操作可能导致内存碎片化，影响后续内存分配效率

六、单链表的算法题整理

移除链表元素
题目要求：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点
思路：
首先创建一个新的单链表，用两个指针分别表示新链表的头和尾
再用一个指针指向原链表的头，用于遍历
只要值不等于val，就保存到新链表中
返回新链表的值

typedef struct ListNode ListNode;//定义一个ListNode结构体的别名

struct ListNode* removeElements(struct ListNode* head, int val) {
    //声明两个指针,用于构建一个新的链表
    ListNode* newHead, * newTail;
    newHead = newTail = NULL;//表示新链表为空

    ListNode* pcur = head;
    while (pcur)
    {
        //找不到值为val的结点，就往新链表中尾插
        if (pcur->val != val)
        {
            if (newHead == NULL)//当前新链表为空
            {
                newHead = newTail = pcur;//我们需要将当前结点设为新链表的头结点
            }
            else
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if (newTail)//检查新链表是否非空
    {
        newTail->next = NULL;
    }
    return newHead;
}

反转链表
题目要求：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
思路:通过三指针直接交换，不用创建新链表

typedef struct ListNode ListNode;

struct ListNode* reverseList(struct ListNode* head) {
    //处理空结点
    if (head == NULL)
    {
        return head;
    }
    //声明三个指针，用于在反转链表过程中跟踪结点
    ListNode* n1, * n2, * n3;
    //n1表示新链表的尾部，n2表示当前正在处理的结点，n3表示下一个要处理的结点
    n1 = NULL, n2 = head, n3 = n2->next;
    while (n2)//只要n2不为空，就继续执行循环，遍历整个链表
    {
        //表示当前指针的next指针指向前一个结点
        n2->next = n1;
        n1 = n2;//将前一个结点的值赋给后一个
        n2 = n3;//n2继续往后走
        if (n3)
        {
            n3 = n3->next;//n3也往后走
        }
    }
    return n1;//n1指向的是原链表的最后一个结点，即反转后的链表的头结点
}

返回链表的中间结点
题目要求：给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点
思路:通过快慢指针，快指针每次走两步，慢指针每次走一步，当快指针遍历到链表结尾的时候，慢指针正好走到中间结点
详细一点解释是：假设链表的长度是n，快指针走的步数是2/n，即 2*慢 = 快

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow = head, * fast = head;
    //fast每次走两步，因此需要检查它是否为空，以避免访问空指针
    //为了访问fast->next->next 必须确保fast->next 不为空 如果fast到达链表的末尾，fast->next会为空，直接访问fast->next->next会出现问题
    //而且这样也适应了链表的不同长度
    //注意不能改成 fast->next && fast 当fast为空时，直接访问 fast->next 会报错
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

返回倒数第K个结点
题目要求：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值
思路:通过快慢指针，快指针先走K步，然后快慢指针一起走，直到快指针走到空，慢指针就走到倒数第K个结点，返回慢指针所指的值

typedef struct ListNode ListNode;

int kthToLast(struct ListNode* head, int k) {
    ListNode* slow = head;
    ListNode* fast = head;

    for(int i = 0;i < k;i++)
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    while(fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow->val;
}

合并两个有序数组
题目要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路:创建新的链表，遍历原链表，比较大小，谁小谁尾插到新链表

typedef struct ListNode ListNode;

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }

    ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* newTail = newHead;

    ListNode* l1 = list1;
    ListNode* l2 = list2;

    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            //l1尾插到新链表中
            newTail->next = l1;
            
            l1 = l1->next;
        }
        else
        {
            newTail->next = l2;
            
            l2 = l2->next;
        }
        newTail = newTail->next;

    }
    if(l1)
    {
        newTail->next = l1;
    }
    else if(l2)
    {
        newTail->next = l2;
    }

    ListNode* ret = newHead->next;
    free(newHead);
    return ret;
    
}

链表分割
题目要求：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路:创建两个链表，将小于x值的链表尾插到小链表中，大于x的值尾插到大链表中，最后将小链表的尾连接到大链表的尾，要将大链表的尾置为空

#include <cstdlib>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* lessHead,*lessTail;
        lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));

        ListNode* greaterHead,*greaterTail;
        greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));

        ListNode* pcur = pHead;
        while(pcur)
        {
            if(pcur->val < x)
            {
                lessTail->next = pcur;
                lessTail = lessTail->next;
            }
            else 
            {
                greaterTail->next = pcur;
                greaterTail = greaterTail->next;
            }
            pcur = pcur->next;
        }
        greaterTail->next = NULL;

        lessTail->next = greaterHead->next;
        ListNode* ret = lessHead->next;
        free(lessHead);
        free(greaterHead);
        lessHead = greaterHead = NULL;

        return ret;
    }
};

链表的回文结构
题目要求：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
思路:利用我们上面所提到的反转链表的思想，先利用快慢指针找到中间结点，将中间结点之后的链表进行反转

class PalindromeList {
public:
    ListNode* findMidNode(ListNode* phead)
    {
        ListNode* slow = phead;
        ListNode* fast = phead;

        while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* reverseList(ListNode* phead)
    {
        ListNode* n1,*n2,*n3;
        n1 = NULL,n2 = phead,n3 = n2->next;
        while (n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3)
            {
                n3 = n3->next;
            }
        }
        return n1;
    }

    bool chkPalindrome(ListNode* A) {
        // write code here
        //1.找到中间结点
        ListNode* mid = findMidNode(A);
        //2.反转链表
        ListNode* right = reverseList(mid);
        //3.原链表和反转链表进行比较
        ListNode* left = A;

        while (right) {
            if(left->val != right->val)
            {
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
        
    }
};

后记

单链表的知识我们就先在此告一段落
后面还会有链表OJ题目的更新和新的单链表知识点随机掉落~
之后我们应该就该对双链表，栈，队列等知识一一进行展开了
大家可以持续关注，会稳定更新~

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。