C语言实现双向链表

C语言的标准库并没有实现链表，所以需要我们通过所学的知识来实现链表。
先来看看双向链表的定义，来源于百度百科。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

此处使用面向对象思想来编写来去实现双向链表。

定义Node

对于C的OOP编程，由于C语言中没有对象的概念，但有struct，我们可以使用struct来定义一个Node，并存放在头文件Node.h中，接下来是他们的实现。

typedef struct Node {
    void *item;        //使用void* 是实现存储任意类型的数据
    struct Node *prev; // 前一个节点的指针变量
    struct Node *next; // 后一个节点的指针变量
} Node;

// 相当于OOP的new函数，用于Node的内存申请
Node *Node_new(Node *prev, void *element, Node *next) {
    struct Node *new_node = (struct Node *) malloc(sizeof(struct Node));
    new_node->item = element;
    new_node->next = next;
    new_node->prev = prev;
    return new_node;
}

定义LinkedList

定义一个LinkedList，去实现对于双向链表的增删改查。

#include "Node.h"
#include <stdio.h>

typedef struct LinkedList {
    int size;
    struct Node *first;
    struct Node *last;
} LinkedList;

// 定义方法，相当于java的构造函数
LinkedList *LinkedList_new() {
    struct LinkedList *linkedList = (struct LinkedList *) malloc(sizeof(struct LinkedList));
    return linkedList;
}

void *LinkedList_getFirst(LinkedList *linkedList) {
    if (linkedList == NULL) {
        return NULL;
    }
    Node *f = linkedList->first;
    return f->item;
}

void *LinkedList_getLast(LinkedList *linkedList) {
    if (linkedList == NULL) {
        return NULL;
    }
    Node *f = linkedList->last;
    return f->item;
}

int LinkedList_size(LinkedList *linkedList) {
    if (linkedList == NULL) {
        return -1;
    }
    return linkedList->size;
}

void LinkedList_addFirst(struct LinkedList *linkedList, void *e) {
    if (linkedList == NULL) {
        return;
    }
    Node *f = linkedList->first;
    Node *newNode = Node_init(NULL, e, f);
    linkedList->first = newNode;
    if (f == NULL) {
        linkedList->last = newNode;
    } else {
        f->prev = newNode;
    }
    linkedList->size++;
}

void LinkedList_addLast(struct LinkedList *linkedList, void *e) {
    if (linkedList == NULL) {
        return;
    }
    Node *l = linkedList->last;
    Node *newNode = Node_init(l, e, NULL);
    linkedList->last = newNode;
    if (l == NULL) {
        linkedList->first = newNode;
    } else {
        l->next = newNode;
    }
    linkedList->size++;
}

void *LinkedList_removeFirst(struct LinkedList *linkedList) {
    if (linkedList == NULL) {
        return NULL;
    }
    Node *f = linkedList->first;
    if (f == NULL) {
        return NULL;
    }
    const void *element = f->item;
    Node *next = f->next;
    f->item = NULL;
    f->next = NULL;
    linkedList->first = next;
    if (next == NULL) {
        linkedList->last = NULL;
    } else {
        next->prev = NULL;
    }
    linkedList->size--;
    return element;
}

void *LinkedList_removeLast(struct LinkedList *linkedList) {
    if (linkedList == NULL) {
        return NULL;
    }
    Node *l = linkedList->last;
    if (l == NULL) {
        return NULL;
    }
    void *element = l->item;
    Node *prev = l->prev;
    l->item = NULL;
    l->prev = NULL;
    linkedList->last = prev;
    if (prev == NULL) {
        linkedList->first = NULL;
    } else {
        prev->next = NULL;
    }
    linkedList->size--;
    return element;
}

void LinkedList_printList(struct LinkedList *linkedList) {
    // 先找到最后一个ListNode，并标记为last
    struct Node *last;
    struct Node *node = linkedList->first;
    while (node != NULL) {
        last = node;
        node = node->next;
        printf(" %d ", last->item);
    }
}

使用Demo

LinkedList *node = LinkedList_new();
LinkedList_addFirst(node, 20);
LinkedList_addLast(node, 19);
LinkedList_addFirst(node, 40);
LinkedList_addLast(node, 21);
LinkedList_addFirst(node, 22);
LinkedList_printList(node);