在了解完什么是資料結構之后，讓我們一起來探索下資料結構中常見的一種—鏈表，

鏈表

鏈表是資料結構之一，其中的資料呈線性排列，在鏈表中，資料的添加和洗掉都較為方便，就是訪問比較耗費時間，

如上圖所示就是鏈表的概念圖，Blue、Yellow、Red 這 3 個字串作為資料被存盤于鏈表中，也就是資料域，每個資料都有 1 個指標，即指標域，它指向下一個資料的記憶體地址，其中 Red 是最后 1 個資料，Red 的指標不指向任何位置，也就是為 NULL，指向 NULL 的指標通常被稱為空指標，

在鏈表中，資料一般都是分散存盤于記憶體中的，無須存盤在連續空間內，

因為資料都是分散存盤的，所以如果想要訪問資料，只能從第 1 個資料開始，順著指標的指向一一往下訪問（這便是順序訪問），比如，想要找到 Red 這一資料，就得從 Blue 開始訪問，這之后，還要經過 Yellow，我們才能找到 Red，

如果想要添加資料，只需要改變添加位置前后的指標指向就可以，非常簡單，比如，在 Blue 和 Yellow 之間添加 Green，

首先將 Blue 的指標指向的位置變成 Green，然后再把 Green 的指標指向 Yellow，資料的添加就大功告成了，

資料的洗掉也一樣，只要改變指標的指向就可以，比如洗掉 Yellow，

這時，只需要把 Green 指標指向的位置從 Yellow 變成 Red，洗掉就完成了，雖然 Yellow 本身還存盤在記憶體中，但是不管從哪里都無法訪問這個資料，所以也就沒有特意去洗掉它的必要了，今后需要用到 Yellow 所在的存盤空間時，只要用新資料覆寫掉就可以了，

那么對鏈表的操作所需的運行時間到底是多少呢？在這里，我們把鏈表中的資料量記成 n，訪問資料時，我們需要從鏈表頭部開始查找（線性查找），如果目標資料在鏈表最后的話，需要的時間就是 O（n），

另外，添加資料只需要更改兩個指標的指向，所以耗費的時間與 n 無關，如果已經到達了添加資料的位置，那么添加操作只需花費 O（1）的時間，洗掉資料同樣也只需 O（1）的時間，

鏈表的實作

在對鏈表有了大概的認識以后，我們用 Java 去實作屬于自己的鏈表：

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

class MyLinkedList {
    int size;
    /**
     * 哨兵節點作為偽頭
     */
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    /**
     * 獲取鏈表第 index 個節點的值，如果索引是無效的，回傳-1
     *
     * @param index
     * @return
     */
    public int get(int index) {
        // 若索引無效
        if (index < 0 || index >= size) {
            return -1;
        }

        ListNode curr = head;
        // 從偽頭節點開始，向前走 index+1 步
        for (int i = 0; i < index + 1; ++i) {
            curr = curr.next;
        }
        return curr.val;
    }

    /**
     * 在頭部插入節點
     *
     * @param val
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    /**
     * 在尾部插入節點
     *
     * @param val
     */
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    /**
     * 在鏈表中的第 index 個節點前添加值為 val 的一個節點，如果 index 等于鏈表的長度時，節點將被添加到鏈表的末尾，如果 index 大于鏈表長度，節點將無法插入
     *
     * @param index
     * @param val
     */
    public void addAtIndex(int index, int val) {
        // 如果index大于長度，則不會插入該節點，
        if (index > size) {
            return;
        }

        // 如果 index 為負，則該節點將插入串列的開頭，
        if (index < 0) {
            index = 0;
        }

        ++size;
        // 查找要添加的節點的前驅節點
        ListNode pred = head;
        for (int i = 0; i < index; ++i) {
            pred = pred.next;
        }

        // 要添加的節點
        ListNode toAdd = new ListNode(val);
        // 通過改變 next 來插入節點
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    /**
     * 如果 index 是有效的，洗掉鏈表中的第 index 個節點
     *
     * @param index
     */
    public void deleteAtIndex(int index) {
        // 如果 index 無效，則不執行任何操作
        if (index < 0 || index >= size) {
            return;
        }

        size--;
        // 找到要洗掉節點的前驅節點
        ListNode pred = head;
        for (int i = 0; i < index; ++i) {
            pred = pred.next;
        }

        // 通過改變 next 來洗掉節點
        pred.next = pred.next.next;
    }
}

到這里，我相信大家應該對鏈表有了進一步的理解，大家可以用不同的語言去設計實作下，