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

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

引用

CSDN

1.

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

链表是数据结构中一种重要的线性表实现方式，与顺序表相比，链表在插入和删除操作上具有更高的效率。本文将详细介绍链表的基本概念、分类以及单链表的具体实现方法。

一、链表的概念和结构

链表是一种形式上连续，物理空间上可能不连续的结构，就像一个小火车一样。链表通过指针来连接各个节点，每个节点包含数据域和指向下一个节点的指针域。

图中的phead指针中存放的是第一个节点的地址，根据这个地址可以找到第一个节点，然后通过节点中的指针找到下一个节点，以此类推，直到找到存放空地址的节点。

二、链表的分类

链表的结构多种多样，常见的有以下几种：

• 单向链表
• 双向链表
• 循环链表
• 带头结点的链表

虽然链表结构如此之多，但实际应用中常用的主要是单向链表和双向链表。

三、单链表的实现

单链表是最基本的链表结构，它是一种无头、单向、非循环的链表。

动态申请节点

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);
    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 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);
    }
}

总结

链表和顺序表是两种重要的线性表实现方式，链表在插入和删除操作上具有更高的效率。通过本文的介绍，相信读者已经对链表有了一个全面的了解。如果想了解更多关于顺序表的内容，可以参考相关资料。

本文原文来自CSDN