链表的详解

一、不带头单链表

   链表节点创建与销毁

   尾插尾删

   头插头删

   随机位置插入与删除

   缺陷

   全部代码

二、链表带环问题

三、带头双链表

   初始准备

   链表节点创建与销毁

   尾插尾删

   头插头删

   随机位置插入与删除

   全部代码

四、对比顺序表与链表

一、不带头单链表

初始准备

不带头单链表，首先创建了一个结构体，而该结构体有2个成员，一个用来存储数据(data)，另一个用来存储下一个数据的地址(next)，从而使得两个结构体变量连接起来，如下图*

为了书写简洁，用typedef将其结构体类型名修改

又为了能方便存储不同类型的数据，不至于把程序写的太呆板，采用typedef将其类型名修改，要存储其他类型的数据时，只要修改即可。如下图，存储浮点型数据时，只要int改为float或double

打印链表

每打印一个数据，指针就向后移动一步

注意：打印因为没有改变链表，所以只需传一级指针即可

** 上图也可以不用创建cur,直接用phead**

指针传参

无头单链表中，只有打印和查找数据时，不用传二级指针，其余时候都要传二级，因为要改变链表

**上述两种都是传递地址，在C语言中要改变实参时，必须传地址才行 **

链表节点创建与销毁

先用malloc开辟一块空间，大小是结构体的大小，然后再做判断，最后再对成员进行初始化即可

链表销毁时，要采用两个指针，一个在前，一个在后，要不然释放空间后，就成了野指针，找不到后面的数据了，把最后一个数据销毁后，再将其置空即可

尾插尾删

首先判断链表是否为空(没有数据)，没有就直接添加数据即可，有就找尾，最后一个数据的next指针为空，就表示找到了，直接连接数据紧接其后即可

要分两种情况，一种是只有一个节点时，另一种是多个节点时

多个节点时，尾删也需要两个指针，否则在删除最后一个数据后，要把前一个数据的next置空，否则next就是野指针了，下一次删除就找不到尾了

一个节点时，直接释放，置空即可

头插头删

头插时不需要判断链表是否为空，只要创建新节点，让它指向头节点，再把新节点的地址赋值给头节点的指针，作为新的头节点指针

头删时要判断链表是否为空，毕竟空链表不能删除

先用一个指针变量存储头节点的下一个节点的地址，再将头节点销毁，再将其前面创建的指针的值赋给头节点的指针

随机位置插入与删除

查找随机数，返回其地址，找不到就返回空指针，同样不需要传二级指针

在随机数的后面插入数据，找不到数据时，pos为空，所以断言判断一下。如下图，如果不多创建一个指针变量时，就需要先连线2，再连线1，因为先练线1时，就找不到cur2,指向的那个节点了；多创建一个变量保存节点地址，1、2那个先连都可以

在随机数的前面插入数据时，要分两种情况

第一种，随机数就是头节点的数据时，直接头插即可

第二种，找到pos的前一个节点，再创建节点，3个节点连接即可

在前面和后面插入两种方法对比，在后面插入明显更简单，效率也更高，因为不需要找前一个节点，这也是单链表的缺陷，双链表可以弥补这一缺陷

删除随机数后面的一节点的数据时，要作2次断言，第一个是随机数存不存在，第二个是随机数的下一个节点存不存在

删除随机数时，首先判断是不是随机数存不存在，同样有两种情况

第一种，随机数是头节点的数据时，直接头删即可

第二种，找到随机数的前一个节点，再连接，释放随机数的节点即可

缺陷：

每存一个数据，都要存一个指针去链接后面数据节点

不支持随机访问(用下标去访问第i个)

全部代码

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DataType;

typedef struct SList
{
    DataType data;
    struct SList* next;
}SLT;

//创建节点
SLT* SListNode(DataType x);
//打印链表
void SListPrint(SLT* phead);
//销毁链表
void SListDestroy(SLT** pphead);
//尾插
void SListPushBack(SLT** pphead, DataType x);
//尾删
void SListPopBack(SLT** pphead);
//头插
void SListPushFront(SLT** pphead, DataType x);
//头删
void SListPopFront(SLT** pphead);
//查找随机数
SLT* SListFind(SLT* pphead, DataType pos);
//随机位置向后插入
void SListInsert(SLT* pos, DataType x);
//随机位置的数的删除
void SListDeleteAfter(SLT* pos);
//随机位置向前插入
void SListInsertPrev(SLT** pphead, SLT* pos, DataType x);
//随机位置数据的删除
void SListDelete(SLT** pphead, SLT* pos);

//定义文件
#include"SList.h"

SLT* SListNode(DataType x)
{
    SLT* newnode = (SLT*)malloc(sizeof(SLT));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

void SListPushBack(SLT** pphead, DataType x)
{
    if (*pphead == NULL)
    {
        *pphead = SListNode(x);
    }
    else
    {
        SLT* cur = *pphead;
        while (cur->next)
        {
            cur = cur->next;
        }
        cur->next = SListNode(x);
    }
}

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

void SListDestroy(SLT** pphead)
{
    assert(pphead);
    SLT* cur = *pphead;
    SLT* prev = *pphead;
    while (cur)
    {
        prev = cur;
        cur = cur->next;
        free(prev);
    }
    *pphead = NULL;
}

void SListPopBack(SLT** pphead)
{
    assert(*pphead);
    SLT* cur = *pphead;
    SLT* prev = NULL;
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        while (cur->next)
        {
            prev = cur;
            cur = cur->next;
        }
        free(cur);
        cur = NULL;
        prev->next = NULL;
    }
}

void SListPushFront(SLT** pphead, DataType x)
{
    SLT* cur = *pphead;
    SLT* newnode = SListNode(x);
    newnode->next = cur;
    *pphead = newnode;
}

void SListPopFront(SLT** pphead)
{
    assert(*pphead);
    SLT* cur = (*pphead)->next;
    free(*pphead);
    *pphead = cur;
}

SLT* SListFind(SLT* phead, DataType pos)
{
    assert(phead);
    SLT* cur = phead;
    while (cur)
    {
        if (cur->data == pos)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

void SListInsert(SLT* pos, DataType x)
{
    assert(pos);
    SLT* cur2 = pos->next;
    SLT* newnode = SListNode(x);
    newnode->next = cur2;
    pos->next = newnode;
}

void SListDelete(SLT** pphead, SLT* pos)
{
    assert(pphead);
    assert(pos);
    if (pos == *pphead)
    {
        SListPopFront(pphead);
    }
    else
    {
        SLT* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}
void SListDeleteAfter(SLT* pos)
{
    assert(pos);
    assert(pos->next);
    pos->next = pos->next->next;
    free(pos->next);
    pos->next = NULL;
}

void SListInsertPrev(SLT** pphead, SLT* pos, DataType x)
{
    SLT* newnode = SListNode(x);
    if (*pphead == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    else
    {
        SLT* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        newnode->next = pos;
        prev->next = newnode;
    }
}

//测试文件
#include"SList.h"
void test1()
{
    SLT* 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);
    SListPopBack(&plist);
    SListPopBack(&plist);

    SListPrint(plist);
}
void test2()
{
    SLT* plist = NULL;
    SListPushFront(&plist, 1);
    SListPushFront(&plist, 2);
    SListPushFront(&plist, 3);
    SListPushFront(&plist, 4);
    SListPrint(plist);

    SListPopFront(&plist);
    SListPopFront(&plist);
    SListPopFront(&plist);
    SListPopFront(&plist);
    SListPrint(plist);

}
void test3()
{
    SLT* plist = NULL;
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);

    SLT* pos = SListFind(plist, 3);
    SListInsert(pos, 8);
    
    /*SListDeleteAfter(pos);
    SListPrint(plist);*/

    SListInsertPrev(&plist, pos, 15);
    SListPrint(plist);

    SListDelete(&plist, pos);
    SListPrint(plist);

    SListDestroy(&plist);
}
int main()
{
    //test1();
    //test2();
    test3();
    return 0;
}

二、链表带环问题

结论一：

快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表 带环则一定会在环中相遇

证明如下图：

至于fast走4步，slow走1步的情况下，读者可依照上图依葫芦画瓢分析

结论二：

fast与slow一定会在环的入口处相遇

三、带头双链表

初始准备

首先创建一个结构体，有3个成员，第一个是存储数据，2个指针，一个指向前节点，另一个指向后节点，用typedef将其结构体类型名修改，使其简洁，方便使用

用typedef将其数据类型名修改，便于存储其它数据时，不用大幅度改动

链表节点创建与销毁

首先创建一个头节点，用malloc开辟空间，不存储数据，前后指针均指向本身

然后用malloc创建其它节点，添加节点时，只需调用函数即可，前后指针均置为NULL

销毁双链表时，从头节点后的节点开始销毁，最后再销毁头节点

打印双链表

尾插尾删

尾删不能把头节点给删了，所以需断言

头插头删

头删不能把头节点给删了，所以需断言

随机位置插入与删除

查找

找不到返回NULL，找得到返回其地址

全部代码

//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DataType;

typedef struct List
{
    DataType data;
    struct List* prev;
    struct List* next;
}LT;

//初始化双链表
LT* LTInit();
//创建节点
LT* LTNode(DataType x);
//打印双链表
void LTPrint(LT* phead);
//尾插
void LTPushBack(LT* phead, DataType x);
//尾删
void LTPopBack(LT* phead);
//头插
void LTPushFront(LT* phead, DataType x);
//头删
void LTPopFront(LT* phead);
//查找
LT* LTFind(LT* phead, DataType pos);
//随机位置插入数据
void LTInsert(LT* pos, DataType x);
//随机位置的数据删除
void LTDelete(LT* pos);
//销毁双链表
void LTDestroy(LT* phead);

//定义文件
#include"List.h"

LT* LTInit()
{
    LT* head = (LT*)malloc(sizeof(LT));
    if (head == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    head->next = head;
    head->prev = head;
    return head;
}

LT* LTNode(DataType x)
{
    LT* newnode = (LT*)malloc(sizeof(LT));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

void LTPrint(LT* phead)
{
    assert(phead);
    LT* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void LTPushBack(LT* phead, DataType x)
{
    assert(phead);
    LT* newnode = LTNode(x);
    LT* tail = phead->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

void LTPopBack(LT* phead)
{
    assert(phead);
    assert(phead->next != phead);
    LT* tail = phead->prev;
    LT* prevtail = phead->prev->prev;
    phead->prev = prevtail;
    prevtail->next = phead;
    free(tail);
    tail = NULL;
}

void LTPushFront(LT* phead, DataType x)
{
    assert(phead);
    LT* newnode = LTNode(x);
    LT* begintail = phead->next;
    phead->next = newnode;
    newnode->prev = phead;
    begintail->prev = newnode;
    newnode->next = begintail;
}

void LTPopFront(LT* phead)
{
    assert(phead);
    assert(phead->next != phead);
    LT* begin = phead->next;
    LT* cur = begin->next;
    phead->next = cur;
    cur->prev = phead;
    free(begin);
    begin = NULL;
}

LT* LTFind(LT* phead, DataType pos)
{
    assert(phead);
    LT* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == pos)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

void LTInsert(LT* pos, DataType x)
{
    assert(pos);
    LT* newnode = LTNode(x);
    LT* prevpos = pos->prev;
    prevpos->next = newnode;
    newnode->prev = prevpos;
    pos->prev = newnode;
    newnode->next = pos;
}

void LTDelete(LT* pos)
{
    assert(pos);
    LT* prevpos = pos->prev;
    LT* tailpos = pos->next;
    prevpos->next = tailpos;
    tailpos->prev = prevpos;
    free(pos);
    pos = NULL;
}

void LTDestroy(LT* phead)
{
    assert(phead);
    LT* cur = phead->next;
    while (cur != phead)
    {
        LT* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
    phead = NULL;
}

//测试文件
#include"List.h"
void test1()
{
    LT* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);
    LTPushBack(plist, 5);
    LTPushBack(plist, 6);
    LTPushBack(plist, 7);
    LTPrint(plist);

    LTPopBack(plist);
    LTPopBack(plist);
    LTPopBack(plist);
    LTPopBack(plist);
    //LTPopBack(plist);
    //LTPopBack(plist);
    //LTPopBack(plist);
    //LTPopBack(plist);

    LTPrint(plist);
}
void test2()
{
    LT* plist = LTInit();
    LTPushFront(plist, 1);
    LTPushFront(plist, 2);
    LTPushFront(plist, 3);
    LTPushFront(plist, 4);
    LTPushFront(plist, 5);
    LTPushFront(plist, 6);
    LTPushFront(plist, 7);
    LTPrint(plist);

    LTPopFront(plist);
    LTPopFront(plist);
    LTPopFront(plist);
    LTPopFront(plist);
    LTPopFront(plist);
    //LTPopFront(plist);
    //LTPopFront(plist);
    //LTPopFront(plist);

    LTPrint(plist);
}
void test3()
{
    LT* plist = LTInit();
    LTPushBack(plist, 1);
    LTPushBack(plist, 2);
    LTPushBack(plist, 3);
    LTPushBack(plist, 4);

    LT* pos = LTFind(plist, 3);
    LTInsert(pos, 8);
    LTInsert(pos, 16);

    LTDelete(pos);
    LTPrint(plist);
    LTDestroy(plist);
}
int main()
{
    test1();
    //test2();
    //test3();
    return 0;
}

四、对比顺序表与链表

顺序表

优点：

支持随机访问。需要随机访问结构支持算法可以很好的适用

缺点：

头部中部插入删除时间效率低 O(n)

连续的物理空间，空间不够了以后需要增容：

增容有一定程度消耗

为了避免频繁增容，一般我们都按倍数去增容，用不完可能存在一定的空间浪费

链表(双向带头循环)

优点：

任意位置插入删除效率高 O(1)

按需申请释放空间

缺点：

不支持随机访问(用下标访问)。意味着：一些排序、二分查找等在这种结构上不适用

链表每存储一个值，同时要存储一个指针，也有一定的消耗