關於鏈表（List），是學C之人常問的問題，本帖試圖給初學者詳細解釋這方面的内容。

首先看看鏈表的模型，如下圖：


圖中，縱向表示內存空間，由於計算機的內存都是綫性的，所以縱坐標1、2、……12等就是內存地址。藍色的是一個鏈表數據的映像，Data是封裝的數據包，可以是任何數據類型，包括基本類型和用戶自定義類型（結構體或類）；Next是鏈表數據結構中的指針，這是一個單向鏈表，它指向下一個元素的地址。在邏輯上，鏈表其實就是一個數組Node[]，不過，這個數組的元素不是連續分佈的，元素可以在內存的任何位置（即可以亂序），抽象出來的數組Node[]，每個元素記錄的是數據的地址，亦即這可視爲一個指針數組，每個元素都是指針——這個數組在我們的大腦中。

如圖：鏈表的頭結點指針Head，指向第1個元素的地址，這個地址是3，按圖索驥，我們到第3列上找到這個數據Node[0]，也就找到它的數據包Data1，用解指針引用操作，可以取出這個數據（注意：凡是指針引用數據，均是這般間接的，先取地址，然後取數據，是兩步，CPU的動作多了）。找到第1個元素之後，我們可以依據它的Next指針找到第2個數據，它指向地址6。看到沒有？鏈表的數據地址與數組不同之處正在這裏，數據的分佈不是連續的！這就所謂“鏈”的意思，用Next指針這個“鈎”，把各個元素串起來，一旦其中一個環節（結點）的指針指錯了地方，整個鏈條就斷開了（鏈表的脆弱性正在這裏）。

對數組，我們可以直接從下標定位到數據處，因爲每個元素都是整齊排列的，間隙一樣，用下標定位數據的尋址很快捷，乘數就是了。但鏈表不一樣，如上所言，要找到鏈表的一個元素，必須從某個節點開始，逐個從它的Next開始找下去，直到找到爲止。你無法跳過任何一個元素！鏈表的隨機查尋效率比數組低，這是依據模型就可以理解的。


[ 本帖最后由 TonyDeng 于 2015-3-17 01:30 编辑 ]

鏈表插入數據的操作，比如我們要在最後追加一個結點：首先，必須先在內存中申請到數據的實體，比如在地址20處“隨機”獲得空間，填入數據，然後到Node[3]結點處，把Next的値修改爲20，那樣，兩個數據就勾搭起來了。鏈表追加和插入、刪除數據的效率比數組高，這也從這個模型可以知道的結果。

插入操作：在鏈表的某個元素後面插入數據，衹需把鈎子設置好即可。仍用前面的數據，新元素Node[4]在地址20處，但要把它插在元素1和2中間，這時我們不用挪動數據，衹要把Node[1]的Next=20，再把新元素Node[4]的Next=10，這樣把鏈子串順當，數據就插好了。想想我爲什麽刻意挑這個數字20？以及要把元素插在Node[1]和Node[2]中間？爲什麽真能插得成？

刪除操作：自己按照前面介紹的模型想一想怎麽操作？有什麽需要注意和可以利用的特點？


[ 本帖最后由 TonyDeng 于 2015-3-17 11:49 编辑 ]

這個模型，屬於單向鏈表，它是從前往後查找數據的，有時需要逆向查找，也可以構造雙向鏈表，多用一個指針，既指向下一個元素，也指向前一個元素，這些都是可以靈活處理的。一旦把頭和尾搭起來，就是一個閉合環。

鏈表的運用，並非一定要從頭結點開始，實際上可以從任意一個元素開始——我們衹要拿這個元素當頭就可以了。

弄明白了1樓的模型，想做什麽，都可以想到該怎麽做、該注意什麽，不知道模型，死記硬背，那是沒用的。比如，不要以爲Next必須就是C的指針，或地址，那可以是如圖中那樣是一個數據表的記錄行數、或別的什麽指向性數據。一切皆抽象！數據結構的知識點在C/C++之後，不是衹有C/C++才可以用指針和構造鏈表的，那是一門抽象的課程，如果鏈表衹有C/C++才能構造和使用，就一點意思都沒有。就如所謂的數據區，什麽常數區、堆、棧之類，你管得著具體的可執行格式這些數據放在哪裏呢，它就是按照字面意義上的邏輯用法，衹讀，就衹能讀不能寫、不能改，知道這一點就夠了，具體怎麽實現的，與你無關，探尋那些不見得有多大的幫助，反而衹能因你越具體而遠離抽象，落得個形而下，一輩子做定碼農，永沒上位機會。


[ 本帖最后由 TonyDeng 于 2015-3-17 01:17 编辑 ]

鏈表就是動態搭建的，不存在什麽動態、靜態鏈表的説法。鏈表的最大特點，就是數據元素是沒有確定位置的，面向這種未知情形。在內存中的鏈表數據，寫入了磁盤文件，再取出來，每取一個元素的數據，都要重新給Next賦値，需要真實的當時的地址，而不是之前存下去的地址，那個地址是廢的，原樣取出肯定錯，所以你衹要讀出Data就好了，不要理會Next的値。我見過壇上有人問過這類問題，故在此特意指出。總而言之，明白1樓的模型，一切都順理成章，全部可以在那裏找到依據的。

[ 本帖最后由 TonyDeng 于 2015-3-17 01:19 编辑 ]

現在，可以稍微離題談一談內存碎片和malloc()分配失敗的問題了。

還是1樓的圖。假定內存空間總共就是12，我們已經按圖那樣佔用了4，還剩8，但是，問題來了：你無法成功申請5的內存！你試試想象一下，在空隙處多佔一些數據，看剩餘的分配方案怎樣？最極端的可能，就算總空閑內存有7，你可能連3也申請不到——在位置8處佔1個。很多人以爲內存管理很容易，總是要走低級路綫，殊不知在你頻繁申請和釋放之下，會把內存弄成怎樣破碎不堪的結果而不自知。malloc()會在什麽時候失敗？往往就是在這種純看數字的誘惑下失敗。指針滿天飛，讓CPU全世界跑來跑去，效率真的很高？我之所以說不要對int之類的小數據用malloc()就是這個道理，你最好一次申請一大塊，不要割碎的來，動態申請內存不是那樣用的。現在算好了，指針的長度夠大，一次可以訪問許遠，如果是以前，有tiny指針和near、far、huge指針的概念，是靠一個搭一個地伸長的，16位機可以用出32位指針的效果，同樣現在32位機也可以用出64位甚至128位程序的效果（不要以爲指針就是一個整數，那種把指針和整數混搭了賦値來賦値去的做法，完全就是一知半解的胡來，邏輯不對不說，技術上也是莫大的漏洞），用指針的效率更低。不要爲用指針而硬用，太多初學者迷信指針神話了。

能夠用數組，就盡量用數組，數組開在棧上和堆上均可，這是忠告。除非迫不得已，不要動輒考慮鏈表，有得選擇，就直接用C++的vector，取代數組、取代鏈表，別給自己製造麻煩，那不顯得你高明。

btw: 曾有人問，爲什麽數據的地址變了？我想說，那可能是你亂用指針造成指錯了，不是數據的地址變了。問你怎麽知道數據的地址變了，你說用調試器跟出來的，你跟的是指針還是數據本身？


[ 本帖最后由 TonyDeng 于 2015-3-17 01:27 编辑 ]

毀人是不辛苦的~

用指針直接指向其中一個結點就可以了。不是雙向鏈表你怎麽從後往前刪？能夠把鏈表從中間刪掉一截的事實就説明可從任意元素開始作入口。


[ 本帖最后由 TonyDeng 于 2015-3-17 01:49 编辑 ]

下面是一個常規的鏈表處理示範：

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

// 結點數據結構
struct Node
{
    int   Value;                // 數據的内容（按需要可爲任何數據類型）
    Node* Next;                 // 數據的地址
};

// 函數原型
void Pause(void);
int GetInt(void);
Node* GetNode(void);
void ShowData(const Node* node);
void ListLinkData(const Node* head);
void FreeLink(Node* head);

// 程序主入口
int main(void)
{
    Node* linkHead = GetNode();
    if (linkHead != NULL)
    {
        Node* p = linkHead;
        Node *node;
        while ((node = GetNode()) != NULL)
        {
            p->Next = node;
            p = node;
        }
    }
    ListLinkData(linkHead);
    FreeLink(linkHead);
   
    Pause();
    return EXIT_SUCCESS;
}

// 暫停等待用戶按鍵
void Pause(void)
{
    printf_s("\n按任意鍵繼續...");
    _getch();
}

// 從控制臺鍵盤讀入一個int型數據
int GetInt(void)
{
    int value = 0;
    do
    {
        value = 0;
        printf_s("請輸入一個整數: ");
        fflush(stdin);
    } while (scanf_s("%d", &value) != 1);
    return value;
}

// 創建一個結點數據並從鍵盤輸入內容，以輸入0爲結束標識
Node* GetNode(void)
{
    Node* node = (Node*)calloc(1, sizeof(Node));
    if (node != NULL)
    {
        node->Value = GetInt();
        if (node->Value == 0)
        {
            // 輸入零結束時應把當前已申請的內存釋放掉
            free(node);
            node = NULL;
        }
    }
    else
    {
        printf_s("內存不足");
    }
    return node;
}

// 輸出結點的信息
void ShowData(const Node* node)
{
    printf_s("Adress = %p, Value = %d, Next = %p\n", node, node->Value, node->Next);
}

// 從指定的結點開始列出鏈表數據
void ListLinkData(const Node* head)
{
    if (head != NULL)
    {
        const Node* node = head;
        do
        {
            ShowData(node);
            node = node->Next;
        } while (node != NULL);
    }
}

// 刪除並釋放從指定節點開始的鏈表數據
void FreeLink(Node* head)
{
    if (head != NULL)
    {
        Node* next;
        do
        {
            next = head->Next;
            free(head);
            head = NULL;
            head = next;
        } while (next != NULL);
    }
}

它的運行效果如下圖：

輸出測試解讀：第1列是鏈表結點自身的數據地址，第2列是數據包的內容，第3列是該結點的Next指針指向的地址，檢驗的目標，是第1行的第3列指向第2行的第一列。

修改一下測試用例，補充在鏈表中插入和刪除元素的功能。

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

// 結點數據結構
struct Node
{
    int   Value;                // 數據的内容（按需要可爲任何數據類型）
    Node* Next;                 // 數據的地址
};

// 函數原型
void Pause(void);
Node* InsertNode(Node* to, Node* from);
Node* DeleteNode(Node* const head, Node* const node);
void ShowData(const Node* node);
void ListLinkData(const Node* head);
void FreeLink(Node* head);

// 程序主入口
int main(void)
{
    Node* linkHead = NULL;

    printf_s("從數組中提取數據生成鏈表\n");
    int data[] = { 1, 2, 3, 4, 5 };
    Node* node = linkHead;
    for (int index = 0; index < _countof(data); ++index)
    {
        Node* p = (Node*)calloc(1, sizeof(Node));
        p->Value = data[index];
        node = InsertNode(node, p);
        if (linkHead == NULL)
        {
            linkHead = node;
        }
    }
    ListLinkData(linkHead);
    putchar('\n');

    printf_s("在第2個元素後面插入一個新的元素\n");
    node = (Node*)calloc(1, sizeof(Node));
    node->Value = 10;
    InsertNode(linkHead->Next, node);
    ListLinkData(linkHead);
    putchar('\n');

    printf_s("刪除剛才插入元素的下一個\n");
    DeleteNode(linkHead, node->Next);
    ListLinkData(linkHead);
    putchar('\n');

    FreeLink(linkHead);
   
    Pause();
    return EXIT_SUCCESS;
}

// 暫停等待用戶按鍵
void Pause(void)
{
    printf_s("\n按任意鍵繼續...");
    _getch();
}

// 將form元素插入在to元素後，如果to爲NULL，則將from創建爲鏈頭，返回from
Node* InsertNode(Node* to, Node* from)
{
    Node* last = NULL;

    if (to != NULL)
    {
        if (to->Next != NULL)
        {
            last = to->Next;
        }
        to->Next = from;
        from->Next = last;
    }

    return from;
}

// 刪除指定的結點node，返回其後的結點
// 對單向鏈表，爲了查尋前面的元素，必須從鏈表開始檢索，所以需要傳入鏈頭
Node* DeleteNode(Node* const head, Node* const node)
{
    Node* previous = NULL;      // 前一個元素
    Node* p = head;             // 遍歷指針
    while ((p != NULL) && (p != node))
    {
        previous = p;
        p = p->Next;
    }
    previous->Next = node->Next;
    free(node);

    return node->Next;
}

// 輸出結點的信息
void ShowData(const Node* node)
{
    printf_s("Adress = %p, Value = %d, Next = %p\n", node, node->Value, node->Next);
}

// 從指定的結點開始列出鏈表數據
void ListLinkData(const Node* head)
{
    if (head != NULL)
    {
        const Node* node = head;
        do
        {
            ShowData(node);
            node = node->Next;
        } while (node != NULL);
    }
}

// 刪除並釋放從指定節點開始的鏈表數據
void FreeLink(Node* head)
{
    if (head != NULL)
    {
        Node* next;
        do
        {
            next = head->Next;
            free(head);
            head = NULL;
            head = next;
        } while (next != NULL);
    }
}

運行效果：



[ 本帖最后由 TonyDeng 于 2015-3-17 17:58 编辑 ]