C语言实现双向链表 – LovelyCat的小站

本文最后更新于 739 天前，其中的信息可能已经有所发展或是发生改变。

之前一直写的都是Java/C#，初学几天C语言，先来实现一个简单的链表试试。

1.定义结构体

typedef struct LinkedListNodeStruct {
    struct LinkedListNodeStruct *next, *pre;
    int value;
} LinkedListNode;

typedef struct LinkedListStruct {
    LinkedListNode *header, *tail;
    int size;
} LinkedList;

2.定义头文件

LinkedList * LinkedList_Create();

void LinkedList_Recycle(LinkedList *linkedList);

int LinkedList_Length(LinkedList *linkedList);

LinkedListNode * LinkedList_BuildNode(int value);

void LinedList_Add(LinkedList *linkedList, LinkedListNode *node);

void LinkedList_Insert(LinkedList *linkedList, LinkedListNode *node, int index);

LinkedListNode * LinedList_Get(LinkedList *linkedList, int index);

LinkedListNode * LinkedList_GetFromHead(LinkedList *linkedList, int targetIndex);

LinkedListNode * LinkedList_GetFromTail(LinkedList *linkedList, int targetIndex);

void LinkedList_Remove(LinkedList *linkedList, int index);

3.函数实现

引入库文件

#include "linkedlist.h"
#include "stdio.h"
#include "memory.h"
#include "stdlib.h"

先来定义两个用于检查链表空和索引越界的函数。

static bool autoCheckAvailable(LinkedList *linkedList, bool isAutoExit);
static bool autoCheckIndex(LinkedList *linkedList, int index, bool isAutoExit);

static bool autoCheckAvailable(LinkedList *linkedList, bool isAutoExit) {
    if (linkedList == nullptr) {
        // Define by urslef or delete
        throwNullPointerException();
        if (isAutoExit) exit(-1);
        return false;
    }
    return true;
}

static bool autoCheckIndex(LinkedList *linkedList, int index, bool isAutoExit) {
    if (index >= linkedList->size || index < 0) {
        // Define by urslef or delete
        throwIndexOutOfBoundsException();
        if (isAutoExit) exit(-1);
        return false;
    }
    return true;
}

3.1创建链表

LinkedList * LinkedList_Create() {
    LinkedList *list = malloc(sizeof (LinkedList));
    memset(list, 0, sizeof (LinkedList));
    list->size = 0;
    list->header = nullptr;
    list->tail = nullptr;
    return list;
}

3.2回收链表

void LinkedList_Recycle(LinkedList *linkedList) {
    if (linkedList != nullptr) {
        free(linkedList);
        linkedList = nullptr;
    }
}

3.3 构建链表节点

LinkedListNode * LinkedList_BuildNode(int value) {
    LinkedListNode *node = malloc(sizeof (LinkedListNode));
    node->value = value;
    return node;
}

3.4 向尾部添加节点

void LinedList_Add(LinkedList *linkedList, LinkedListNode *newNode) {
    bool checkResult = autoCheckAvailable(linkedList, false);
    if (!checkResult) {
        return;
    }

    if (linkedList->size == 0) {
        linkedList->header = newNode;
        linkedList->tail = newNode;
    } else {
        newNode->next = nullptr;
        newNode->pre = linkedList->tail;
        // Link new node to the old tail node
        linkedList->tail->next = newNode;
        // Reset old tail node to new
        linkedList->tail = newNode;
    }

    linkedList->size++;
}

3.5 插入节点

void LinkedList_Insert(LinkedList *linkedList, LinkedListNode *node, int index) {
    bool checkResult = autoCheckAvailable(linkedList, false);
    if (!checkResult) {
        return;
    }

    LinkedListNode *target = LinedList_Get(linkedList, index);
    LinkedListNode *preNode = target->pre;

    node->next = target;
    target->pre = node;
    if (index == 0) {
        linkedList->header = node;
    } else {
        preNode->next = node;
        node->pre = preNode;
    }

    linkedList->size++;
}

3.6 获取节点

由于双向链表既可以从头部开始遍历也可以从尾部开始遍历，所以双向链表具有插入慢、读取快的特性，但假设链表长度为10，需要获取下标为8的节点，显然从尾部开始向前遍历速度最快，所以可以根据下标来决定从哪个方向开始遍历。

以下是具体实现

LinkedListNode * LinkedList_GetFromHead(LinkedList *linkedList, int targetIndex) {
    LinkedListNode *cursor = linkedList->header;
    for (int i = 0; i < targetIndex; i++) {
        cursor = cursor->next;
    }
    return cursor;
}

LinkedListNode * LinkedList_GetFromTail(LinkedList *linkedList, int targetIndex) {
    LinkedListNode *cursor = linkedList->tail;
    for (int i = linkedList->size; i > targetIndex + 1; i--) {
        cursor = cursor->pre;
    }
    return cursor;
}

所以整合一下就是这样

LinkedListNode * LinedList_Get(LinkedList *linkedList, int index) {
    bool checkResult = autoCheckAvailable(linkedList, false) && autoCheckIndex(linkedList, index, false);
    if (!checkResult) {
        return nullptr;
    }
    return index + 1 <= linkedList->size / 2 ? LinkedList_GetFromHead(linkedList, index) : LinkedList_GetFromTail(linkedList, index);
}

3.7 移除节点

void LinkedList_Remove(LinkedList *linkedList, int index) {
    bool checkResult = autoCheckAvailable(linkedList, false) && autoCheckIndex(linkedList, index, false);
    if (!checkResult) {
        return;
    }

    LinkedListNode *target = LinedList_Get(linkedList, index);
    LinkedListNode *preNode = target->pre;
    LinkedListNode *nextNode = target->next;

    if (index == 0) {
        linkedList->header = nextNode;
    } else if (index + 1 == linkedList->size) {
        linkedList->tail = preNode;
    } else {
        preNode->next = nextNode;
        nextNode->pre = preNode;
    }

    free(target);
    target = nullptr;

    linkedList->size--;
}

4.测试与总结

写一个测试函数来试试

void LinkedList_UnitTest() {
    printf(">>> Now start unit test of LinkedList\n");

    LinkedList *testList = LinkedList_Create();
    LinedList_Add(testList, LinkedList_BuildNode(114));
    LinedList_Add(testList, LinkedList_BuildNode(514));
    LinedList_Add(testList, LinkedList_BuildNode(191));
    LinedList_Add(testList, LinkedList_BuildNode(981));
    LinedList_Add(testList, LinkedList_BuildNode(189));

    printf(">>> List content\n");
    LinkedListNode *cursor = testList->header;
    for (int i = 0; i < testList->size; i++) {
        printf("%d\n", cursor->value);
        cursor = cursor->next;
    }

    printf(">>> || Fx: Get\n");
    printf("%d\n", LinedList_Get(testList, 0)->value);
    printf("%d\n", LinedList_Get(testList, 1)->value);
    printf("%d\n", LinedList_Get(testList, 2)->value);
    printf("%d\n", LinedList_Get(testList, 3)->value);
    printf("%d\n", LinedList_Get(testList, 4)->value);

    printf(">>> || Fx: Remove Head\n");
    LinkedList_Remove(testList, 0);
    printf("%d\n", LinedList_Get(testList, 0)->value);

    printf(">>> || Fx: Remove Tail\n");
    LinkedList_Remove(testList, 3);
    printf("%d\n", LinedList_Get(testList, 2)->value);

    printf(">>> || Fx: Insert\n");
    LinkedList_Insert(testList, LinkedList_BuildNode(2333), 1);
    printf("%d\n", LinedList_Get(testList, 1)->value);

    LinkedList_Recycle(testList);
    printf(">>> Unit test of LinkedList now ended\n");
}

运行结果为

>>> Now start unit test of LinkedList
>>> List content
114
514
191
981
189
>>> || Fx: Get
114
514
191
981
189
>>> || Fx: Remove Head
514
>>> || Fx: Remove Tail
981
>>> || Fx: Insert
2333
>>> Unit test of LinkedList now ended

最后欢迎各位大佬指正