通過(guò)研究證明，怎么學(xué)好數(shù)據(jù)結(jié)構(gòu)？怎么入門？需要學(xué)些什么東西？鏈表是數(shù)據(jù)結(jié)構(gòu)的重要部分，學(xué)好用好鏈表，在解題的過(guò)程中，思路將更加清晰，鏈表作為數(shù)據(jù)結(jié)果的基礎(chǔ)之一，本篇將會(huì)通過(guò)圖文和代碼展示的形式系統(tǒng)的介紹。

什么是鏈表？

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

（1）數(shù)組—順序存儲(chǔ)

數(shù)組作為一個(gè)順序儲(chǔ)存方式的數(shù)據(jù)結(jié)構(gòu)，可是有大作為的，它的靈活使用為我們的程序設(shè)計(jì)帶來(lái)了大量的便利；

但數(shù)組最大的缺點(diǎn)就是我們的插入和刪除時(shí)需要移動(dòng)大量的元素，所以，很多人想到需要大量的消耗時(shí)間，以及冗余度就想放棄或?qū)で髣e的方法。

以C語(yǔ)言數(shù)組插入一個(gè)元素為例，當(dāng)我們需要在一個(gè)數(shù)組{1,2,3,4}的第1個(gè)元素后的位置插入一個(gè)’A’時(shí)，我們需要做的有：

1. 將第1個(gè)元素后的整體元素后移，形成新的數(shù)組{1,2,2,3,4}

2. 再將第2個(gè)元素位置的元素替換為我們所需要的元素’A’

3. 最終形成我們的預(yù)期，這需要很多的操作喔。

上圖可以看出，使用數(shù)組都有這兩大缺點(diǎn)：

1. 插入刪除操作所需要移動(dòng)的元素很多，浪費(fèi)算力。

2. 必須為數(shù)組開足夠的空間，否則有溢出風(fēng)險(xiǎn)。

（2）鏈表—鏈?zhǔn)酱鎯?chǔ)

由于數(shù)組的這些缺點(diǎn)，自然而然的就產(chǎn)生鏈表的思想。

鏈表通過(guò)不連續(xù)的儲(chǔ)存方式，自適應(yīng)內(nèi)存大小，以及指針的靈活使用，巧妙的簡(jiǎn)化了上述的內(nèi)容。

鏈表的基本思維是，利用結(jié)構(gòu)體的設(shè)置，額外開辟出一份內(nèi)存空間去作指針，它總是指向下一個(gè)結(jié)點(diǎn)，一個(gè)個(gè)結(jié)點(diǎn)通過(guò)NEXT指針相互串聯(lián)，就形成了鏈表。

其中DATA為自定義的數(shù)據(jù)類型，NEXT為指向下一個(gè)鏈表結(jié)點(diǎn)的指針，通過(guò)訪問(wèn)NEXT，可以引導(dǎo)我們?nèi)ピL問(wèn)鏈表的下一個(gè)結(jié)點(diǎn)。

對(duì)于一連串的結(jié)點(diǎn)而言，就形成了鏈表如下圖：

相比起數(shù)組，鏈表解決了數(shù)組不方便移動(dòng)，插入，刪除元素的弊端，但相應(yīng)的，鏈表付出了更加大的內(nèi)存犧牲換來(lái)的這些功能的實(shí)現(xiàn)。

鏈表概述

包含單鏈表，雙鏈表，循環(huán)單鏈表，實(shí)際應(yīng)用中的功能不同，但實(shí)現(xiàn)方式都差不多。

鏈表與數(shù)組的區(qū)別

　　回憶下數(shù)組的概念 ，所謂數(shù)組，是相同數(shù)據(jù)類型的元素按一定順序排列的集合。根據(jù)概念我們可以知道數(shù)組在內(nèi)存中連續(xù)，鏈表不連續(xù)；由于不同的存儲(chǔ)方式導(dǎo)致數(shù)組靜態(tài)分配內(nèi)存，鏈表動(dòng)態(tài)分配內(nèi)存，數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū)；由于數(shù)組在內(nèi)存中連續(xù)，我們可以利用下標(biāo)定位，時(shí)間復(fù)雜度為O(1)，鏈表定位元素時(shí)間復(fù)雜度O(n)；但是由于數(shù)組的連續(xù)性數(shù)組插入或刪除元素的時(shí)間復(fù)雜度O(n)，鏈表的時(shí)間復(fù)雜度O(1)?？偨Y(jié)一下，數(shù)組和鏈表的區(qū)別如下：

　　1. 數(shù)組靜態(tài)分配內(nèi)存，鏈表動(dòng)態(tài)分配內(nèi)存

　　2. 數(shù)組在內(nèi)存中連續(xù)，鏈表不連續(xù)

　　3. 數(shù)組元素在棧區(qū)，鏈表元素在堆區(qū)

　　4. 數(shù)組利用下標(biāo)定位，時(shí)間復(fù)雜度為O(1)，鏈表定位元素時(shí)間復(fù)雜度O(n)；

　　5. 數(shù)組插入或刪除元素的時(shí)間復(fù)雜度O(n)，鏈表的時(shí)間復(fù)雜度O(1)。

C#實(shí)現(xiàn)鏈表的基本操作

以單鏈表為例，單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)由元素和指針構(gòu)成。元素表示數(shù)據(jù)元素的映象，就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元；指針指示出后繼元素存儲(chǔ)位置，就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。

以結(jié)點(diǎn)的序列表示的線性表稱作線性鏈表，也就是單鏈表，單鏈表是鏈?zhǔn)酱嫒〉慕Y(jié)構(gòu)。

public class Node<T>
{
    private T data;
    private Node<T> next;
 
    //有參構(gòu)造函數(shù)
    //主要用例實(shí)例化需要處理的節(jié)點(diǎn)用
    public Node(T item, Node<T> next)
    {
        data = item;
        this.next = next;
    }
 
    //無(wú)參構(gòu)造函數(shù)，用例實(shí)例化Node節(jié)點(diǎn)
    public Node()
    {
        data = default(T);
        next = null;
    }
 
    public Node<T> Next
    {
        get { return next; }
        set { this.next = value; }
    }
 
    public T Data
    {
        get { return data; }
        set { this.data = value; }
    }
}

接下來(lái)我們來(lái)實(shí)現(xiàn)鏈表的操作，構(gòu)造一個(gè)鏈表，在構(gòu)造鏈表里我們定一個(gè)頭結(jié)點(diǎn)的對(duì)象，頭結(jié)點(diǎn)是個(gè)很有用的節(jié)點(diǎn)，在后續(xù)代碼中就可以慢慢體會(huì)到

public class MyLinkList<T>
{
   public Node<T> Head { get; set; }
 
    //構(gòu)造器 
    public MyLinkList()
    {
        Head = null;
    }
}

（1）求鏈表的長(zhǎng)度，思路：從頭結(jié)點(diǎn)向后訪問(wèn)，直到最后一個(gè)節(jié)點(diǎn)，代碼展示：

public int Length()
 {
     var p = Head;
     int len = 0;
     while (p != null)
     {
         ++len;
         p = p.Next;
     }
     return len;
 }

（2）清空鏈表，這個(gè)就比較奧簡(jiǎn)單了，直接將頭結(jié)點(diǎn)置為null 即可，代碼展示：

public void Clear()
{
    Head = null;
}

（3）同理判斷鏈表是否為空也要用的頭結(jié)點(diǎn)，代碼展示：

public bool IsEmpty()
{
    if (Head == null)
    {
        return true;
    }
    else
    {
        return false;
    }
}

（4）在鏈表的末尾添加新元素，添加新元素，需要先判斷鏈表是否為空，如果為空我們要給頭結(jié)點(diǎn)賦值，如果不為空需要修改最后一個(gè)節(jié)點(diǎn)的next指向，代碼展示：

public void Append(T item)
 {
 
     if (Head == null)
     {
         Head = new Node<T>(item, null);
         return;
     }
     var p = new Node<T>();
     p = Head;
     while (p.Next != null)
     {
         p = p.Next;
     }
     p.Next = new Node<T>(item, null);
 }

（5）在單鏈表的第i個(gè)結(jié)點(diǎn)的位置前插入一個(gè)指定結(jié)點(diǎn)，首先需要找到插入的位置，然后修改相鄰節(jié)點(diǎn)的指向即可，代碼展示：

public void Insert(T item, int i)
{
 
    if (IsEmpty() || i < 1 || i > GetLength())
    {
        return;
    }
    //如果在第一個(gè)位置插入 則只需要將該節(jié)點(diǎn)的next 指向head即可
    if (i == 1)
    {
        var first = new Node<T>(item, null);
        first.Next = Head;
        Head = first;
        return;
    }
 
    var p = new Node<T>();
    p = Head;
    var left = new Node<T>();
    var right = new Node<T>();
    int j = 1;
    while (p.Next != null && j < i)
    {
        left = p;
        right = p.Next;
        ++j;
    }
    var q = new Node<T>(item, null);
    left.Next = q;
    q.Next = right;
}

（6）刪除指定節(jié)點(diǎn)，先找到要?jiǎng)h除的前一個(gè)結(jié)點(diǎn)，然后修改該結(jié)點(diǎn)的next指向即可。

（7）鏈表還有刪除、獲取、查找等操作，這些都相對(duì)簡(jiǎn)單，大家可以在做題中理解。