资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

数据结构——链表（超详细解读）

创作时间:

作者:

@小白创作中心

数据结构——链表（超详细解读）

引用

CSDN

https://blog.csdn.net/2303_81146519/article/details/142530281

链表是一种常见的数据结构，它通过指针将数据元素链接在一起，形成一个线性序列。与顺序表不同，链表的元素在内存中可以是不连续的，这使得链表在插入和删除操作上具有更高的效率。本文将详细介绍链表的基本概念、分类以及单链表的各种操作实现。

一、链表的概念和结构

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表的基本组成单元）组成，结点可以在运行时动态生成。

图中的phead指针中存放的是第一个结点的地址，根据这个地址可以找到这个结构体，又因为这个结构体中存放了下一个结构体的地址，所以又可以找到第二个结构体，循环往复就可以找到所有的结点，直到存放空地址的结构体。

注：图中的箭头实际上是不存在的，这里只是为了方便理解。

注意：

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

二、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

虽然链表结构如此之多，但是我们常用的就只有两种：

单链表：无头+单向+非循环
双链表：无头+双向+非循环

三、单链表的实现

所谓单链表就是无头+单向+非循环链表。

动态申请节点

SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

单链表查找

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
    assert(plist);
    SListNode* cur = plist;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

单链表的尾插

void SListPushBack(SListNode** pplist, SLTDateType x)
{
    SListNode* newnode = BuySListNode(x);
    if (*(pplist) == NULL)
    {
        *pplist = newnode;
    }
    else
    {
        SListNode* tail = *pplist;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

单链表的头插

void SListPushFront(SListNode** pplist, SLTDateType x)
{
    SListNode* newnode = BuySListNode(x);
    if (*pplist == NULL)
    {
        *pplist = newnode;
    }
    else
    {
        newnode->next = *pplist;
        *pplist = newnode;
    }
}

单链表的尾删

void SListPopBack(SListNode** pplist)
{
    assert(*pplist);
    if ((*pplist)->next == NULL)
    {
        free(*pplist);
        *pplist = NULL;
    }
    else
    {
        SListNode* tail = *pplist;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

单链表的头删

void SListPopFront(SListNode** pplist)
{
    assert(*pplist);
    if ((*pplist)->next == NULL)
    {
        free(*pplist);
        *pplist = NULL;
    }
    else
    {
        SListNode* next = (*pplist)->next;
        free(*pplist);
        *pplist = next;
    }
}

单链表在pos位置之后插入

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    SListNode* next = pos->next;
    pos->next = newnode;
    newnode->next = next;
}

单链表在pos位置之前插入

void SListInsertFront(SListNode** pplist, SListNode* pos, SLTDateType x)
{
    assert(pos);
    assert(*pplist);
    if (pos == *pplist)
    {
        SListPushFront(pplist, x);
    }
    else
    {
        SListNode* prev = *pplist;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        SListNode* newnode = BuySListNode(x);
        newnode->next = pos;
        prev->next = newnode;
    }
}

删除pos位置的值

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

单链表的销毁

void SListDestroy(SListNode** pplist)
{
    assert(*pplist);
    while (*pplist)
    {
        SListNode* prev = *pplist;
        *pplist = (*pplist)->next;
        free(prev);
    }
}

四、完整代码

SList.h

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

typedef int SLTDateType;
typedef struct SListNode
{
    SLTDateType data;
    struct SListNode* next;
} SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsertFront(SListNode** pplist, SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 删除pos位置
void SListErase(SListNode** pplist, SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);

SList.c

#include "SList.h"

void SListPrint(SListNode* plist)
{
    assert(plist);
    while (plist)
    {
        printf("%d ", plist->data);
        plist = plist->next;
    }
    printf("NULL\n");
}

SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
    assert(newNode);
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

void SListPushBack(SListNode** pplist, SLTDateType x)
{
    SListNode* newNode = BuySListNode(x);
    if (*pplist == NULL)
    {
        *pplist = newNode;
    }
    else
    {
        SListNode* tail = *pplist;
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newNode;
    }
}

void SListPushFront(SListNode** pplist, SLTDateType x)
{
    SListNode* newNode = BuySListNode(x);
    newNode->next = *pplist;
    *pplist = newNode;
}

void SListPopBack(SListNode** pplist)
{
    assert(*pplist);
    if ((*pplist)->next == NULL)
    {
        free(*pplist);
        *pplist = NULL;
    }
    else
    {
        SListNode* tail = *pplist;
        while (tail->next->next != NULL)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

void SListPopFront(SListNode** pplist)
{
    assert(*pplist);
    SListNode* next = (*pplist)->next;
    free(*pplist);
    *pplist = next;
}

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
    assert(plist);
    while (plist)
    {
        if (plist->data == x)
        {
            return plist;
        }
        plist = plist->next;
    }
    return NULL;
}

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    SListNode* next = pos->next;
    pos->next = newnode;
    newnode->next = next;
}

void SListInsertFront(SListNode** pplist, SListNode* pos, SLTDateType x)
{
    assert(pos);
    assert(*pplist);
    if (pos == *pplist)
    {
        SListPushFront(pplist, x);
    }
    else
    {
        SListNode* prev = *pplist;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        SListNode* newnode = BuySListNode(x);
        newnode->next = pos;
        prev->next = newnode;
    }
}

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

void SListDestroy(SListNode** pplist)
{
    assert(*pplist);
    while (*pplist)
    {
        SListNode* prev = *pplist;
        *pplist = (*pplist)->next;
        free(prev);
    }
}

链表和顺序表是两种常见的线性数据结构，它们各有优劣。链表在插入和删除操作上具有更高的效率，而顺序表在随机访问上具有优势。理解这两种数据结构的原理和使用场景，对于编写高效的数据处理程序至关重要。