單鏈表與順序鏈表不同，順序鏈表在聲明時在內存中開辟一塊連續的存儲空間進行鏈表數據項的保存。所以單鏈表的項只需要保存其數據，根據數據所在的序號進行訪問直接由鏈表類控制，因為屋裡保存區域連續，所以能夠很方便實現這些數據的訪問，插入和刪除。
單鏈表在內存中不適用連續的空間存儲，所以單鏈表的項實際保存兩個信息，一個信息為該項的數據項，另
從上面的單鏈表示意圖可以看到，鏈表首項指向第二項，第二項指向第三項，最後一項不指向任何項，所以在構造單鏈表之前，我們需要首先構造單鏈表的項，這裡我們就疑問了，為什麼在順序鏈表中不需要構造鏈表項？剛才已經說了，順序鏈表只需要保存值本身即可，所以使用泛型類即可滿足需求，下面給出單鏈表項的類：
/// <summary>
/// 單向連接節點類
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
private T data; //數據域
private Node<T> next; //引用域
//構造函數
public Node(T data, Node<T> next)
{
this.data = data;
this.next = next;
}
//構造函數
public Node(T data)
{
this.data = data;
this.next = null;
}
//構造函數
public Node(Node<T> next)
{
this.next = next;
}
//構造函數
public Node()
{
this.data = default(T);
this.next = null;
}
public T Data
{
set { data = value; }
get { return data; }
}
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
鏈表項的類很簡單，聲明了兩個屬性分別為Data和Next，分別表示鏈表項的兩個存儲信息，聲明相對應的構造函數。
下面是單鏈表項的代碼：
class SinglyLink<T> : IListDS<T>
{
private Node<T> head;
public Node<T> Head
{
set { head = value; }
get { return head; }
}
/// <summary>
/// 求單鏈表長度，正確
/// </summary>
/// <returns></returns>
public int GetLength()
{
int length = 0;
Node<T> P = head;
while (P != null)
{
P = P.Next;
length++;
}
return length;
}
/// <summary>
/// 清楚單鏈表所有項
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 判斷單鏈表是否為空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
if (head == null)
return true;
else
return false;
}
/// <summary>
/// 判斷單鏈表是否已滿，因為單鏈表不存在最大長度的限制，所以單鏈表永遠不會滿
/// </summary>
/// <returns></returns>
public bool IsFull()
{
return false;
}
/// <summary>
/// 在單鏈表的最末尾添加新項，有以下幾種情況
/// 當鏈表為空時，只需要將添加項賦予鏈表頭即可
/// 當鏈表不為空時，需要先查找到鏈表的最末項，然後將最末項的末尾
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
if (head == null)
{
head = new Node<T>(item);
return;
}
Node<T> p = head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = new Node<T>(item);
}
/// <summary>
/// 在單鏈表指定的位置插入新項，當插入時，存在以下幾種情況
/// 當指定的位置超出單鏈表的最小長度和現有長度時，拋出異常
/// 當在單鏈表的起始位置插入新項時，只需要將新項的Next屬性設為現有的head
/// 當在單鏈表的末尾位置插入新項時，只需要在鏈表的最末位Append新項
/// 當在單鏈表的中間位置插入新項時，需要首先獲取插入位置的前一項，將其Next屬性設置為新項，然後將新項Next屬性設置為中間斷開的下一項
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
if (index <= 0 || index > GetLength() + 1)
throw new Exception("指定位置不在鏈表長度內");
if (index == 1)
{
if (this.IsEmpty())
{
this.head = new Node<T>(item);
return;
}
Node<T> node = this.head;
this.head = new Node<T>(item);
this.head.Next = node;
return;
}
if (index == GetLength() + 1)
{
this.Append(item);
return;
}
Node<T> tempItem = new Node<T>(item);
Node<T> tempLast = this.head;
Node<T> tempNext = default(Node<T>);
for (int i = 0; i < index - 2; i++)
{
tempLast = tempLast.Next;
}
tempNext = tempLast.Next;
tempLast.Next = tempItem;
tempItem.Next = tempNext;
}
/// <summary>
/// 刪除列表中指定順序的項，可能有以下幾種情況
/// 順序的序列號超出鏈表的范圍，拋出異常
/// 順序的序號為列表首項，只需要將第二項設置為首相即可
/// 順序的序號為列表尾箱，只需要將倒數第二項後的Next屬性設置為空
/// 順序的序號在列表中時，需要刪除該項，然後設置前項的Next屬性為下一項
/// </summary>
/// <param name="index"></param>
public void Delete(int index)
{
if (index <= 0 || index > GetLength())
throw new Exception("指定位置不在鏈表長度內");
if (index == 1)
{
this.head = head.Next;
return;
}
if (index == GetLength())
{
Node<T> node = this.head;
for (int i = 0; i < index - 2; i++)
{
node = node.Next;
}
node.Next = null;
return;
}
Node<T> tempItem = head;
Node<T> tempNext = default(Node<T>);
for (int i = 0; i < index - 2; i++)
{
tempItem = tempItem.Next;
}
tempNext = tempItem.Next;
tempNext = tempNext.Next;
tempItem.Next = tempNext;
}
/// <summary>
/// 根據用戶輸入的列表項序號獲取列表項，可能遇到以下情況
/// 當輸入序號超出列表索引范圍時，拋出異常
/// 當輸入序號為首項時，返回head
/// 當輸入序號為其他時，查找對應的項返回
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetItem(int index)
{
if (index < 0 || index > GetLength() - 1)
throw new Exception("指定位置不在鏈表長度內");
if (index == 0)
return this.head.Data;
Node<T> tempItem = head;
for (int i = 0; i < index - 1; i++)
{
tempItem = tempItem.Next;
}
return tempItem.Next.Data;
}
/// <summary>
/// 根據用戶輸入的值返回該值在鏈表的位置
/// 有兩種情況，當鏈表為空或鏈表不為空
/// 順序查找鏈表的項，當找到匹配項時，返回，不再查找後面的項是否仍有匹配
/// 當搜索完整個鏈表仍沒有找到值時，返回-1。表示沒有找到任何值
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
if (IsEmpty())
throw new Exception("鏈表為空，無法查找");
for (int i = 0; i < GetLength(); i++)
{
if (GetItem(i).Equals(value))
{
return i;
}
}
return -1;
}
}
摘自 魯信的專欄
