AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【DS】单链表@线性表 —— 增删查改

2022-07-29 78
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 单链表

@TOC

嘿嘿：上次实现单链表已经是两个月之前的事儿了，今儿拿出来再写，思路还是在，但确实忘掉了一些细节，一上午出现了各种小问题，全都是自己一个个调出来的，这种快感不是别的什么事情可以代替的。同时也发现，当初觉得想不到的东西，现在看也就是理所当然，这就是螺旋式上升吧:ram:！

0. 引

上文说到顺序表缺陷 ——

:snowflake:1. 空间不够需要 增容，增容是要付出代价的。
:snowflake:2. 为了避免频繁扩容，我们基本都是按倍数去扩（比如扩2倍），这又可能会造成一定的 空间浪费。
:snowflake:3. 顺序表要求数据从开始位置保持连续，那么中间和头部的插入和删除，都需要挪动数据，时间复杂度为 O(N)， 效率不高。

为此，我们引入了链表。

1. 链表的概念和结构

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

  • [ ] 逻辑图 —— 想象出来的形象方式表示

<img src=" title="">

  • [ ] 物理图 —— 内存中的真实存储 —— 通过指针来存储下一个节点的地址，并不连续

<img src=" title="">

2. 链表的分类

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

  • [ ] 单向或双向

<img src=" title="">

  • [ ] 带头不带头

<img src=" title="">

  • [ ] 循环非循环

在这里插入图片描述

当然我们最常用的还是这两种 ——

  1. 无头单向非循环链表

<img src=" title="">

  • 结构简单，但缺陷还是很多（一会儿实现的时候你就知道啦），单纯单链表的增删查改意义不大。
  • 但是还是要写，可能正因为它的缺陷，很多oj题考察的都是单链表
  • 更多的是做更复杂数据结构的子结构，比如哈希桶、邻接表。
  1. 带头双向循环链表

<img src=" title="">

  • 结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。
  • 另外这个结构虽然复杂，却也是无死角的结构，用代码实现时会发现结构会带来很多优势，非常爽，后面我们代码实现了就知道了。

3. 链表的实现

文末领取头文件大家自己写，自己写自己调时候思路是最清晰的，具体实现中每个思路和要注意的小点我都会写好（尤其是它第一次出现的时候）（这链表电脑画图老累了，主要是这个破箭头，ipad上写字还丑，我把我草纸的图弄进来了哦吼吼）红笔写的是边界，耦合色写的是变化过程哈哈。

3.1 打印、申请新节点、销毁

3.1.1 打印

<img src=" title="">

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

3.1.2 申请新节点

//申请新节点
SLTNode* BuyListNode(SListDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

3.1.3 销毁

  • 顺序表中申请的内存是连续的(realloc)，因此一次释放就行；而链表的空间申请时候就不连续，必须遍历回收。
  • free时，data和next都会被置成随机值，因此要记录next

<img src=" title="">

void SListDestroy(SLTNode** pphead)
{
    assert(pphead);
    // 链表的空间必须遍历回收，因为申请时候就不连续
    SLTNode* cur = *pphead;
    SLTNode* next = cur->next;// 记录下一个节点的位置
    while (next)
    {
        free(cur);
        cur = next;
        next = cur->next;
    }
    *pphead = NULL;
}

3.2 尾插、尾删

3.2.1 尾插

  • 为什么要传二级指针？尾插、包括后面的尾删头插头删、前面的销毁都需要传二级指针，而打印、查找就不需要。

:strawberry:实际上，二级指针就是为了处理首节点的改变（pList是链表的地址，类型为SLNode*），后面操纵的都是结构体就不需要。众所周知形参是实参的一份临时拷贝，形参的改变不会影响实参，因此必须传实参地址（在这里类型为SLNode**）以改变实参。

  • 解释一下assert(pphead);，像这种一定不为空的要断言一下，方便查错（传错）

<img src=" title="">

void SListPushBack(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    //1.空链表 - 尾插头结点的地址pList发生改变，因此需要传pList的地址
    //单拎出来处理
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //2.找尾
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = newnode;
}

3.2.2 尾删

  • 考虑链表为空 —— 断言结束（STL采取的就是这样粗暴的方式），毕竟，就是你用错了
  • 其余细节过程都在图中

<img src=" title="">

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);
    //1.空链表
    assert(*pphead);
    //2.删的只剩一个节点时
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }

    //3.
    //找尾的上一个
    SLTNode* prevtail = *pphead;
    SLTNode* tail = prevtail->next;
    while (tail->next != NULL)
    {
        prevtail = tail;
        tail = tail->next;
    }
    free(tail);
    prevtail->next = NULL;
}

3.3 头插、头删

3.3.1 头插

<img src=" title="">

void SListPushFront(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

3.3.2 头删

<img src=" title="">

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    //1.删空
    assert(*pphead);
    //2.
    SLTNode* headnext = (*pphead)->next;
    free(*pphead);
    *pphead = headnext;
}

3.4 查找、任意位置插入、任意位置删除

3.4.1 查找

SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
    SLTNode* cur = phead;
    if (phead == NULL)
    {
        //处理空链表，不然后面解引用可是又错了
        return NULL;
    }
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;//走到这儿还没找到
}

3.4.2 任意位置插入

<img src=" title="">

//在pos位置之前去插入一个节点--pos位置一般是find来的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{
    assert(pphead);
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    //1. 头插
    if (*pphead == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    //2.
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
}

<img src=" title="">

//在pos后边插入--这个更适合也更简单高效
//STL- insert_after
void SListInsertAfter(SLTNode* pos, SListDataType x)
{
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    SLTNode* posNext = pos->next;
    pos->next = newnode;
    newnode->next = posNext;
}

3.4.3 任意位置删除

<img src=" title="">

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);
    //删空
    assert(*pphead);
    //1.头删
    //带哨兵位的头的 -- 可以合并 头删与中间删 -- 逻辑结构一样，不会删完
    if (*pphead == pos)
    {
        *pphead = pos->next;
        free(pos);
        return;//自己调出来的
    }

    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = pos->next;
    free(pos);//注意顺序，对于我很简单啦
    //pos不置空也无所谓，毕竟在函数中是形参，形参的改变不会影响实参，处于好习惯，还是置空比较好
}

当然也可以实现删除pos后面的节点，这个功能很奇葩哈哈给pos不删pos

void SListEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);//一个节点
    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    //next = NULL;//出作用域即销毁，是野指针，但别人拿不到
}

4. 关于单链表的思考

4.1 链表优点

链表弥补了顺序表的缺陷

  1. 按需申请空间，不用了就释放（更合理的使用了空间），不存在空间浪费
  2. 头部和中间插入删除数据，不需要挪动数据

4.1 链表缺点

  1. 每一个数据，都要存一个指针链接后面的数据结点
  2. 不支持随机访问（用下标直接访问第i个元素），而有些算法，需要随机访问，如：二分查找、优化的快排

附录

SingleList.h

#pragma once

//无头单向非循环链表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SListDataType;

typedef struct SListNode
{
    SListDataType data;
    struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead);
//销毁
void SListDestroy(SLTNode** pphead);

//尾插
void SListPushBack(SLTNode** pphead, SListDataType x);
//尾删
void SListPopBack(SLTNode** pphead);
//头插
void SListPushFront(SLTNode** pphead, SListDataType x);
//头删
void SListPopFront(SLTNode** pphead);

//查找
SLTNode* SListFind(SLTNode* phead, SListDataType x);
//在pos位置之前去插入一个节点--pos位置一般是find来的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x);
//任意位置删
void SListErase(SLTNode** pphead, SLTNode* pos);
//在pos后边插入--这个更适合也更简单高效
void SListInsertAfter(SLTNode* pos, SListDataType x);

void SListEraseAfter(SLTNode* pos);
//void SListInsert(SLTNode* phead, SLTNode* pos,SListDataType x);
//void SListErase(SLTNode* phead, int pos);

SingleList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void SListDestroy(SLTNode** pphead)
{
    // 这个链表是
    // 链表的空间必须遍历回收，因为申请时候就不连续
    SLTNode* cur = *pphead;
    SLTNode* next = cur->next;// 记录下一个节点的位置
    while (next)
    {
        free(cur);
        cur = next;
        next = cur->next;
    }
    *pphead = NULL;
}

//申请新节点
SLTNode* BuyListNode(SListDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        printf("malloc failed\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void SListPushBack(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    //1.空链表 - 尾插头结点的地址pList发生改变，因此需要传pList的地址
    // **pphead
    if (*pphead == NULL)
    {
        *pphead = newnode;
        return;
    }
    //找尾
    SLTNode* tail = *pphead;
    while (tail->next != NULL)
    {
        tail = tail->next;
    }
    tail->next = newnode;
}

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);
    //1.空链表
    assert(*pphead);
    //2.删的只剩一个节点时
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
        return;
    }

    //3.普遍情况
    //找尾的上一个
    SLTNode* prevtail = *pphead;
    SLTNode* tail = prevtail->next;
    while (tail->next != NULL)
    {
        prevtail = tail;
        tail = tail->next;
    }
    free(tail);
    prevtail->next = NULL;
}


void SListPushFront(SLTNode** pphead, SListDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    //1.删空
    assert(*pphead);
    //2.
    SLTNode* headnext = (*pphead)->next;
    free(*pphead);
    *pphead = headnext;
}

SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
    SLTNode* cur = phead;
    if (phead == NULL)
    {
        //处理空链表，不然后面解引用可是又错了
        return NULL;
    }
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;//走到这儿还没找到
}

//在pos位置之前去插入一个节点--pos位置一般是find来的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{
    assert(pphead);
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    //1. 头插
    if (*pphead == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    //2.
    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = newnode;
    newnode->next = pos;
}

//在pos后边插入--这个更适合也更简单高效
//STL- insert_after
void SListInsertAfter(SLTNode* pos, SListDataType x)
{
    assert(pos);
    SLTNode* newnode = BuyListNode(x);
    SLTNode* posNext = pos->next;
    pos->next = newnode;
    newnode->next = posNext;
}


//任意位置删
void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead);
    assert(pos);
    //删空
    assert(*pphead);
    //1.头删
    //带哨兵位的头的 -- 可以合并 头删与中间删 -- 逻辑结构一样，不会删完
    if (*pphead == pos)
    {
        *pphead = pos->next;
        free(pos);
        return;//自己调出来的
    }

    SLTNode* posPrev = *pphead;
    while (posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    posPrev->next = pos->next;
    free(pos);//注意顺序，对于我很简单啦
    //pos不置空也无所谓，毕竟在函数中是形参，形参的改变不会影响实参，处于好习惯，还是置空比较好

}

void SListEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);//一个节点
    SLTNode* posNext = pos->next;
    pos->next = posNext->next;
    free(posNext);
    //next = NULL;//出作用域即销毁，是野指针，但别人拿不到
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

//测试尾插尾删
void testSingleList1()
{
    //指向单链表的指针 - 本质是存储这个单链表头结点的地址的指针变量
    SLTNode* pList;
    pList = NULL;//这个错是我调出来的
    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPrint(pList);

    SListPopBack(&pList);
    SListPopBack(&pList);
    SListPopBack(&pList);
    /*SListPopBack(&pList);
    SListPopBack(&pList);*/

    SListPrint(pList);
    SListDestroy(&pList);
}

//测试头插头删
void testSingleList2()
{
    SLTNode* pList;
    pList = NULL;
    SListPushFront(&pList, 1);
    SListPushFront(&pList, 2);
    SListPushFront(&pList, 3);

    SListPrint(pList);

    SListPopFront(&pList);
    SListPopFront(&pList);
    /*SListPopFront(&pList);
    SListPopFront(&pList);*/

    SListPrint(pList);

    SListDestroy(&pList);
}

//测试任意位置的插入、查找
void testSingleList3()
{
    SLTNode* pList;
    pList = NULL;
    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);

    SLTNode* ret = SListFind(pList, 2);
    if (ret == NULL)
    {
        printf("not found\n");
    }
    else
    {
        printf("%d\n", ret->data);
    }
    //SListInsert(&pList, ret, 0);//测试头插
    //SListInsert(&pList, ret, 3);

    SListInsertAfter(ret, 3);
    SListPrint(pList);
    SListDestroy(&pList);

}

//测试任意位置删
void testSingleList4()
{
    SLTNode* pList;
    pList = NULL;
    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPrint(pList);

    SLTNode* ret = SListFind(pList, 1);
    if (ret == NULL)
    {
        printf("not found\n");
    }
    else
    {
        printf("%d\n", ret->data);
    }
    //SListErase(&pList, ret);
    //SListErase(&pList, ret);

    SListEraseAfter(ret);
    SListPrint(pList);
    SListDestroy(&pList);

}

int main()
{
    //testSingleList1();
    //testSingleList2();
    //testSingleList3();
    testSingleList4();
    return 0;
}

下一篇来带头双向循环链表

本文完

文章标签：
C++
iOS开发
算法
存储
@浮光掠影
目录
相关文章
chian-ocean
|
3月前
|
存储
顺序表以及实现（结构篇）
顺序表以及实现（结构篇）
chian-ocean
55 11
sky_qiyi
|
5月前
|
存储 算法
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
sky_qiyi
29 0
yma16
|
6月前
|
存储
线性表、链表、栈和队列的初始化
线性表、链表、栈和队列的初始化
yma16
41 1
wan__cheng
|
6月前
|
存储
实现双链表的增删查改
实现双链表的增删查改
wan__cheng
32 0
pearlthriving
|
6月前
|
存储
实现顺序表的增删查改
现在让我们探索数据结构这个美妙的世界吧！
pearlthriving
35 0
阿甘兄
|
存储
05 顺序表的结构与实现
05 顺序表的结构与实现
阿甘兄
37 0
KOBE0824BRYANT
|
存储
单链表（增删查改）
单链表（增删查改）
KOBE0824BRYANT
48 0
KOBE0824BRYANT
|
存储
顺序表（增删查改）
顺序表（增删查改）
KOBE0824BRYANT
67 0
诺诺的包包
|
存储
【线性表】—动态顺序表的增删查改实现
【线性表】—动态顺序表的增删查改实现
诺诺的包包
132 0
愿荣
|
存储 Java
【DS】链表的介绍和实现(单/双链表)
【DS】链表的介绍和实现(单/双链表)
愿荣
96 0
【DS】链表的介绍和实现(单/双链表)