C#實現鏈表

鏈表：鏈表是用一組任意的存儲單元來存儲線性表中的數據元素。為此，在存儲數據元素時，除了存儲數據元素本身的信息外，還要存儲與它相鄰的數據元素的存儲地址信息。這兩部分信息組成該數據元素的存儲映像，稱為結點(Node)。把存儲據元素本身信息的域叫結點的數據域，把存儲與它相鄰的數據元素的存儲地址信息的域叫結點的引用域。

節點類:

using System;
using System.Collections.Generic;
using System.Text;
namespace DateStructrues.Lists.Node
{
　　/// <summary>
　　/// 節點類。
　　/// </summary>
　　/// <typeparam name="T"></typeparam>
　　public class DNode<T>
　　{
　　　　#region Fields
　　　　//
　　　　//數據域
　　　　//
　　　　T _data;
　　　　//
　　　　//地址域(下一個)
　　　　//
　　　　DNode<T> _next;
　　　　//
　　　　//地址域(上一個)
　　　　//
　　　　DNode<T> _prev;
　　　　#endregion
　　　　#region Constructor
　　　　/// <summary>
　　　　/// 構造器
　　　　/// </summary>
　　　　/// <param name="value"></param>
　　　　public DNode(T value)
　　　　{
　　　　　　_data = value;
　　　　}
　　　　/// <summary>
　　　　/// 構造器
　　　　/// </summary>
　　　　/// <param name="value"></param>
　　　　/// <param name="prev"></param>
　　　　/// <param name="next"></param>
　　　　public DNode(T value, DNode<T> prev, DNode<T> next)
　　　　{
　　　　　　_data = value;
　　　　　　_prev = prev;
　　　　　　_next = next;
　　　　}
　　　　/// <summary>
　　　　/// 構造器
　　　　/// </summary>
　　　　public DNode() { }
　　　　#endregion
　　　　#region Properties
　　　　/// <summary>
　　　　/// 地址域屬性（上一個）。
　　　　/// </summary>
　　　　public DNode<T> Prev
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　return _prev;
　　　　　　}
　　　　　　set
　　　　　　{
　　　　　　　　_prev = value;
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 地址域屬性(下一個)。
　　　　/// </summary>
　　　　public DNode<T> Next
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　return _next;
　　　　　　}
　　　　　　set
　　　　　　{
　　　　　　　　_next = value;
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 數據域屬性。
　　　　/// </summary>
　　　　public T Data
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　return _data;
　　　　　　}
　　　　　　set
　　　　　　{
　　　　　　　　_data = value;
　　　　　　}
　　　　}
　　　　#endregion
　　}
}

鏈表：

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace DateStructrues.Lists.Node
{
　　/// <summary>
　　/// 鏈表
　　/// </summary>
　　/// <typeparam name="T">數據類型</typeparam>
　　public class LinkList<T> : IList<T>
　　{
　　　　#region Fields
　　　　//
　　　　// 頭節點
　　　　//
　　　　Node<T> head;
　　　　//
　　　　// 尾節點
　　　　//
　　　　Node<T> rear;
　　　　//
　　　　// 記錄節點的個數
　　　　//
　　　　int count;
　　　　#endregion
　　　　#region Methods
　　　　/// <summary>
　　　　/// 通過遍歷，求鏈表的長度。
　　　　/// </summary>
　　　　/// <returns>長度</returns>
　　　　public int GetCount()
　　　　{
　　　　　　int count = 0;
　　　　　　Node<T> p = head;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　count++;
　　　　　　　　p = p.Next;
　　　　　　}
　　　　　　return count;
　　　　}
　　　　/// <summary>
　　　　/// 獲得節點。
　　　　/// </summary>
　　　　/// <param name="index">索引</param>
　　　　/// <returns>對應的節點</returns>
　　　　public Node<T> GetNodeByIndex(int index)
　　　　{
　　　　　　if (index < 0)
　　　　　　{
　　　　　　　　return null;
　　　　　　}
　　　　　　Node<T> p = head;
　　　　　　int count = 0;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　if (index == count)
　　　　　　　　{
　　　　　　　　　　return p;
　　　　　　　　}
　　　　　　　　count++;
　　　　　　　　p = p.Next;
　　　　　　}
　　　　　　return null;
　　　　}
　　　　/// <summary>
　　　　/// 復制
　　　　/// </summary>
　　　　/// <returns></returns>
　　　　public LinkList<T> Copy()
　　　　{
　　　　　　LinkList<T> tmp = new LinkList<T>();
　　　　　　tmp.head = new Node<T>(head.Data);
　　　　　　Node<T> p1 = tmp.head;
　　　　　　Node<T> p2 = head.Next;
　　　　　　while (p2 != null)
　　　　　　{
　　　　　　　　Node<T> tmpNode = new Node<T>(p2.Data);
　　　　　　　　p1.Next = tmpNode;
　　　　　　　　p1 = p1.Next;
　　　　　　　　p2 = p2.Next;
　　　　　　}
　　　　　　return tmp;
　　　　}
　　　　/// <summary>
　　　　/// 倒序
　　　　/// </summary>
　　　　public void Revers()
　　　　{
　　　　　　Node<T> p = head.Next;
　　　　　　Node<T> q = new Node<T>();
　　　　　　head.Next = null;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　q = p;
　　　　　　　　p = p.Next;
　　　　　　　　q.Next = head.Next;
　　　　　　　　head.Next = q;
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 合並
　　　　/// </summary>
　　　　/// <param name="Ha"></param>
　　　　/// <param name="Hb"></param>
　　　　/// <returns></returns>
　　　　public static LinkList<int> Merge(LinkList<int> Ha, LinkList<int> Hb)
　　　　{
　　　　　　LinkList<int> Hc = new LinkList<int>();
　　　　　　Node<int> p = Ha.head;
　　　　　　Node<int> q = Hb.head;
　　　　　　Node<int> s = new Node<int>();
　　　　　　Hc = Ha;
　　　　　　Hc.head = null;
　　　　　　while (p != null && q != null)
　　　　　　{
　　　　　　　　if (p.Data < q.Data)
　　　　　　　　{
　　　　　　　　　　s = p;
　　　　　　　　　　p = p.Next;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　s = q;
　　　　　　　　　　q = q.Next;
　　　　　　　　}
　　　　　　　　Hc.Add(s.Data);
　　　　　　}
　　　　　　if (p == null)
　　　　　　{
　　　　　　　　p = q;
　　　　　　}
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　s = p;
　　　　　　　　p = p.Next;
　　　　　　　　Hc.Add(s.Data);
　　　　　　}
　　　　　　return Hc;
　　　　}
　　　　/// <summary>
　　　　/// 合並,由於同上一個合並方法簽名相同,即不能重載
　　　　/// </summary>
　　　　/// <param name="Ha"></param>
　　　　/// <param name="Hb"></param>
　　　　/// <returns></returns>
　　　　public static LinkList<int> Merge2(LinkList<int> Ha, LinkList<int> Hb)
　　　　{
　　　　　　LinkList<int> Hc = new LinkList<int>();
　　　　　　Node<int> p = Ha.head;
　　　　　　Node<int> q = Hb.head;
　　　　　　Node<int> s = new Node<int>();
　　　　　　Hc = Ha;
　　　　　　Hc.head = null;
　　　　　　//兩個表非空
　　　　　　while (p != null && q != null)
　　　　　　{
　　　　　　　　if (p.Data < q.Data)
　　　　　　　　{
　　　　　　　　　　s = p;
　　　　　　　　　　p = p.Next;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　s = q;
　　　　　　　　　　q = q.Next;
　　　　　　　　}
　　　　　　　　s.Next = Hc.head;
　　　　　　　　Hc.head = s;
　　　　　　}
　　　　　　//第2個表非空而第1個表為空
　　　　　　if (p == null)
　　　　　　{
　　　　　　　　p = q;
　　　　　　}
　　　　　　//將兩表中的剩余數據元素附加到新表的末尾
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　s = p;
　　　　　　　　p = p.Next;
　　　　　　　　s.Next = Hc.head;
　　　　　　　　Hc.head = s;
　　　　　　}
　　　　　　return Hc;
　　　　}
　　　　/// <summary>
　　　　/// 取消
　　　　/// </summary>
　　　　/// <param name="Ha"></param>
　　　　/// <returns></returns>
　　　　public static LinkList<int> Purge(LinkList<int> Ha)
　　　　{
　　　　　　LinkList<int> Hb = new LinkList<int>();
　　　　　　Node<int> p = Ha.head;
　　　　　　Node<int> q = new Node<int>();
　　　　　　Node<int> s = new Node<int>();
　　　　　　s = p;
　　　　　　p = p.Next;
　　　　　　s.Next = null;
　　　　　　Hb.head = s;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　s = p;
　　　　　　　　p = p.Next;
　　　　　　　　q = Hb.head;
　　　　　　　　while (q != null && q.Data != s.Data)
　　　　　　　　{
　　　　　　　　　　q = q.Next;
　　　　　　　　}
　　　　　　　　if (q == null)
　　　　　　　　{
　　　　　　　　　　s.Next = Hb.head;
　　　　　　　　　　Hb.head = s;
　　　　　　　　}
　　　　　　}
　　　　　　return Hb;
　　　　}
　　　　#endregion
　　　　#region Properties
　　　　/// <summary>
　　　　/// 數組模式，主要用於調試時查看。
　　　　/// </summary>
　　　　public T[] ArrayMode
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　T[] arr = new T[Count];
　　　　　　　　Node<T> p = head;
　　　　　　　　int count = 0;
　　　　　　　　while (p != null)
　　　　　　　　{
　　　　　　　　　　arr[count] = p.Data;
　　　　　　　　　　p = p.Next;
　　　　　　　　　　count++;
　　　　　　　　}
　　　　　　　　return arr;
　　　　　　}
　　　　}
　　　　#endregion
　　　　#region IList<T> 成員
　　　　/// <summary>
　　　　/// 求元素所在的索引。
　　　　/// </summary>
　　　　/// <param name="item">要查找的元素</param>
　　　　/// <returns>所在索引</returns>
　　　　public int IndexOf(T item)
　　　　{
　　　　　　// 用於遍歷鏈表
　　　　　　Node<T> p = head;
　　　　　　// 計數器
　　　　　　int count = 0;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　if (p.Data.Equals(item))
　　　　　　　　{
　　　　　　　　　　return count;
　　　　　　　　}
　　　　　　　　count++;
　　　　　　　　// 移到下一個節點
　　　　　　　　p = p.Next;
　　　　　　}
　　　　　　return -1;
　　　　}
　　　　/// <summary>
　　　　/// 插入元素。
　　　　/// </summary>
　　　　/// <param name="index">索引</param>
　　　　/// <param name="item">要插入的項</param>
　　　　public void Insert(int index, T item)
　　　　{
　　　　　　int count = 1;
　　　　　　Node<T> p = head;
　　　　　　Node<T> v = new Node<T>(item);
　　　　　　if (index == 0)
　　　　　　{
　　　　　　　　if (head == null)
　　　　　　　　{
　　　　　　　　　　rear = v;
　　　　　　　　}
　　　　　　　　v.Next = head;
　　　　　　　　head = v;
　　　　　　　　this.count++;
　　　　　　　　return;
　　　　　　}
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　if (count == index)
　　　　　　　　{
　　　　　　　　　　if (p.Next == null)
　　　　　　　　　　　　rear = v;
　　　　　　　　　　v.Next = p.Next;
　　　　　　　　　　p.Next = v;
　　　　　　　　　　this.count++;
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　p = p.Next;
　　　　　　　　count++;
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 以索引方式刪除元素
　　　　/// </summary>
　　　　/// <param name="index">索引</param>
　　　　public void RemoveAt(int index)
　　　　{
　　　　　　int count = 0;
　　　　　　if (index == 0)
　　　　　　{
　　　　　　　　head = head.Next;
　　　　　　　　this.count--;
　　　　　　　　return;
　　　　　　}
　　　　　　Node<T> p = head;
　　　　　　Node<T> prev = head;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　if (count == index)
　　　　　　　　{
　　　　　　　　　　prev.Next = p.Next;
　　　　　　　　　　this.count--;
　　　　　　　　　　if (p.Next == null)
　　　　　　　　　　{
　　　　　　　　　　　　rear = prev;
　　　　　　　　　　}
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　prev = p;
　　　　　　　　p = p.Next;
　　　　　　　　count++;
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 以索引方式訪問
　　　　/// </summary>
　　　　/// <param name="index">索引</param>
　　　　/// <returns>對應的元素</returns>
　　　　public T this[int index]
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　try
　　　　　　　　{
　　　　　　　　　　Node<T> p = GetNodeByIndex(index);
　　　　　　　　　　return p.Data;
　　　　　　　　}
　　　　　　　　catch (NullReferenceException)
　　　　　　　　{
　　　　　　　　　　throw new IndexOutOfRangeException("索引超出數組界限。");
　　　　　　　　}
　　　　　　}
　　　　　　set
　　　　　　{
　　　　　　　　try
　　　　　　　　{
　　　　　　　　　　Node<T> p = GetNodeByIndex(index);
　　　　　　　　　　p.Data = value;
　　　　　　　　}
　　　　　　　　catch (NullReferenceException)
　　　　　　　　{
　　　　　　　　　　throw new IndexOutOfRangeException("索引超出數組界限。");
　　　　　　　　}
　　　　　　}
　　　　}
　　　　#endregion
　　　　#region ICollection<T> 成員
　　　　/// <summary>
　　　　/// 向鏈表末尾，追加元素
　　　　/// </summary>
　　　　/// <param name="item">要追加的元素</param>
　　　　public void Add(T item)
　　　　{
　　　　　　Node<T> p = new Node<T>(item);
　　　　　　if (head == null)
　　　　　　{
　　　　　　　　head = p;
　　　　　　　　// 將這個節點設為末尾。
　　　　　　　　rear = p;
　　　　　　　　this.count = 1;
　　　　　　　　return;
　　　　　　}
　　　　　　rear.Next = p;
　　　　　　rear = p;
　　　　　　count++;
　　　　}
　　　　/// <summary>
　　　　/// 清空
　　　　/// </summary>
　　　　public void Clear()
　　　　{
　　　　　　head = null;
　　　　　　rear = null;
　　　　}
　　　　/// <summary>
　　　　/// 是否包含元素
　　　　/// </summary>
　　　　/// <param name="item">檢查是否包含的元素</param>
　　　　/// <returns>是否存在</returns>
　　　　public bool Contains(T item)
　　　　{
　　　　　　int index = IndexOf(item);
　　　　　　return (index != -1);
　　　　}
　　　　/// <summary>
　　　　/// 將數據拷貝到數組
　　　　/// </summary>
　　　　/// <param name="array">准備的數組</param>
　　　　/// <param name="arrayIndex">開始的索引</param>
　　　　public void CopyTo(T[] array, int arrayIndex)
　　　　{
　　　　　　ArrayMode.CopyTo(array, arrayIndex);
　　　　}
　　　　/// <summary>
　　　　/// 獲得此鏈表的元素個數
　　　　/// </summary>
　　　　public int Count
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　return GetCount();
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 獲得是否是只讀。
　　　　/// </summary>
　　　　public bool IsReadOnly
　　　　{
　　　　　　get
　　　　　　{
　　　　　　　　return false;
　　　　　　}
　　　　}
　　　　/// <summary>
　　　　/// 刪除元素
　　　　/// </summary>
　　　　/// <param name="item">將要被刪除的元素</param>
　　　　/// <returns>是否成功刪除</returns>
　　　　public bool Remove(T item)
　　　　{
　　　　　　Node<T> prev = null;
　　　　　　Node<T> p = head;
　　　　　　while (p != null)
　　　　　　{
　　　　　　　　if (p.Data.Equals(item))
　　　　　　　　{
　　　　　　　　　　if (prev != null)
　　　　　　　　　　　　prev.Next = p.Next;
　　　　　　　　　　else
　　　　　　　　　　　　head = head.Next;
　　　　　　　　　　this.count--;
　　　　　　　　　　return true;
　　　　　　　　}
　　　　　　　　prev = p;
　　　　　　　　p = p.Next;
　　　　　　}
　　　　　　return false;
　　　　}
　　　　#endregion
　　　　#region IEnumerable<T> 成員
　　　　public IEnumerator<T> GetEnumerator()
　　　　{
　　　　　　throw new Exception("The method or operation is not implemented.");
　　　　}
　　　　#endregion
　　　　#region IEnumerable 成員
　　　　IEnumerator IEnumerable.GetEnumerator()
　　　　{
　　　　　　throw new Exception("The method or operation is not implemented.");
　　　　}
　　　　#endregion
　　}
}