數據結構(C#)：單鏈表

與順序表相比，鏈表有自己的特點：插入、刪除操作無需移動元素；能夠高效實現動態內存分配；但 不能按節點索引快速定位到節點；由於需要記錄指針域，系統開銷較大。

本篇介紹單鏈表的實現，使用上一篇定義的接口。

代碼：

/*
* File　　 :　 SingleLinkedList.cs
* Author　 :　 Zhenxing Zhou
* Date　　 :　 2008-12-06
* Blog　　 :　 http://www.xianfen.net/
*/
using System;
using System.Collections;
using System.Collections.Generic;

namespace Xianfen.Net.DataStructure
{
　　 // 定義節點
　　 internal class SingleLinkedListNode<T>
　　 {
　　　　 private T m_Value;
　　　　 private SingleLinkedListNode<T> m_Next;

　　　　 public T Value
　　　　 {
　　　　　　 get { return m_Value; }
　　　　　　 set { m_Value = value; }
　　　　 }

　　　　 public SingleLinkedListNode<T> Next
　　　　 {
　　　　　　 get { return m_Next; }
　　　　　　 set { m_Next = value; }
　　　　 }

　　　　 public SingleLinkedListNode()
　　　　 {
　　　　　　 m_Next = null;
　　　　 }

　　　　 public SingleLinkedListNode(T t)
　　　　　　 : this()
　　　　 {
　　　　　　 Value = t;
　　　　 }
　　 }

　　 // 實現單鏈表
　　 public class SingleLinkedList<T> : ILinearList<T>
　　 {
　　　　 private int m_Count;
　　　　 private SingleLinkedListNode<T> m_Head;

　　　　 public SingleLinkedList()
　　　　 {
　　　　　　 m_Count = 0;
　　　　　　 m_Head = new SingleLinkedListNode<T>();
　　　　 }

　　　　 public SingleLinkedList(T t)
　　　　　　 : this()
　　　　 {
　　　　　　 m_Count = 1;
　　　　　　 m_Head.Next = new SingleLinkedListNode<T>(t);
　　　　 }

　　　　 public bool IsEmpty
　　　　 {
　　　　　　 get { return m_Count == 0; }
　　　　 }

　　　　 public int Count
　　　　 {
　　　　　　 get { return m_Count; }
　　　　 }

　　　　 public void Add(T t)
　　　　 {
　　　　　　 InsertAt(t, this.Count);
　　　　 }

　　　　 public void AddHead(T t)
　　　　 {
　　　　　　 InsertAt(t, 0);
　　　　 }

　　　　 public void AddTail(T t)
　　　　 {
　　　　　　 Add(t);
　　　　 }

　　　　 public void InsertAt(T t, int pos)
　　　　 {
　　　　　　 if (pos > this.Count || pos < 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 if (m_Count == int.MaxValue)
　　　　　　 {
　　　　　　　　 throw new ArithmeticException();
　　　　　　 }

　　　　　　 SingleLinkedListNode<T> currentNode = m_Head;

　　　　　　 while (pos-- > 0)
　　　　　　 {
　　　　　　　　 currentNode = currentNode.Next;
　　　　　　 }

　　　　　　 SingleLinkedListNode<T> tempNode = new SingleLinkedListNode<T> (t);

　　　　　　 tempNode.Next = currentNode.Next;
　　　　　　 currentNode.Next = tempNode;
　　　　　　 m_Count++;
　　　　 }

　　　　 public void RemoveTail()
　　　　 {
　　　　　　 RemoveAt(this.Count - 1);
　　　　 }

　　　　 public void RemoveHead()
　　　　 {
　　　　　　 RemoveAt(0);
　　　　 }

　　　　 public void RemoveAt(int pos)
　　　　 {
　　　　　　 if (pos >= Count || pos < 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 SingleLinkedListNode<T> currentNode = m_Head;

　　　　　　 while (pos-- > 0)
　　　　　　 {
　　　　　　　　 currentNode = currentNode.Next;
　　　　　　 }

　　　　　　 currentNode.Next = currentNode.Next.Next;
　　　　　　 m_Count--;
　　　　 }

　　　　 public void RemoveAll()
　　　　 {
　　　　　　 m_Head.Next = null;
　　　　　　 m_Count = 0;
　　　　 }

　　　　 public void Clear()
　　　　 {
　　　　　　 RemoveAll();
　　　　 }

　　　　 public T GetHead()
　　　　 {
　　　　　　 return GetAt(0);
　　　　 }

　　　　 public T GetTail()
　　　　 {
　　　　　　 return GetAt(this.Count - 1);
　　　　 }

　　　　 public T GetAt(int pos)
　　　　 {
　　　　　　 return GetNodeAt(pos).Value;
　　　　 }

　　　　 private SingleLinkedListNode<T> GetNodeAt(int pos)
　　　　 {
　　　　　　 if (pos >= Count || pos < 0)
　　　　　　 {
　　　　　　　　 throw new IndexOutOfRangeException("pos");
　　　　　　 }

　　　　　　 SingleLinkedListNode<T> currentNode = m_Head;

　　　　　　 while (pos-- > 0)
　　　　　　 {
　　　　　　　　 currentNode = currentNode.Next;
　　　　　　 }

　　　　　　 return currentNode.Next;
　　　　 }

　　　　 public void SetAt(int pos, T t)
　　　　 {
　　　　　　 GetNodeAt(pos).Value = t;
　　　　 }

　　　　 public int Find(T t)
　　　　 {
　　　　　　 SingleLinkedListNode<T> node = m_Head;
　　　　　　 int pos = 0;

　　　　　　 while ((node = node.Next) != null)
　　　　　　 {
　　　　　　　　 if (node.Value.Equals(t))
　　　　　　　　 {
　　　　　　　　　　 return pos;
　　　　　　　　 }

　　　　　　　　 pos++;
　　　　　　 }

　　　　　　 return -1;
　　　　 }

　　　　 public IEnumerator<T> GetEnumerator()
　　　　 {
　　　　　　 SingleLinkedListNode<T> node = m_Head;

　　　　　　 while ((node = node.Next) != null)
　　　　　　 {
　　　　　　　　 yield return node.Value;
　　　　　　 }
　　　　 }

　　　　 IEnumerator IEnumerable.GetEnumerator()
　　　　 {
　　　　　　 return GetEnumerator();
　　　　 }
　　 }
}

如果發現BUG請留言指出，下一篇介紹雙鏈表的實現。