關於鏈表（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 编辑 ]

看完《我的早更女友》过来，发现T版还在毁人不倦，辛苦啦！
我就捧捧场啦！
dos文件系统就是一个典型的链表应用。文件以簇为基本单位存在硬盘中，而一个文件由哪些簇构成则是由一个链表指明，链表存在专门区域即所谓的文件分配表（通常格式化硬盘时看到的fat、ntfs），而链表的头则在文件目录中，所以读一个文件首先从访问目录开始，从目录获得该文件存储的第一个簇指针，硬盘上的数据区中的每个簇都对应fat中的一个固定位置（fat16占2个字节、fat32占4个字节、ntfs占8个字节），从fat中这个固定位置可获取该文件下一个簇的位置，如此链下去，直到读到簇指针为0xffff(-1)，链结束，文件也读取完毕。
在内存中使用链表，我觉得更多的是当作动态数组来使用，程序设计之初，你并不确定你将使用的成员数量，这时链表即可充分发挥作用。
使用链表会从head往后申请内存，使用完毕切记要从后往前逐个释放内存，段不可随意释放，链一旦中断则很难原样链接（文件系统里有一个程序chkdsk就是修复链的，它并不能完全修复一个文件），对链表的增删改也要算法明确、及时处理，一旦混乱很可能是系统崩溃。
T版在4楼所说的“不一定从链表头开始访问”是有前提条件的，前提条件就是你也像文件的fat一样使用了一个静态的指针数组存储链表指针（数据在堆中），否则你是无法从内存堆中知道哪一块内存存储的是下一个链的指针的。

毀人是不辛苦的~

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


[ 本帖最后由 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行的第一列。