簡單好用的LIST之C語言實作

LIST用時方很少

撰寫程式時，多少都會用到一些串列、佇列等資料結構，有的程式語言會提供相關的實作，很容易就可以取用，相較之下，C language的使用者在這方面就比較麻煩。老練的C language程式設計師討生活的工具箱裡，都會有這方面的程式碼，以備不時之需。在open source的領域裡，也有不少高手提供這方面的函式庫。如果有需要搭配搜尋、排序的演算法，SimCList會是一個不錯的選擇，它的優點是使用方便，容易上手，速度也不錯，且授權方式採用極為友善的BSD license；倘若僅需要用到單純的list、stack、FIFO時，FreeBSD核心中的相關程式碼片段就可立即派上用場。其實Linux核心中也有功能相似的實作，較之前者可說各有勝場，只是Linux核心採用GPL授權，使用上需要多加斟酌。FreeBSD的List與Queue實作，位於sys/queue.h。

FreeBSD的queue.h提供了多個LIST的實作，可供不同場合應用。這些資料結構的使用方式差不多，個人倒是比較常用到其中的SLIST、LIST及TAILQ。其中， SLIST是單向連結的串列(Singly-linked List)；LIST是雙向連結的串列；TAILQ是可直接存取末端元素的串列，可說是LIST的加強版。三者的使用時機與差異就不在此詳述了，請參考任何一本講述資料結構及演算法的教科書，都會有詳盡的說明，個人推薦「The Art of Computer Programming」。

與既有C結構(C struct)的整合

要讓資料結構可以變成串列的元素(an element of list)，首先要在原本宣告的結構中透過queue.h的提供的巨集(marco)：LIST_ENTRY(type)增添新的欄位。

struct element
{
    int value;
    LIST_ENTRY(element) node;
};

宣告LIST型別

接著，宣告串列的結構型別。宣告方式為：LIST_HEAD(name, type)，name為LIST的型別名稱，type為節點的型別。

LIST_HEAD(sample_list, element);

宣告LIST變數

變數宣告方式如C language變數宣告方式。

... ... ...

struct sample_list list1;

... ... ...

初始化串列
LIST初始化方式分為靜態初始化與動態初始化兩種。且看下面的範例。

... ... ...

static struct sample_list list1 = LIST_HEAD_INITIALIZER(list1);

... ... ...

int main(int argc, char** argv)
{
    ... ... ...

    struct sample_list list2;

    LIST_INIT(&list2);

    ... ... ...
}

將元素添加至串列前端

... ... ...
LIST_INSERT_HEAD(&list1, e1, entry);
... ... ...

取得串列的第一個元素

 ... ... ...
e = LIST_FIRST(&list1);
 ... ... ...

將元素插入至某個元素之前

要將e2插入至e1之前，可透過LIST_INSERT_BEFORE。

 ... ... ...
LIST_INSERT_BEFORE(e1, e2, node);
 ... ... ...

將元素插入至某個元素之後

要將e2插入至e1之後，可透過LIST_INSERT_AFTER。

 ... ... ...
LIST_INSERT_AFTER(e1, e2, node);
 ... ... ...

串列是否包含任何元素

 ... ... ...
while (!LIST_EMPTY(list)) {
    ... ... ...
}
 ... ... ...

透過迴圈尋訪串列

 ... ... ...
LIST_FOREACH(e, list, entry) {
    printf("%d ", e->value);
}
 ... ... ...

移除元素
使用LIST_REMOVE，可將特定元素從LIST中移除。

 ... ... ...
LIST_REMOVE(e1, node);
 ... ... ...

取得串列中特定元素的下一個元素
LIST_NEXT可回傳串列中特定元素之下一個元素，若該元素位於串列尾端，則回傳NULL。

 ... ... ...
LIST_FOREACH(e1, list, node) {
    if (LIST_NEXT(e1, node) != NULL) {
        printf("[ %2d ] -> ", e1->value);
    } else {
        printf("[ %2d ]", e1->value);
    }
}
 ... ... ...

完整範例

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

#include "queue.h"

struct element
{
    int value;

    LIST_ENTRY(element) node;
};

LIST_HEAD(sample_list, element);


static struct sample_list list1 = LIST_HEAD_INITIALIZER(list1);


int main(int argc, char** argv)
{
    int i = 0;
    struct element* e1 = NULL;
    struct element* e2 = NULL;
    struct sample_list* list = NULL;

    list = &list1;

    for (i = 0; i < 4; i++) {
        e1 = calloc(1, sizeof(*e1));
        e1->value = i;
        LIST_INSERT_HEAD(list, e1, node);
    }

    e1 = LIST_FIRST(list);
    printf("The first element is %d.\n", e1->value);

    printf("list1: ");
    LIST_FOREACH(e1, list, node) {
        if (LIST_NEXT(e1, node) != NULL) {
            printf("[ %2d ] -> ", e1->value);
        } else {
            printf("[ %2d ]", e1->value);
        }
    }
    printf("\n");

    // Remove all elements from list1
    while (!LIST_EMPTY(list)) {
        e1 = LIST_FIRST(list);
        LIST_REMOVE(e1, node);
        free(e1);
    }

    list = malloc(sizeof(*list));

    // Initialize the head of list2
    LIST_INIT(list);

    e1 = calloc(1, sizeof(*e1));
    e1->value = -2;
    LIST_INSERT_HEAD(list, e1, node);

    e2 = calloc(1, sizeof(*e2));
    e2->value = -1;
    LIST_INSERT_BEFORE(e1, e2, node);

    e2 = calloc(1, sizeof(*e2));
    e2->value = -3;
    LIST_INSERT_AFTER(e1, e2, node);

    printf("list2: ");
    LIST_FOREACH(e1, list, node) {
        if (LIST_NEXT(e1, node) != NULL) {
            printf("[ %2d ] -> ", e1->value);
        } else {
            printf("[ %2d ]", e1->value);
        }
    }
    printf("\n");

    // Remove all elements from list2
    e1 = LIST_FIRST(list);
    while (e1 != NULL) {
        e2 = LIST_NEXT(e1, node);
     free(e1);
     e1 = e2;
    }
    free(list);

    return 0;
}