C语言链表

链表简述

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

链表的分类与实现

链表的分类

链表有八大类。

链表主要分：单链表，带哨兵位头节点的链表，双向链表，循环链表。

把后面三种排列组合就可以得到其他四种不同的组合(单链表是最基础的所以不算)。

这里着重讲前面四种链表，其他的可以依葫芦画瓢。

单链表

单链表是链表中最基本的链表。人如其名，就是单纯的一个链表没什么花里胡哨的操作。

为了好理解我画了一个形象一点的图

下面直接上代码，边看代码边理解

1
2
3
4
5
6
7
8
typedef int LinkListDate;

//链表节点
typedef struct LinkListNode
{
    LinkListDate x; //数据
    struct LinkListNode* next;  //next指针
}Node;

单链表节点的结构就这样，去创建出一个个链表节点，再把它们通过next指针首尾链接起来就是单链表。

接下来看单链表的几种常规操作

后面几种链表的操作和单链表差不多。所以这里要好好看好好学才能给后面的操作打下坚实的基础。QWQ

1.初始化

链表的初始化：创建一个头指针，创建一个链表节点，并把头指针指向链表节点。

注意

创建节点时就把数据存入链表节点了。

在创建链表的时候next指针一定要置空(next == NULL)，预防野指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node* NewNode(LinkListDate x)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
    assert(NewNode);
    NewNode->x = x;
    NewNode->next = NULL;
    return NewNode;
}

Node* CreateLinkList(LinkListDate x)
{
    Node* phead = NewNode(x);
    return phead;
}

2.单链表的销毁

这里用到了二级指针，因为要把原本的头指针head指向NULL，所以用到了二级指针。一级指针不行，因为函数传参数时，形参只是实参的一份拷贝，就算把形参指向NULL，实参也不会有任何变化。所以这里要用二级指针。

1
2
3
4
5
6
7
8
9
void DestoryLinkList(Node** pphead)
{
    *pphead = NULL;    //二级指针，head指向NULL
}

void DestoryLinkList1(Node* phead)
{
    phead = NULL;   //实参head不会改变
}

这里用了快慢指针，一个指针在前，一个指针在后。

后面的fast先保存一下slow的next，然后free掉slow，再把slow赋值给fast。重复以上操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void DestoryLinkList(Node** pphead)
{
    assert(pphead);
    assert(*pphead);
    Node* fast, * slow;
    slow = *pphead;
    fast = (*pphead)->next;
    while (slow != NULL)
    {
        free(slow);
        slow = fast;
        if(slow != NULL)
        fast = slow->next;
    }
    slow = NULL;
    *pphead = NULL;    //二级
}

3.单链表的头插尾插

这里用到了二级指针，因为要把原本的头指针head重新指向新节点，所以用到了二级指针。一级指针不行，因为函数传参数时，形参只是实参的一份拷贝，就算把形参指向新节点，实参也不会有任何变化。所以这里要用二级指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void LinkListPushBack(Node** pphead, LinkListDate x)//尾插
{
    assert(pphead);
    Node* NewBack = NewNode(x);

    if (*pphead == NULL)//初始没有节点
    {
        *pphead = NewBack;
    }
    else
    {
        Node* Back = *pphead;
        while (Back->next)//找尾
        {
            Back = Back->next;
        }
        Back->next = NewBack;
    }
}

void LinkListPushFront(Node** pphead, LinkListDate x)//头插
{
    assert(pphead);
    Node* NewFront = NewNode(x);
    NewFront->next = *pphead;
    *pphead = NewFront;    //这里用二级
}

4.单链表的头删，尾删

这里同样使用了二级指针，但是之前已经讲过了，这里就不赘述了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void LinkListPopBack(Node** pphead)//尾删
{
    assert(pphead);
    assert(*pphead);
    Node* Back = *pphead;
    if (Back->next)
    {
        while (Back->next->next)
        {
            Back = Back->next;
        }
        free(Back->next);
        Back->next = NULL;
    }
    else
    {
        free(*pphead);
        *pphead = NULL;
    }
}

void LinkListPopFront(Node** pphead)//头删
{
    assert(pphead);
    assert(*pphead);
    Node* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

5.单链表的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Node* LinkListFind(Node* phead, LinkListDate x)
{
    assert(phead);
    Node* find = phead;
    while (find)
    {
        if (find->x = x)
        {
            return find;
        }
        find = find->next;
    }
    return NULL;
}

6.单链表在pos位置之后插入

单链表因为结构的特性，只能在pos位置之后插入，在pos位置，pos位置之前插入都不行。因为找不到指向pos的前一个指针。

1
2
3
4
5
6
7
void LinkListInsertAfter(Node* pos, LinkListDate x)
{
    assert(pos);
    Node* AfterNode = NewNode(x);
    AfterNode->next = pos->next;
    pos->next = AfterNode;
}

7.单链表删除pos位置之后的元素

1
2
3
4
5
6
7
8
9
void LinkListEraseAfter(Node* pos)
{
    assert(pos);
    Node* EraseNode = pos->next;
    assert(EraseNode);
    pos->next = EraseNode->next;
    free(EraseNode);
    EraseNode = NULL;
}

以上就是单链表的各种操作，下面是验证代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main()
{
    Node* head = CreateLinkList(1);

    //头插尾插
    PrintLinkList(head);
    LinkListPushBack(&head, 2);
    LinkListPushFront(&head, 3);
    PrintLinkList(head);

    //头删尾删
    LinkListPopBack(&head);
    LinkListPopFront(&head);
    PrintLinkList(head);

    //查找
    LinkListPushBack(&head, 2);
    printf("%d\n", LinkListFind(head, 2)->x);

    //插入和删除,pos位置通过查找来实现
    LinkListInsertAfter(LinkListFind(head, 2), 3);
    PrintLinkList(head);
    LinkListEraseAfter(LinkListFind(head, 2));
    PrintLinkList(head);

    DestoryLinkList(&head);
    return 0;
}

带哨兵位头节点的链表

带哨兵位头节点的链表，就是在单链表的基础上，在单链表的头加一个空节点，这个节点本身没有什么意义。但是在进行增删查改的时候我们会方便很多，看看之前单链表的操作我们是不是要去判断链表为空的情况，但是加了哨兵位头节点，我们就可以不用去判断，因为不可能为空哨兵位一直都在。

并且，我们可以把哨兵位节点的数据部分作为链表长度size的载体，在创建节点时就去对size++，删除时对size–，这样再去求链表长度时就可以直接从哨兵位节点把size调出来。

总结一下，增加哨兵位头节点可以降低我们增删查改的操作复杂度。

详情可以去看这位博主的博客

1
2
3
4
5
6
7
8
9
对于创建一个新的链表：
1、没有哨兵节点时，添加一个节点要先判断是否是第一个节点，并单独保留第一个节点的指针，以便于返回整个链表的头指针。
2、有哨兵节点时，链表头是固定的，不可能为空，后续的节点都是链接在前一个节点的，不需要单独判断是否为头节点。

对于插入一个节点
有哨兵节点时，不需要判断链表为空和插入点在第一个位置节点的情况。

对于删除指定位置的节点
有哨兵节点时，不需要判断链表为空和删除第一个位置节点的情况。

双向链表

双向链表，就是在节点里再加一个指向上一个节点的指针。

1
2
3
4
5
6
7
8
typedef int LinkListDate;

typedef struct DoubleListNode
{
    LinkListDate x;//数据
    struct DoubleListNodee* left;//指向前一节点
    struct DoubleListNode* right;//指向后一节点
}DoubleNode;

有了这个指向上一节点的指针，对于单链表来说无疑是一次大加强。不足的就是是结构和操作变复杂了，占用内存也更大。这下不仅要考虑指向下一个节点的指针还要照顾指向前一个节点的指针，但是支持了在pos位置的操作，可以从前往后遍历，也可以从后往前遍历。

循环链表

循环链表，就是把最后一个节点的next指针指向头指针。当然，如果是双向链表还要把头节点指向上一个节点的指针left指向最后一个节点。

这个就没什么说的了，就是可以支持循环遍历。（在写代码操作时注意尾插尾删的细节）

结束总结

谢谢你能看到最后，虽然单链表后面的东西我写得不是很多，但是有些细节我认为还是写清楚了的，希望你能通过我的这篇文章学到东西。QWQ