2020-02-21 08:25:00 EdisonTalk

每天5分鐘，學習數據結構

在中，我們學習了線性表最基礎的表現形式-順序表，但是其存在一定缺點：必須佔用一整塊事先分配好的存儲空間，在插入和刪除操作上需要移動大量元素（即操作不方便），於是不受固定存儲空間限制並且可以進行比較快捷地插入和刪除操作的鏈表橫空出世，所以我們就來複習一下鏈表，這一篇主要會集中在單鏈表。

1 認識單鏈表

單鏈表的節點結構

在鏈表中，每個節點由兩部分組成：數據域和指針域。

單鏈表的總體結構

鏈表就是由N個節點鏈接而成的線性表，如果其中每個節點只包含一個指針域那麼就稱為單鏈表，如果含有兩個指針域那麼就稱為雙鏈表。

PS：在線性表的鏈式存儲結構中，為了便於插入和刪除操作的實現，每個鏈表都帶有一個頭指針（或尾指針），通過頭指針可以唯一標識該鏈表。從頭指針所指向的節點出發，沿著節點的鏈可以訪問到每個節點。

2 單鏈表的實現

多說無益，現在我們直接動手用C#來實現一個單鏈表吧！

節點定義

<code>public class Node{    // 數據域    public T Item { get; set; }    // 指針域    public Node Next { get; set; }    public Node() {}    public Node(T item){        this.Item = item;    }}/<code>

此處定義Node類為單鏈表的節點，其中包括了一個數據域Item與一個指針域Next（指向後繼節點的位置）。

節點的新增

① 默認在尾節點後插入新節點

<code>public void Add(T value){    Node newNode = new Node(value);    if (this.head == null)    {        // 如果鏈表當前為空則置為頭結點        this.head = newNode;    }    else    {        Node prevNode = this.GetNodeByIndex(this.count - 1);        prevNode.Next = newNode;    }    this.count++;}/<code>

首先判斷頭結點是否為空，其次依次遍歷各節點找到尾節點的前驅節點，然後更改前驅節點的Next指針指向新節點即可。

② 指定在某個節點後插入新節點

<code>public void Insert(int index, T value){    Node tempNode = null;    if (index < 0 || index > this.count)    {        throw new ArgumentOutOfRangeException("index", "索引超出範圍");    }    else if (index == 0)    {        if (this.head == null)        {            tempNode = new Node(value);            this.head = tempNode;        }        else        {            tempNode = new Node(value);            tempNode.Next = this.head;            this.head = tempNode;        }    }    else    {        Node prevNode = GetNodeByIndex(index - 1);        tempNode = new Node(value);        tempNode.Next = prevNode.Next;        prevNode.Next = tempNode;    }    this.count++;}/<code>

這裡需要判斷是否是在第一個節點進行插入，如果是則再次判斷頭結點是否為空。