数据结构-链表的应用和实现

作者：HerryLo (opens new window) 博客原文链接 (opens new window)

在软件开发中链表和数组非常常见，它们都是线性存储，区别只是存储方式的不同。数组是连续存储，链表是离散存储(非连续)。链表是根据节点的前后关系进行存储的，同时由于它是离散存储，对内存空间利用更好。

链表分为：单链表、双向链表、循环链表，下面我主要是以单链表为示例说明，单链表基本结构如下：

    头结点:A           首节点:B                                  尾节点:C
       👇               👇                                       👇
[data=NULL|next]——>[data|next]——>[data|next]——>[data|next]——>[data|next]——> NULL

由上结构可以知道，链表的每个节点都由两个属性构成，data负责存储数据，next负责指向下一个节点。当然，双向链表和循环链表都是以上面的结构进行扩展的。

单链表的头结点和尾结点比较特殊，头结点用来记录链表的头地址，是链表遍历的起点，尾结点的后继指针不指向任何结点，而是指向一个空地址NULL。这里首节点才时第一个有效节点。

时间复杂度: 单链表的插入、删除操作时间复杂度为O(1)，随机查找时间复杂度为O(n)。相对于数组，链表的插入和删除更加简便。

尽管在前端开发中，数组的使用可能大于链表，但由于链表的优点，就我所知道，目前React框架中就有应用，React项目中React Fiber由单链表构成，参考：react16.3的fiber架构 (opens new window)。

C语言单链表实现

创建结构体Node数据类型，链表中的每个节点都将是下面的数据结构：

// 默认data为整型
typeof struct Node{
    int data; // 数据域
    struct Node * next; // 指针域
}Node, *PNode;

在上面的讲解中未说到结构体，简单点结构体就是一种数据类型。(*表示指针，指针就是内存地址，struct Node * next就是创建一个Node类型的结构体指针变量next，指针变量即存储内存地址的变量)。

链表创建函数如下：

// 创建链表
PNode createList() {
    // 长度
    int len;
    // 存放用户输入的节点值
    int val;
    
    // 不存放有效数据的头结点，分配动态内存
    PNode pHead = (PNode)malloc(sizeof(Node));
    // 容错
    if(NULL == pHead) {
        printf("分配失败，程序终止！\n");
        exit(-1);
    }
    
    // 创建一个临时节点
    PNode pTail = pHead;
    pTail->next = NULL;
    
    printf("请输入链表的长度: len=");
    scanf("%d", &len);
    
    for (int i = 0; i<len; ++i) {
        printf("请输入第%d个节点的值: ", i+1);
        scanf("%d", &val);
        // 分配动态内存
        PNode pNew = (PNode)malloc(sizeof(Node));
        if(NULL == pNew) {
            printf("分配失败，程序终止！\n");
            exit(-1);
        }
        
        // 赋值/替换
        pNew->data = val;
        pTail->next = pNew;
        pNew->next = NULL;
        pTail = pNew;
    }
    return pHead;
}

// 遍历  
int traverseList(PNode pHead) {
    printf("打印链表的z值：\n");
    PNode next = pHead->next;
    while(next != NULL) {
        printf("%d \n", next->data);
        next = next->next;
    }
    printf("\n");
    return 0;
}

// 移除
// pHead 链表头节点
// i 移除的下标，由1开始
bool removeList(PNode pHead, int position, int *pVal) {
    PNode p = pHead;
    int i = 0;
    
    // p->next != NULL，移除的前提下，保证要移除的那个只存在；
    // 在存在的前提下，p会指向要移除的前一个节点；
    while (p->next != NULL && i< position - 1) {
        p = p->next;
        ++i;
    }
    
    // i > position - 1，防止负数
    if(i > position - 1 || p->next == NULL) {
        return false;
    }
    
    PNode q = p->next;
    *pVal = p->data;
    
    p->next = p->next->next;
    free(q);
    q = NULL;
    return true;
}

// 插入
// pHead 链表头节点
// i 插入的下标，由1开始
bool insertList(PNode pHead, int position, int val){
    PNode p = pHead;
    int i = 0;
    
    // p != NULL，插入的前提下，保证要插入位置的前y一个元素存在；
    // 在存在的前提下，p会指向要插入的前的节点；
    while (p->next != NULL && i< position - 1) {
        p = p->next;
        ++i;
    }
    // // i > position - 1，防止负数
    if(i > position - 1 || p == NULL) {
        return false;
    }
    
    PNode pNew = (PNode)malloc(sizeof(Node));
    if(NULL == pNew) {
        printf("分配失败，程序终止！\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->next = p->next;
    p->next = pNew;
    return true;
}

通过createList函数创建单链表，这个函数的核心：创建一个临时的指针变量pTail，进行节点的替换。traverseList函数打印链表的值，removeList函数负责移除节点，insertList函数负责插入节点。

main函数中创建链表：

int main() {
    // 头节点
    PNode pHead = NULL; // 等价于struct Node * pHead = NULL
    int value;
    
    pHead = createList();
    removeList(pHead, 8, &value);
    insertList(pHead, 2, 123123);
    traverseList(pHead);
}

代码示例：C语言创建单链表 (opens new window)

参考：

郝斌老师数据结构视频 (opens new window)

ps: 微信公众号：Yopai，有兴趣的可以关注，每周不定期更新。不断分享，不断进步