這里我們來看下“單鏈表(LinkList)”。在上一篇《C#數(shù)據(jù)結(jié)構(gòu)之順序表(SeqList)實(shí)例詳解》的最后，我們指出了：順序表要求開辟一組連續(xù)的內(nèi)存空間，而且插入/刪除元素時，為了保證元素的順序性，必須對后面的元素進(jìn)行移動。如果你的應(yīng)用中需要頻繁對元素進(jìn)行插入/刪除，那么開銷會很大。

而鏈表結(jié)構(gòu)正好相反，先來看下結(jié)構(gòu)：

每個元素至少具有二個屬性：data和next。data用來存放數(shù)據(jù)，而next用來指出它后面的元素是誰(有點(diǎn)“指針”的意思)。

鏈表中的元素，通常也稱為節(jié)點(diǎn)Node，下面是泛型版本的Node.cs

namespace 線性表
{
  public class Node<T>
  {
    private T data;
    private Node<T> next;
    public Node(T val, Node<T> p) 
    {
      data = val;
      next = p;
    }
    public Node(Node<T> p) 
    {
      next = p;
    }
    public Node(T val) 
    {
      data = val;
      next = null;
    }
    public Node() 
    {
      data = default(T);
      next = null;
    }
    public T Data 
    {
      get { return data; }
      set { data = value; }
    }
    public Node<T> Next 
    {
      get { return next; }
      set { next = value; }
    }
  }
}

鏈表在存儲上并不要求所有元素按順序存儲，因?yàn)橛霉?jié)點(diǎn)的next就能找到下一個節(jié)點(diǎn)，這好象一根“用珠子串成的鏈子”，要找到其中的某一顆珠子，只要從第一顆節(jié)點(diǎn)(通常稱為Head節(jié)點(diǎn))開始，不斷根據(jù)next指向找到下一個，直到找到需要的節(jié)點(diǎn)為止。

鏈表中需要有一個Head節(jié)點(diǎn)做為開始，這跟順序表有所不同，下面是單鏈表的實(shí)現(xiàn):

using System;
using System.Text;
namespace 線性表
{
  public class LinkList<T> : IListDS<T>
  {
    private Node<T> head;
    public Node<T> Head
    {
      get { return head; }
      set { head = value; }
    }
    public LinkList()
    {
      head = null;
    }
    /// <summary>
    /// 類索引器
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T this[int index] 
    {
      get
      {
        return this.GetItemAt(index);
      }
    }
    /// <summary>
    /// 返回單鏈表的長度
    /// </summary>
    /// <returns></returns>
    public int Count()
    {
      Node<T> p = head;
      int len = 0;
      while (p != null)
      {
        len++;
        p = p.Next;
      }
      return len;
    }
    /// <summary>
    /// 清空
    /// </summary>
    public void Clear()
    {
      head = null;
    }
    /// <summary>
    /// 是否為空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
      return head == null;
    }
    /// <summary>
    /// 在最后附加元素
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
      Node<T> d = new Node<T>(item);
      Node<T> n = new Node<T>();
      if (head == null)
      {
        head = d;
        return;
      }
      n = head;
      while (n.Next != null)
      {
        n = n.Next;
      }
      n.Next = d;
    }
    //前插
    public void InsertBefore(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      //在最開頭插入
      if (i == 0)
      {
        Node<T> q = new Node<T>(item);
        q.Next = Head;//把"頭"改成第二個元素
        head = q;//把自己設(shè)置為"頭"
        return;
      }
      Node<T> n = head;
      Node<T> d = new Node<T>();
      int j = 0;
      //找到位置i的前一個元素d
      while (n.Next != null && j < i)
      {
        d = n;
        n = n.Next;
        j++;
      }
      if (n.Next == null) //說明是在最后節(jié)點(diǎn)插入(即追加)
      {
        Node<T> q = new Node<T>(item);
        n.Next = q;
        q.Next = null;
      }
      else
      {
        if (j == i)
        {
          Node<T> q = new Node<T>(item);
          d.Next = q;
          q.Next = n;
        }
      }
    }
    /// <summary>
    /// 在位置i后插入元素item
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void InsertAfter(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      if (i == 0)
      {
        Node<T> q = new Node<T>(item);
        q.Next = head.Next;
        head.Next = q;
        return;
      }
      Node<T> p = head;
      int j = 0;
      while (p != null && j < i)
      {
        p = p.Next;
        j++;
      }
      if (j == i)
      {
        Node<T> q = new Node<T>(item);
        q.Next = p.Next;
        p.Next = q;
      }
      else
      {
        Console.WriteLine("Position is error!");
      }
    }
    /// <summary>
    /// 刪除位置i的元素
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T RemoveAt(int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("Link is empty or Position is error!");
        return default(T);
      }
      Node<T> q = new Node<T>();
      if (i == 0)
      {
        q = head;
        head = head.Next;
        return q.Data;
      }
      Node<T> p = head;
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        q = p;
        p = p.Next;
      }
      if (j == i)
      {
        q.Next = p.Next;
        return p.Data;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return default(T);
      }
    }
    /// <summary>
    /// 獲取指定位置的元素
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T GetItemAt(int i)
    {
      if (IsEmpty())
      {
        Console.WriteLine("List is empty!");
        return default(T);
      }
      Node<T> p = new Node<T>();
      p = head;
      if (i == 0) 
      { 
        return p.Data; 
      }
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        p = p.Next;
      }
      if (j == i)
      {
        return p.Data;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return default(T);
      }
    }
    //按元素值查找索引
    public int IndexOf(T value)
    {
      if (IsEmpty())
      {
        Console.WriteLine("List is Empty!");
        return -1;
      }
      Node<T> p = new Node<T>();
      p = head;
      int i = 0;
      while (!p.Data.Equals(value) && p.Next != null)
      {
        p = p.Next;
        i++;
      }
      return i;
    }
    /// <summary>
    /// 元素反轉(zhuǎn)
    /// </summary>
    public void Reverse()
    {
      LinkList<T> result = new LinkList<T>();
      Node<T> t = this.head;
      result.Head = new Node<T>(t.Data);
      t = t.Next;
      //(把當(dāng)前鏈接的元素從head開始遍歷，逐個插入到另一個空鏈表中，這樣得到的新鏈表正好元素順序跟原鏈表是相反的)
      while (t!=null)
      {        
        result.InsertBefore(t.Data, 0);
        t = t.Next;
      }
      this.head = result.head;//將原鏈表直接掛到"反轉(zhuǎn)后的鏈表"上
      result = null;//顯式清空原鏈表的引用，以便讓GC能直接回收
    }
    public override string ToString()
    {
      StringBuilder sb = new StringBuilder();
      Node<T> n = this.head;
      sb.Append(n.Data.ToString() + ",");
      while (n.Next != null)
      {
        sb.Append(n.Next.Data.ToString() + ",");
        n = n.Next;
      }
      return sb.ToString().TrimEnd(',');
    }
  }
}

下面是單鏈表插入和刪除的算法圖解：

可以看到：鏈表在元素插入/刪除時，無需對后面的元素進(jìn)行移動，只需要修改自身以及相鄰節(jié)點(diǎn)的next指向即可，所以插入/刪除元素的開銷要比順序表小得多。但是也應(yīng)該注意到，其它操作比如：查找元素，反轉(zhuǎn)倒置鏈表等，有可能需要遍歷整個鏈表中的所有元素。

測試代碼片斷：

Console.WriteLine("-------------------------------------");
Console.WriteLine("單鏈表測試開始...");
LinkList<string> link = new LinkList<string>();
link.Head = new Node<string>("x");
link.InsertBefore("w", 0);
link.InsertBefore("v", 0);
link.Append("y");
link.InsertBefore("z", link.Count());
Console.WriteLine(link.Count());//5
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link[1]);//w
Console.WriteLine(link[0]);//v
Console.WriteLine(link[4]);//z
Console.WriteLine(link.IndexOf("z"));//4
Console.WriteLine(link.RemoveAt(2));//x
Console.WriteLine(link.ToString());//v,w,y,z
link.InsertBefore("x", 2);
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link.GetItemAt(2));//x
link.Reverse();
Console.WriteLine(link.ToString());//z,y,x,w,v
link.InsertAfter("1", 0);
link.InsertAfter("2", 1);
link.InsertAfter("6", 5);
link.InsertAfter("8", 7);
link.InsertAfter("A", 10);//Position is error!
Console.WriteLine(link.ToString()); //z,1,2,y,x,w,6,v,8

至于具體在實(shí)際應(yīng)用中應(yīng)該選用順序表 or 鏈表，主要是看：對于元素插入/刪除的頻繁程度以及對于內(nèi)存分配的苛刻程度。如果不要求一開始就分配一組連續(xù)的內(nèi)存區(qū)域，可以根據(jù)元素的增加而自動加大內(nèi)存的使用量，或者插入/刪除的次數(shù)很多，那么建議使用鏈表，反之用順序表。

最后指出：可以給節(jié)點(diǎn)再添加一個prev元素，用于指出前一個節(jié)點(diǎn)是誰，即同時有next和prev二個指向，這種改進(jìn)后的鏈表稱為“雙向鏈表”，它有助于某些情況下減少遍歷循環(huán)的次數(shù)，本文中的這種僅有一個next指向的鏈表，稱為“單鏈表”。

希望本文所述對大家C#程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: