C# 數據結構--單鏈表

什么是單鏈表

　　這兩天看到很多有關單鏈表的面試題，對單鏈表都不知道是啥的我。經過學習和整理來分享一下啥是單鏈表和單鏈表的一些基本使用方法。最后看些網上有關單鏈表的面試題代碼實例。

啥是單鏈表?

　　單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。這組存儲單元既可以是連續的，也可以是不連續的。

　　鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) +指針(指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。

　　鏈表的結點結構：

實例代碼

public class Node<T>{    public T Data { set; get; }          //數據域,當前結點數據    public Node<T> Next { set; get; }    //位置域,下一個結點地址    public Node(T item)    {        this.Data = item;        this.Next = null;    }    public Node()    {        this.Data = default(T);        this.Next = null;    }}

public class LinkList<T>{    public Node<T> Head { set; get; } //單鏈表頭    //構造    public LinkList()    {        Head=null;    }    /// <summary>    /// 增加新元素到單鏈表末尾    /// </summary>    public void Append(T item)    {        Node<T> foot = new Node<T>(item);        Node<T> A = new Node<T>();        if (Head == null)        {            Head = foot;            return;        }        A = Head;        while (A.Next != null)        {            A = A.Next;        }        A.Next = foot;    }}

1.如果增加的是頭結點。直接把數據域（Data）給Head，Next為空。因為只有一個頭結點，沒有對應的下結點。

2.單鏈表是”不走回頭路“，所以每次增加都要從單鏈表的頭開始找到單鏈表最后一個結點（最后一個結點就是Next為NULL），然后把最后一個結點的Next設置成需增加的結點,這時要需增加的結點變身為最后一結點，他的Next為NULL。

public class LinkList<T>{    public Node<T> Head { set; get; } //單鏈表頭    //構造    public LinkList()    {        Head=null;    }    public void Delete(int i)    {        Node<T> A = new Node<T>();        if (i == 1)   //刪除頭        {            A = Head;            Head = Head.Next;            return;        }        Node<T> B = new Node<T>();        B = Head;        int j = 1;        while (B.Next != null && j < i)        {            A = B;            B = B.Next;            j++;        }        if (j == i)        {            A.Next = B.Next;        }    }}

1.如果刪除的是頭結點，那現在的頭結點就應該是頭結點的下一結點。

2.刪除結點如果不是頭結點。從單鏈表頭開始查詢要刪除結點的位置。并記錄刪除的前一結點值A和所要刪除的結點B。因為結點B被刪除了,所以結點A的Next就應該為B的Next。把結點A的Next設置為結點B的Next。

單鏈表類

public class LinkList<T>{    public Node<T> Head { set; get; } //單鏈表頭    //構造    public LinkList()    {        Clear();    }    /// <summary>    /// 求單鏈表的長度    /// </summary>    /// <returns></returns>    public int GetLength()    {        Node<T> p = Head;        int length = 0;        while (p != null)        {            p = p.Next;            length++;        }        return length;    }    /// <summary>    /// 判斷單鍵表是否為空    /// </summary>    /// <returns></returns>    public bool IsEmpty()    {        if (Head == null)            return true;        else            return false;    }    /// <summary>    /// 清空單鏈表    /// </summary>    public void Clear()    {        Head = null;    }    /// <summary>    /// 獲得當前位置單鏈表中結點的值    /// </summary>    /// <param name="i">結點位置</param>    /// <returns></returns>    public T GetNodeValue(int i)    {        if (IsEmpty() || i<1 || i>GetLength())        {            Console.WriteLine("單鏈表為空或結點位置有誤！");            return default(T);        }        Node<T> A = new Node<T>();        A = Head;        int j = 1;        while (A.Next!=null && j<i)        {            A = A.Next;            j++;        }        return A.Data;    }    /// <summary>    /// 增加新元素到單鏈表末尾    /// </summary>    public void Append(T item)    {        Node<T> foot = new Node<T>(item);        Node<T> A = new Node<T>();        if (Head == null)        {            Head = foot;            return;        }        A = Head;        while (A.Next != null)        {            A = A.Next;        }        A.Next = foot;    }    /// <summary>    /// 增加單鏈表插入的位置    /// </summary>    /// <param name="item">結點內容</param>    /// <param name="n">結點插入的位置</param>    public void Insert(T item, int n)    {        if (IsEmpty() || n < 1 || n > GetLength())        {            Console.WriteLine("單鏈表為空或結點位置有誤！");            return;        }        if (n == 1)  //增加到頭部        {            Node<T> H = new Node<T>(item);            H.Next = Head;            Head = H;            return;        }        Node<T> A = new Node<T>();        Node<T> B = new Node<T>();        B = Head;        int j = 1;        while (B.Next != null && j < n)        {            A = B;            B = B.Next;            j++;        }        if (j==n)        {            Node<T> C = new Node<T>(item);            A.Next = C;            C.Next = B;        }    }    /// <summary>    /// 刪除單鏈表結點    /// </summary>    /// <param name="i">刪除結點位置</param>    /// <returns></returns>    public void Delete(int i)    {        if (IsEmpty() || i < 1 || i > GetLength())        {            Console.WriteLine("單鏈表為空或結點位置有誤！");            return;        }        Node<T> A = new Node<T>();        if (i == 1)   //刪除頭        {            A = Head;            Head = Head.Next;            return;        }        Node<T> B = new Node<T>();        B = Head;        int j = 1;        while (B.Next != null && j < i)        {            A = B;            B = B.Next;            j++;        }        if (j == i)        {            A.Next = B.Next;        }    }    /// <summary>    /// 顯示單鏈表    /// </summary>    public void Dispaly()    {        Node<T> A = new Node<T>();        A = Head;        while (A != null)        {            Console.WriteLine(A.Data);            A = A.Next;        }    }    #region 面試題    /// <summary>    /// 單鏈表反轉    /// </summary>    public void Reverse()     {        if (GetLength()==1 || Head==null)        {            return;        }        Node<T> NewNode = null;        Node<T> CurrentNode = Head;        Node<T> TempNode = new Node<T>();        while (CurrentNode!=null)        {            TempNode = CurrentNode.Next;            CurrentNode.Next = NewNode;            NewNode = CurrentNode;            CurrentNode = TempNode;        }        Head = NewNode;        Dispaly();    }    /// <summary>    /// 獲得單鏈表中間值    /// 思路：使用兩個指針，第一個每次走一步，第二個每次走兩步：    /// </summary>    public void GetMiddleValue()    {        Node<T> A = Head;        Node<T> B = Head;        while (B!=null && B.Next!=null)        {            A = A.Next;            B = B.Next.Next;        }        if (B != null) //奇數        {            Console.WriteLine("奇數:中間值為：{0}", A.Data);        }        else    //偶數        {            Console.WriteLine("偶數:中間值為：{0}和{1}", A.Data, A.Next.Data);        }    }    #endregion}

調用實例

static void Main(string[] args){    LinkList<string> link = new LinkList<string>();    link.Append("A");    link.Append("B");    link.Append("C");    link.Append("D");    link.Append("E");    link.Insert("Head", 1);    Console.WriteLine("單鏈表內容：");    link.Dispaly();    link.Delete(5);    Console.Write