本篇我們會(huì)討論單向鏈表，在所有線性存儲(chǔ)結(jié)構(gòu)當(dāng)中，鏈表是最常用且非常重要的數(shù)據(jù)結(jié)構(gòu)，因?yàn)殒湵韺?shí)現(xiàn)隊(duì)列(Queue)以及環(huán)形隊(duì)列(Circle Queue),棧(Stack)的最佳選擇,在許多app中,單鏈表應(yīng)用隨處可見(jiàn)。例如很多即時(shí)通訊工具的好友列表，電話中的通訊錄,以及媒體播放器的播放列表都廣泛地用到了鏈表。

單向鏈表(Single-LinkedList)，由一個(gè)或多個(gè)節(jié)點(diǎn)(Node)組成,每個(gè)結(jié)點(diǎn)承載著特定數(shù)據(jù)類型的對(duì)象。

鏈表示意圖

結(jié)點(diǎn)(Node)

• 數(shù)據(jù)域(Data Field):用于保存實(shí)際的對(duì)象數(shù)據(jù)，
• 指針域(Data Pointer),用于指向下一個(gè)相同數(shù)據(jù)類型的節(jié)點(diǎn)的內(nèi)存地址。

ArrayList vs LinkedList

我們用一個(gè)形象生動(dòng)的例子，來(lái)比較一下ArrayList和LinkedList的差別

• ArrayList內(nèi)部的堆內(nèi)存塊是連續(xù)的內(nèi)存塊，而LinkedList的元素存儲(chǔ)位置在堆中通常是不連續(xù)的。

  
  
  LinkedList的節(jié)點(diǎn)在堆內(nèi)存中可能不連續(xù)
  
  
  ArrayList在堆中是連續(xù)的內(nèi)存空間

• 對(duì)于中間元素的插入/刪除操作，ArrayList的性能消耗通常是O(n)，而LinkedList通常是O(1).

  • ArrayList元素插入場(chǎng)景,需要將后面的N個(gè)元素逐個(gè)向后移動(dòng)。

    
    
    ArrayList和Vector中間插入元素

  • LinkedList元素插入元素的場(chǎng)景,只需改變現(xiàn)有元素與新增元素的指針指向關(guān)系即可。

    
    
    LinkedList中間插入元素

• 對(duì)于遍歷搜索元素操作，ArrayList的性能開消為O(n),而LinkedList通常為O(n)
• 對(duì)于下標(biāo)索引訪問(wèn)操作, ArrayList的性能開銷為O(1),而LinkedList通常為O(n)

那么我們來(lái)看看ArrayList與LinkedList的各種操作下的時(shí)間復(fù)雜度對(duì)比，這個(gè)表并沒(méi)有考慮到最差的情況。這表面上看，LinkedList似乎跟ArrayList沒(méi)什么優(yōu)勢(shì)。LinkList在中間位置和末尾插入的時(shí)間復(fù)雜度之所以為O(n)，是因?yàn)槊看卧诓迦朐刂氨仨毎l(fā)生遍歷操作找到插入元素對(duì)應(yīng)的位置。

性能比較

如果你對(duì)標(biāo)準(zhǔn)庫(kù)vector或我前一篇文章ArrayList的內(nèi)部堆內(nèi)存管理有所了解的話,應(yīng)該知道ArrayList在添加或刪除達(dá)到一個(gè)指定比例值時(shí)，內(nèi)存可能需要擴(kuò)容/收縮(簡(jiǎn)稱resize).

假設(shè)ArrayList的元素類型為T,原有內(nèi)存數(shù)量為n,resize的內(nèi)存數(shù)量為m=malloc(sizeof(T)*n)的內(nèi)存空間重分配的時(shí)間復(fù)雜度為O(m)這個(gè)malloc操作屬于操作系統(tǒng)底層的,另外ArrayList本身n個(gè)元素的深度拷貝到新堆內(nèi)存空間的一系列過(guò)程,這個(gè)時(shí)間復(fù)雜度就為O(n)那么這種最差的情況下

那么，ArrayList在插入/刪除操作最差的情況，確切是O(m)+O(n)

LinkedList相比之下就沒(méi)有這些昂貴的操作,LinkedList只會(huì)對(duì)插入/刪除的元素的一次性malloc或free操作，無(wú)需額外的連續(xù)內(nèi)存重分配。所以LinkedList在插入或刪除方面有著明顯的性能優(yōu)勢(shì)。

需要注意的是遍歷操作與下標(biāo)訪問(wèn)是兩個(gè)絕然不同的概念

• 遍歷操作是值通過(guò)for/while/foreach循環(huán)控制語(yǔ)句遍歷整個(gè)線性表,例如arr是一個(gè)線性表，下面的示例都屬于遍歷結(jié)構(gòu)，他們的時(shí)間復(fù)雜度約定為O(n)

for(auto i=0;i<arr.size;i++){....}
//或
foreach(item in arr){...}
//或
size_t i=0;
while(i<arr.size){...}
//或
while(arr.next()){...}

• 下標(biāo)索引訪問(wèn):可能會(huì)有人疑問(wèn)ArrayList的下標(biāo)索引操作的時(shí)間復(fù)雜度不是O(n)嗎？當(dāng)然不是，因?yàn)锳rrayList的下表訪問(wèn)的底層實(shí)現(xiàn)是其內(nèi)部的數(shù)據(jù)指針d_arr加或減整數(shù)，即表達(dá)式*(d_arr+i)或d_arr[i]，只要i的值確定,這是可以在恒定時(shí)間內(nèi)完成指針偏移的常量,因此ArrayList的下標(biāo)索引操作的時(shí)間復(fù)雜度為O(1).通常遍歷操作內(nèi)嵌下標(biāo)索引訪問(wèn)。

鏈表類接口的基本定義

以前說(shuō)過(guò)用C++實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)合適，寫類接口對(duì)比C代碼,C++在語(yǔ)法上更優(yōu)雅和邏輯清晰，并且C++具有訪問(wèn)級(jí)別的限制，使得外部調(diào)用代碼無(wú)法隨意修改鏈表中的數(shù)據(jù)。該系列的文章，我會(huì)用到C++來(lái)實(shí)現(xiàn)該單向鏈表。

首先LinkedList由一個(gè)節(jié)點(diǎn)類(Node)和一個(gè)鏈表類(LinkedList)構(gòu)成。

• 節(jié)點(diǎn)類(Node)：類名英文寫法上約定一般為Node，他包括兩個(gè)數(shù)據(jù)屬性，
  • 數(shù)據(jù)字段，我們約定為data,用于承載類型為T的對(duì)象數(shù)據(jù)的實(shí)體。
  • 指針字段，我們約定為next用于指向下一個(gè)同樣T類型的Node節(jié)點(diǎn)。
• 鏈表類(LinkedList):就是構(gòu)成整個(gè)鏈表的驅(qū)動(dòng)主體，你可以將鏈表比喻為一輛很長(zhǎng)的火車。LinkedList對(duì)象可是就是“駕駛員”他負(fù)責(zé)維護(hù)整個(gè)鏈表的狀態(tài)，而Node對(duì)象就是(車廂)，而最后一個(gè)節(jié)點(diǎn)需要指向一個(gè)nullptr。
  • head指針:負(fù)責(zé)指向整個(gè)鏈表的第一個(gè)節(jié)點(diǎn)(火車頭)，它是遍歷整個(gè)鏈表的起點(diǎn)。
  • 尺寸(size):負(fù)責(zé)記錄整個(gè)鏈表的節(jié)點(diǎn)數(shù)(有多少節(jié)車廂)
    
    LinkedList對(duì)象與Node對(duì)象的關(guān)系

Node類接口

這里需要注意的是我們定義的同時(shí)，我們需要類內(nèi)部聲明一個(gè)LinkedList接口的友元函數(shù)，以便LinkedList類接口的成員函數(shù)能夠訪問(wèn)Node類接口的私有數(shù)據(jù)成員。這是設(shè)計(jì)模式中典型的組合模式，在C++中普遍存在。

#include <iostream>
#include <stdlib.h>

template <class T>
class LinkedList;

template <class T>
class Node
{
private:
    Node *d_next; //指向下一個(gè)節(jié)點(diǎn)
    T d_data;

public:
    Node();
    //自定義構(gòu)造函數(shù)
    Node(T);
    //返回節(jié)點(diǎn)上的元素實(shí)體
    const T &elem();

    //返回當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址
    Node<T> *next();

    //析構(gòu)函數(shù)
    ~Node();
    //LinkList的友元函數(shù)
    friend class LinkedList<T>;

    template <typename R>
    friend std::ostream &operator<<(std::ostream &, const Node<R> &);
};

LinkedList類接口

template <class T>
class LinkedList
{
private:
    //頭指針
    Node<T> *d_head;
    //中間節(jié)點(diǎn)
    Node<T> *d_mid;
    //未指針
    Node<T> *d_last;
    //鏈表尺寸
    size_t d_size;

    //查找元素所在位置
    Node<T> *_search(const T &val);
    //二分查找法
    size_t binary_search(size_t s, size_t e, size_t k);

public:
    //默認(rèn)構(gòu)造函數(shù)(空鏈表)
    LinkedList();

    LinkedList(size_t);
    //拷貝構(gòu)造函數(shù)
    LinkedList(const LinkedList &list);
    //移動(dòng)構(gòu)造函數(shù)
    LinkedList(LinkedList &&otl);
    //析構(gòu)函數(shù)
    ~LinkedList();
    //末端插入元素
    void push_back(T);
    //在頭部插入元素
    void push_head(T);

    //獲取頭部元素
    T front();
    // 獲取末端元素
    T last();

    //顛倒鏈表順序
    void reverse();

    //查找元素的值，刪除該元素
    void remove(const T &value);
    //在指定位置，插入元素
    void insert(size_t idx, T elem);

    //迭代接口:返回下一個(gè)節(jié)點(diǎn)
    // T next();

    //公開的查找節(jié)點(diǎn)函數(shù)
    Node<T> *search(const T &val);

    Node<T> *search_v2(size_t);

    //清空整個(gè)鏈表
    void clear();

    //打印鏈表
    template <class R>
    friend std::ostream &operator<<(std::ostream &, const LinkedList<R> &);

    //索引訪問(wèn)操作符號(hào)
    T operator[](size_t);

    //獲取尺寸
    size_t size()
    {
        return d_size;
    }
    //獲取中間節(jié)點(diǎn)
    Node<T> *mid_node();
    //獲取中間節(jié)點(diǎn)
    Node<T> *mid_node(size_t &);
};

小結(jié)

本篇主要是對(duì)鏈表一個(gè)概念，以及和ArrayList做了一些性能上的對(duì)比，可以知道，在寫入/刪除元素操作方面具有其他線性表結(jié)構(gòu)代替的性能優(yōu)勢(shì)。似乎單項(xiàng)鏈表本質(zhì)上來(lái)說(shuō)是不支持下標(biāo)索引訪問(wèn)，只能通過(guò)每次O(n)的遍歷來(lái)模擬下標(biāo)索引的訪問(wèn)操作，因此這方面不如ArrayList和標(biāo)準(zhǔn)庫(kù)的vector,后面的相關(guān)隨筆會(huì)談到這方面。很晚了，睡覺(jué)去~~!!