C#数据结构之单链表(LinkList)实例详解

本文实例讲述了c#数据结构之单链表(linklist)实现方法。分享给大家供大家参考，具体如下：

这里我们来看下“单链表(linklist)”。在上一篇《c#数据结构之顺序表(seqlist)实例详解》的最后，我们指出了：顺序表要求开辟一组连续的内存空间，而且插入/删除元素时，为了保证元素的顺序性，必须对后面的元素进行移动。如果你的应用中需要频繁对元素进行插入/删除，那么开销会很大。

而链表结构正好相反，先来看下结构：

每个元素至少具有二个属性：data和next。data用来存放数据，而next用来指出它后面的元素是谁(有点“指针”的意思)。

链表中的元素，通常也称为节点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; }
    }
  }
}

链表在存储上并不要求所有元素按顺序存储，因为用节点的next就能找到下一个节点，这好象一根“用珠子串成的链子”，要找到其中的某一颗珠子，只要从第一颗节点(通常称为head节点)开始，不断根据next指向找到下一个，直到找到需要的节点为止。

链表中需要有一个head节点做为开始，这跟顺序表有所不同，下面是单链表的实现:

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;//把自己设置为"头"
        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) //说明是在最后节点插入(即追加)
      {
        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>
    /// 元素反转
    /// </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;
      //(把当前链接的元素从head开始遍历，逐个插入到另一个空链表中，这样得到的新链表正好元素顺序跟原链表是相反的)
      while (t!=null)
      {        
        result.insertbefore(t.data, 0);
        t = t.next;
      }
      this.head = result.head;//将原链表直接挂到"反转后的链表"上
      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(',');
    }
  }
}

下面是单链表插入和删除的算法图解：

可以看到：链表在元素插入/删除时，无需对后面的元素进行移动，只需要修改自身以及相邻节点的next指向即可，所以插入/删除元素的开销要比顺序表小得多。但是也应该注意到，其它操作比如：查找元素，反转倒置链表等，有可能需要遍历整个链表中的所有元素。

测试代码片断：

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

至于具体在实际应用中应该选用顺序表 or 链表，主要是看：对于元素插入/删除的频繁程度以及对于内存分配的苛刻程度。 如果不要求一开始就分配一组连续的内存区域，可以根据元素的增加而自动加大内存的使用量，或者插入/删除的次数很多，那么建议使用链表，反之用顺序表。

最后指出：可以给节点再添加一个prev元素，用于指出前一个节点是谁，即同时有next和prev二个指向，这种改进后的链表称为“双向链表”，它有助于某些情况下减少遍历循环的次数，本文中的这种仅有一个next指向的链表，称为“单链表”。

希望本文所述对大家c#程序设计有所帮助。