【演算】連結串列 - Linked List

　　當你需要儲存一串同型資料時，使用陣列或許是一個最簡單的方法。但是由於陣列在宣告時，就需要明確的指定大小。在資料不多(比陣列大小小)時，就容易造成記憶體的浪費。反之資料多(比陣列大小大)時，也會出現記憶體空間上使用限制。

　　而連結串列(linked list)，可以說就是為了解決這些缺陷而出現的。串列的最大特色，就是其大小可因應需求動態配置記憶體，避免記憶體的浪費。不過相對的，串列的實現與操作也較陣列麻煩許多。

　　串列中的每一個元素稱之為節點(node)，每一個節點都包含了儲存資料的變數，以及連結其他節點的連結指標(linked list 之名便是有此而來)。


　　根據不同情況，比較常見的串列有單向連結串列(singly-linked lists)、雙向連結串列(doubly-linked lists)與環狀連結串列(circularly-linked lists)。

　　單向連結串列是一個最基本的串列，每一個節點都包含一個指向下一個節點的指標。



　　一個節點的宣告方式大致如下：

struct Node
{
    Type data;
    Node *next;
}

　　而串列的操作，大致有插入(insert)跟移除(remove)這兩種方式。

　　插入操作的進行，其實只是指標指向的轉移。假設現在欲在 A 與 C 節點中插入一個 B 節點，則先將 B 節點的連結指標指向 C，再將 A 節點的連結指標指向 B。



　　相同的，移除操作也是藉由指標指向的轉移達成。假設現在我們要將 A 與 C 節點中的 B 節點移除，則將 A 節點的連結指標指向 C 即可。



　　以上兩種操作的虛擬碼大致如下：

void insert(Node* n1, Node* n2)
{
    // 將 n2 插入在 n1 之後
    n2->next = n1->next;
    n1->next = n2;
}

void remove(Node* n1)
{
    // 刪除 n1 的下一個節點
    n1->next = n1->next->next;
}

　　以下是使用 C 語言的實作單向連結串列的使用實例：

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

// 宣告節點結構
typedef struct ns
{
    int data;
    struct ns* next;
} node;

// 宣告相關函式
node* create_node(int);
void insert_node(node*, node*);
void remove_node(node*);
void print_lists(node*);
void free_lists(node*);

int main(void)
{
    // 宣告節點
    node* lists = create_node(0);
    node* a = create_node(1);
    node* b = create_node(2);
    node* c = create_node(3);
    node* d = create_node(4);
    node* e = create_node(5);

    // 0 -> 5
    insert_node(lists, e);

    // 0 -> 1 -> 5
    insert_node(lists, a);

    // 1 -> 2 -> 5
    insert_node(a, b);

    // 1 -> 3 -> 2
    insert_node(a, c);

    // 5 -> 4
    insert_node(e, d);

    print_lists(lists);
    free_lists(lists);

    system("pause");
}

node* create_node(int data)
{
    // 動態配置記憶體
    node* n = (node*)malloc(sizeof(node));

    n->data = data;
    n->next = NULL;

    return n;
}

void insert_node(node* n1, node* n2)
{
    n2->next = n1->next;
    n1->next = n2;
}

void remove_node(node* n1)
{
    n1->next = n1->next->next;
}

void print_lists(node* lists)
{
    node* n = lists;

    // 依序印出節點內容
    while (n != NULL)
    {
        printf("%d ", n->data);

        n = n->next;
    }

    printf("\n");
}

void free_lists(node* lists)
{
    // 遞迴刪除串列所有節點
    if (lists->next != NULL)
    {
        free_lists(lists->next);
    }

    free(lists);
}

　　至於雙向連結串列，則是結點比單向連結串列多了一個連結指標，指向的是這個節點的前一個節點。



　　而環狀連結串列跟單向連結串列僅有唯一不同點，就是環狀連結串列的最後一個節點指標指向的是第一個節點。



　　至於這兩種連結串列的操作，基本上與單向連結串列大同小異，這裡我們不再多花篇幅解釋(格主想睡了)。


　　儘管連結串列在資料的新增與移除上，較陣列來的彈性許多，它也是具有許多缺點的。

　　除了一開始我所提到的操作麻煩之外，由於串列沒有索引值，因此要提取某節點存放的變數值會相當不方便。而且若是一個連結串列的節點相當多，每一個節點指標所佔用的記憶體也相當龐大。

　　因此，根據不同的情況，判斷何時用陣列、何時用串列，也是相當重要的。