数据结构基础（C语言实现）—— 单向链表

最近在看 C 语言，不得不感慨现在的编程语言真的简化了很多操作，更加方便使用，被简化了的东西都被 C 和 C++ 干完了，从客观角度来看，C/C++ 仍然是目前最牛逼的编程语言。

数据结构基础的博客我只是贴个代码，并不写任何相关的知识点。知乎，CSDN，简书，B站，YouTube，Stack Overflow 这些网站上多的是比我这个半瓶水的要说得明白得多的博客和帖子，我只是基于我自己的理解写出来的代码，如果有疑问或者代码错误可以在评论提出，谢谢。

链表节点和链表结构体

//
// Created by Tianyi on 2021/10/28.
//

#ifndef DATA_STRUCT_LINKLIST_STRUCT_H
#define DATA_STRUCT_LINKLIST_STRUCT_H

#endif //DATA_STRUCT_LINKLIST_STRUCT_H

/**
 * 链表节点结构体
 */
struct LinkNode {
    int value;
    struct LinkNode *next;
};


/**
 * 链表结构体
 */
struct LinkList {
    // 用于记录当前链表中有多少个节点（节点下标从 1 开始）
    int count;
    // 分别定义头指针和尾指针，方便进行操作
    struct LinkNode *head;
    struct LinkNode *tail;
};

链表相关操作

//
// Created by Tianyi on 2021/10/28.
//

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

#ifndef DATA_STRUCT_LINKLIST_UTILS_H
#define DATA_STRUCT_LINKLIST_UTILS_H


typedef struct LinkNode LinkNode;
typedef struct LinkList LinkList;

#endif //DATA_STRUCT_LINKLIST_UTILS_H

void addLastNode(struct LinkList *linkList, int value);

void addFirstNode(struct LinkList *linkList, int value);

void removeFirstNode(struct LinkList *linkList);

void removeLastNode(struct LinkList *linkList);

/**
 * 用于创建一个新的节点，并返回该结点的内存指针
 */
struct LinkNode *newNode(int value) {
    // 申请内存，类似于 Java 的 new 操作
    struct LinkNode *node = (LinkNode *) malloc(sizeof(LinkNode));
    if (node == NULL) {
        printf("create node failure!!!\n");
        return NULL;
    }
    // 清空申请的内存
    memset(node, 0, sizeof(LinkNode));
    // 添加对应的值
    node->value = value;
    node->next = NULL;
    // 返回指针
    return node;
}

/**
 * 用于创建一个链表结构体实例，类似于 Java 中的 new，将返回一个链表结构体的指针
 */
struct LinkList *newList() {

    struct LinkList *linkList = (LinkList *) malloc(sizeof(LinkList));
    if (linkList == NULL) {
        printf("create linkList failure!!!\n");
        return NULL;
    }

    // 清空申请的内存
    memset(linkList, 0, sizeof(LinkNode));

    linkList->count = 0;
    linkList->head = NULL;
    linkList->tail = NULL;

    return linkList;
}

/**
 * 通过下标查找节点
 * 下标从 1 开始，用于区别数组，数组下标从 0 开始，链表没有这种规则
 */
LinkNode *findByIndex(const struct LinkList *linkList, int index) {
    if (index == 0) {
        printf("this index is undefined!!!");
        return NULL;
    }

    if (index < 0 || index > linkList->count) {
        printf("the index is out of range!!!");
        return NULL;
    }

    // 创建一个临时节点指向链表，用于保证下标 1 指向的就是链表的第一个节点
    // 后续会释放掉这个节点的内存
    LinkNode *node = newNode(0);
    node->next = linkList->head;
    LinkNode *tempNode = node;

    // 遍历链表找到对应位置的节点
    for (int i = 0; i < index && tempNode != linkList->tail; i++) {
        tempNode = tempNode->next;
    }

    // 释放掉临时节点的内存
    free(node);
    return tempNode;
}

/**
 * 通过值查找节点
 * 如果节点存在则放回下标，不存在就返回 -1
 */
int findByValue(struct LinkList * linkList, int findValue) {
    int index = 1;

    struct LinkNode *p = linkList->head;

    while (p != linkList->tail && p->value != findValue) {
        p = p->next;
        index++;
    }

    if (p != linkList->tail) {
        return index;
    }

    if (p == linkList->tail && linkList->tail->value == findValue) {
        return index;
    } else {
        printf("There is no value equal %d, you can insert a new value to this linklist or find another value.", findValue);
        return -1;
    }
}

/**
 * 向链表添加元素，默认使用尾插法
 */
void add(struct LinkList *linkList, int value) {
    addLastNode(linkList, value);
}

/**
 * 头插法添加元素
 */ 
void addFirstNode(struct LinkList *linkList, int value) {
    LinkNode *node = newNode(value);
    node->next = linkList->head;
    linkList->head = node;

    // 针对空链表单独进行处理
    if (linkList->count == 0) {
        linkList->tail = node;
    }

    linkList->count++;
}

/**
 * 尾插法添加元素
 */ 
void addLastNode(struct LinkList *linkList, int value) {
    LinkNode *node = newNode(value);

    // 针对空链表进行处理
    if (linkList->count == 0) {
        linkList->head = node;
        linkList->tail = node;
    } else {
        // 非空链表处理
        linkList->tail->next = node;
        linkList->tail = node;
    }

    linkList->count++;
}

/**
 * 根据下标位置插入节点
 */
void addInIndex(struct LinkList *linkList, int index, int value) {
    if (index > linkList->count) {
        printf("this index is out of range!!!\n");
        return;
    }

    // 如果是插入到第一个位置直接使用头插法提升效率
    if (index == 1) {
        addFirstNode(linkList, value);
        return;
    }

    // 拿到目标位置的前一个位置节点
    LinkNode *findNode = findByIndex(linkList, index - 1);
    // 创建一个新节点
    LinkNode *node = newNode(value);
    // 根据链表性质添加节点
    node->next = findNode->next;
    findNode->next = node;
    linkList->count++;
}

/**
 * 根据下标删除节点
 */
void removeIndex(struct LinkList *linkList, int index) {
    if (linkList->count == 0) {
        printf("linklist is empty, can't remove any node.\n");
        return;
    }

    if (index > linkList->count) {
        printf("this index is out of range!!!\n");
        return;
    }

    // 如果当前链表只剩下一个节点，或者只删除第一个节点，那直接调用删除头结点的函数
    if (linkList->count == 1 || index == 1) {
        removeFirstNode(linkList);
        return;
    }

    // 如果当前链表只剩下两个节点，且不删除第一个节点，直接调用删除尾结点的函数
    if (linkList->head->next == linkList->tail) {
        removeLastNode(linkList);
        return;
    }

    // 找到要删除的节点的前一个结点，根据链表性质删除节点
    LinkNode *findNode = findByIndex(linkList, index - 1);
    LinkNode *removeNode = findNode->next;    

    findNode->next = removeNode->next;
    free(removeNode);
    linkList->count--;
}

/**
 * 删除头结点
 */
void removeFirstNode(struct LinkList *linkList) {
    if (linkList->count == 0) {
        printf("linklist is empty, can't remove any node.\n");
        return;
    }
    LinkNode *node = linkList->head;
    linkList->head = node->next;
    free(node);
    linkList->count--;
}

/**
 * 删除尾结点
 */
void removeLastNode(struct LinkList *linkList) {
    if (linkList->count == 0) {
        printf("linklist is empty, can't remove any node.\n");
        return;
    }

    // 当链表只剩下一个节点的时候，直接使用删除头结点的函数，若使用下面的步骤会出现指针异常
    if (linkList->count == 1) {
        removeFirstNode(linkList);
        return;
    }

    LinkNode *findNode = findByIndex(linkList, linkList->count - 1);
    free(linkList->tail);
    linkList->tail = findNode;
    linkList->count--;
}

/**
 * 修改节点值
 */
void changeNodeValue(struct LinkList * linkList, int index, int newValue) {
    LinkNode * findNode = findByIndex(linkList, index);
    findNode->value = newValue;
}

/**
 * 打印链表
 */
void show(const struct LinkList *linkList) {
    int index = 1;

    printf("the count of linklist is %d\n", linkList->count);

    if (linkList->count == 0) {
        printf("the linklist is empty.\n");
        return;
    }

    struct LinkNode *p = linkList->head;

    while (p != linkList->tail) {
        printf("index %d -- value %d\n", index, p->value);
        p = p->next;
        index++;
    }
    printf("index %d -- value %d\n", index, p->value);
}

测试代码

#include <stdio.h>
#include "lib/struct.h"
#include "lib/utils.h"

int main() {

//    LinkNode *node1 = newNode(1);
//    LinkNode *node2 = newNode(2);
//    LinkNode *node3 = newNode(3);
//    LinkNode *node4 = newNode(4);
//
//    node1->next = node2;
//    node2->next = node3;
//    node3->next = node4;
//
//    LinkList *linkList = newList();
//    linkList->head = node1;
//    linkList->tail = node4;
//    linkList->count = 4;
//
//    addFirstNode(linkList, 0);
//    addLastNode(linkList, 5);
//    show(linkList);

//    LinkNode * findNode = findByIndex(linkList, 1);
//    if (findNode != NULL) {
//        printf("the node was found value is %d", findNode->value);
//    }

    LinkList *newLinkList = newList();
    addLastNode(newLinkList, 6);
    add(newLinkList, 0);
    add(newLinkList, 1);
    addInIndex(newLinkList, 1, -1);
    addInIndex(newLinkList, 2, 2);
    show(newLinkList);
    printf("=====================\n");
    changeNodeValue(newLinkList, 2, 999);
    show(newLinkList);
    printf("=====================\n");
    int index = findByValue(newLinkList, 999);
    if (index != -1) {
        printf("the index of value was found is %d\n", findByValue(newLinkList, 999));
    }
    printf("=====================\n");
    index = findByValue(newLinkList, 666);
    if (index != -1) {
        printf("the index of value was found is %d\n", findByValue(newLinkList, 999));
    }


//    removeIndex(newLinkList, 2);
//    show(newLinkList);
//    printf("=====================\n");
//    removeIndex(newLinkList, 2);
//    show(newLinkList);
//    printf("=====================\n");
//    removeIndex(newLinkList, 2);
//    show(newLinkList);
//    printf("=====================\n");
//    removeIndex(newLinkList, 2);
//    show(newLinkList);
//    printf("=====================\n");
//    removeIndex(newLinkList, 2);
//    show(newLinkList);
//    printf("=====================\n");
//    removeIndex(newLinkList, 1);
//    show(newLinkList);

    return 0;
}