链表 -- 数据结构




概述



引言

C 语言中数组的缺陷: 

  • 静态空间, 一旦分配内存就不可以动态扩展
  • 如果内存分配过多, 会造成资源浪费
  • 对于头部插入/删除的效率低


什么是链表

链表是一种常用的数据结构, 它通过指针将一些数据节点, 连接成一个数据链. 相对于数组, 链表具有更好的动态性 (非顺序存储).

数据域用来存储数据, 指针域用于建立与下一个节点的联系.

建立链表时无需预先知道数据总量的. 可以随机的分配内存空间, 可以高效的在链表中任意位置实时插入或删除数据.



链表的组成

由节点组成

节点由数据域和指针域组成

  • 数据域是用来维护数据的
  • 指针域用来维护节点关系的



链表的分类


分类一


静态链表

在栈上分配内存


~ cat test.c
#include <stdio.h>

struct LinkNode
{
    int num; // 数据域
    struct LinkNode *next; // 指针域
};

void test()
{
    // 创建节点
    struct LinkNode node1 = {10, NULL};
    struct LinkNode node2 = {20, NULL};
    struct LinkNode node3 = {30, NULL};
    struct LinkNode node4 = {40, NULL};
    struct LinkNode node5 = {50, NULL};

    // 建立关系
    node1.next = &node2;
    node2.next = &node3;
    node3.next = &node4;
    node4.next = &node5;

    // 打印链表
    struct LinkNode *pCurrent = &node1;

    while (pCurrent != NULL)
    {
        printf("%d\n", pCurrent -> num);
        pCurrent = pCurrent -> next;
    }
}

int main()
{
    test();

    return 0;
}
~ gcc test.c -o test && ./test
10
20
30
40
50



动态链表

在堆区分配内存

~ cat test.c
#include <stdio.h>
#include <stdlib.h>

struct LinkNode
{
    int num; // 数据域
    struct LinkNode *next; // 指针域
};

void test()
{
    // 创建节点
    struct LinkNode *node1 = malloc(sizeof(struct LinkNode));
    struct LinkNode *node2 = malloc(sizeof(struct LinkNode));
    struct LinkNode *node3 = malloc(sizeof(struct LinkNode));
    struct LinkNode *node4 = malloc(sizeof(struct LinkNode));
    struct LinkNode *node5 = malloc(sizeof(struct LinkNode));

    // 给数据域赋值
    node1 -> num = 100;
    node2 -> num = 200;
    node3 -> num = 300;
    node4 -> num = 400;
    node5 -> num = 500;

    // 建立关系
    node1 -> next = node2;
    node2 -> next = node3;
    node3 -> next = node4;
    node4 -> next = node5;
    node5 -> next = NULL;

    // 打印链表
    struct LinkNode *pCurrent = node1;

    while (pCurrent != NULL)
    {
        printf("%d\n", pCurrent -> num);
        pCurrent = pCurrent -> next;
    }

    // 释放内存
    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(node5);
    node1 = NULL;
    node2 = NULL;
    node3 = NULL;
    node4 = NULL;
    node5 = NULL;
}

int main()
{
    test();

    return 0;
}
~ gcc test.c -o test && ./test
100
200
300
400
500



分类二


单向链表


双向链表


单向循环链表


双向循环链表


分类三


带头链表

固定一个节点作为头节点 (数据域不保存有效数据), 起一个标志位的作用, 以后不管链表节点如何改变, 此头点固定不变.



不带头链表

头节点不固定, 根据实际需要变换头节点 (如果在原来头节点前插入新节点, 然后新节点作为链表的头节点).



链表的基本操作


~ cat headers/linkList.h
#pragma once

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct LinkNode
{
    int num;
    struct LinkNode *next;
};

// 初始化链表
struct LinkNode *initLinkList();

// 遍历链表
void foreachLinkList(struct LinkNode *pHeader);

// 插入链表
void insertLinkList(struct LinkNode *pHeader, int oldVal, int newVal);


// 删除链表中某个节点
void deleteLinkList(struct LinkNode *pHeader, int val);
~ cat sources/linkList.c
#include <linkList.h>

// 初始化链表
struct LinkNode *initLinkList()
{
    // 创建头节点
    struct LinkNode *pHeader = malloc(sizeof(struct LinkNode));

    if (pHeader == NULL)
    {
        return NULL;
    }

    // 初始化头节点
    pHeader -> num = -1;
    pHeader -> next = NULL;

    // 记录尾节点位置, 方便插入新的数据
    struct LinkNode *pTail = pHeader;

    int val = -1;
    while (1)
    {
        // 让用户初始化几个节点, 如果用户输入的是 -1, 代表结束
        printf("请初始化链表, 如果输入 -1 代表结束\n");
        scanf("%d", &val);

        if (val == -1)
        {
            break;
        }

        // 如果输入不是 -1, 插入节点到链表中
        struct LinkNode *newNode = malloc(sizeof(struct LinkNode));
        newNode -> num = val;
        newNode -> next = NULL;

        // 更改指针的指向
        pTail -> next = newNode;

        // 更新新的尾节点的指向
        pTail = newNode;
    }

    return pHeader;
}

// 遍历链表
void foreachLinkList(struct LinkNode *pHeader)
{
    if (pHeader == NULL)
    {
        return;
    }

    struct LinkNode *curNode = pHeader -> next; // 指定第一个有真实数据的节点
    while (curNode != NULL)
    {
        printf("%d\n", curNode -> num);

        curNode = curNode -> next;
    }
}


// 插入链表
void insertLinkList(struct LinkNode *pHeader, int oldVal, int newVal)
{
    if (pHeader == NULL)
    {
        return;
    }

    // 创建两个临时节点
    struct LinkNode *pPrev = pHeader;
    struct LinkNode *pCurrent = pHeader -> next;

    while (pCurrent != NULL)
    {
        if (pCurrent -> num == oldVal)
        {
            break;
        }

        // 如果没有找到对应的位置, 辅助指针向后移动
        pPrev = pCurrent;
        pCurrent = pCurrent -> next;
    }

    // 创建新节点
    struct LinkNode *newNode = malloc(sizeof(struct LinkNode));
    newNode -> num = newVal;
    newNode -> next = NULL;

    // 建立关系
    pPrev -> next = newNode;
    newNode -> next = pCurrent;
}

// 删除链表中某个节点
void deleteLinkList(struct LinkNode *pHeader, int val)
{
    if (pHeader == NULL)
    {
        return;
    }

    // 创建两个临时节点
    struct LinkNode *pPrev = pHeader;
    struct LinkNode *pCurrent = pHeader -> next;

    while (pCurrent != NULL)
    {
        if (pCurrent -> num == val)
        {
            break;
        }

        // 如果没有找到对应的位置, 辅助指针向后移动
        pPrev = pCurrent;
        pCurrent = pCurrent -> next;
    }

    if (pCurrent == NULL) // 没有找到用户要删除的数据
    {
        return;
    }

    // 更改指针指向进行删除
    pPrev -> next = pCurrent -> next;

    free(pCurrent);
    pCurrent = NULL;
}
~ cat sources/test.c
#include <linkList.h>

void test()
{
    // 初始化链表
    struct LinkNode *pHeader = initLinkList();

    // 打印链表
    printf("遍历链表结果为:\n");
    foreachLinkList(pHeader);

    // 插入链表
    // 10 20 30 --> 10 1000 2000 20 30 500
    insertLinkList(pHeader, 20, 1000);
    insertLinkList(pHeader, 20, 2000);
    insertLinkList(pHeader, -1, 500);

    // 打印链表
    printf("遍历链表结果为:\n");
    foreachLinkList(pHeader);

    // 删除链表
    deleteLinkList(pHeader, 2000);
    deleteLinkList(pHeader, 3000);
    deleteLinkList(pHeader, 1000);
    deleteLinkList(pHeader, -1);

    // 打印链表
    printf("遍历链表结果为:\n");
    foreachLinkList(pHeader);
}

int main()
{
    test();

    return 0;
}


~ cd sources
~ gcc test.c linkList.c -I../headers -o test && ./test
请初始化链表, 如果输入 -1 代表结束
10
请初始化链表, 如果输入 -1 代表结束
20
请初始化链表, 如果输入 -1 代表结束
30
请初始化链表, 如果输入 -1 代表结束
-1
遍历链表结果为:
10
20
30
遍历链表结果为:
10
1000
2000
20
30
500
遍历链表结果为:
10
20
30
500



带头链表


初始化链表


// 初始化链表
struct LinkNode *initLinkList()
{
    // 创建头节点
    struct LinkNode *pHeader = malloc(sizeof(struct LinkNode));

    if (pHeader == NULL)
    {
        return NULL;
    }

    // 初始化头节点
    pHeader -> num = -1;
    pHeader -> next = NULL;

    // 记录尾节点位置, 方便插入新的数据
    struct LinkNode *pTail = pHeader;

    int val = -1;
    while (1)
    {
        // 让用户初始化几个节点, 如果用户输入的是 -1, 代表结束
        printf("请初始化链表, 如果输入 -1 代表结束\n");
        scanf("%d", &val);

        if (val == -1)
        {
            break;
        }

        // 如果输入不是 -1, 插入节点到链表中
        struct LinkNode *newNode = malloc(sizeof(struct LinkNode));
        newNode -> num = val;
        newNode -> next = NULL;

        // 更改指针的指向
        pTail -> next = newNode;

        // 更新新的尾节点的指向
        pTail = newNode;
    }

    return pHeader;
}



遍历链表


// 遍历链表
void foreachLinkList(struct LinkNode *pHeader)
{
    if (pHeader == NULL)
    {
        return;
    }

    struct LinkNode *curNode = pHeader -> next; // 指定第一个有真实数据的节点
    while (curNode != NULL)
    {
        printf("%d\n", curNode -> num);

        curNode = curNode -> next;
    }
}


插入链表


// 插入链表
void insertLinkList(struct LinkNode *pHeader, int oldVal, int newVal)
{
    if (pHeader == NULL)
    {
        return;
    }

    // 创建两个临时节点
    struct LinkNode *pPrev = pHeader;
    struct LinkNode *pCurrent = pHeader -> next;

    while (pCurrent != NULL)
    {
        if (pCurrent -> num == oldVal)
        {
            break;
        }

        // 如果没有找到对应的位置, 辅助指针向后移动
        pPrev = pCurrent;
        pCurrent = pCurrent -> next;
    }

    // 创建新节点
    struct LinkNode *newNode = malloc(sizeof(struct LinkNode));
    newNode -> num = newVal;
    newNode -> next = NULL;

    // 建立关系
    pPrev -> next = newNode;
    newNode -> next = pCurrent;
}


删除链表中某个节点


// 删除链表中某个节点
void insertLinkList(struct LinkNode *pHeader, int val)
{
    if (pHeader == NULL)
    {
        return;
    }

    // 创建两个临时节点
    struct LinkNode *pPrev = pHeader;
    struct LinkNode *pCurrent = pHeader -> next;

    while (pCurrent != NULL)
    {
        if (pCurrent -> num == val)
        {
            break;
        }

        // 如果没有找到对应的位置, 辅助指针向后移动
        pPrev = pCurrent;
        pCurrent = pCurrent -> next;
    }

    if (pCurrent == NULL) // 没有找到用户要删除的数据
    {
        return;
    }

    // 更改指针指向进行删除
    pPrev -> next = pCurrent -> next;

    free(pCurrent);
    pCurrent = NULL;
}



清空链表中所有节点


// 清空链表
void clearLinkList(struct LinkNode *pHeader)
{
    if (pHeader == NULL)
    {
        return;
    }

    struct LinkNode *pCurrent = pHeader -> next;

    while (pCurrent != NULL)
    {
        // 先保存下一个节点的位置
        struct LinkNode *nextNode = pCurrent -> next;

        free(pCurrent);
        pCurrent = nextNode;
    }

    pHeader -> next = NULL;
}




销毁链表


// 销毁链表
void destroyLinkList(struct LinkNode *pHeader)
{
    if (pHeader == NULL)
    {
        return;
    }

    struct LinkNode *pCurrent = pHeader -> next;

    while (pCurrent != NULL)
    {
        // 先保存下一个节点的位置
        struct LinkNode *nextNode = pCurrent -> next;

        free(pCurrent);
        pCurrent = nextNode;
    }

    pHeader -> next = NULL;

    free(pHeader);
    pHeader = NULL;
}