C#數(shù)據(jù)結構之單鏈表(LinkList)實例詳解
更新時間：2015年11月27日 12:25:28 作者：Jimmy.Yang
這篇文章主要介紹了C#數(shù)據(jù)結構之單鏈表(LinkList)實現(xiàn)方法,結合實例形式較為詳細的分析了單鏈表的原理、定義與C#具體實現(xiàn)技巧,具有一定參考借鑒價值,需要的朋友可以參考下
本文實例講述了C#數(shù)據(jù)結構之單鏈表(LinkList)實現(xiàn)方法。分享給大家供大家參考，具體如下：
這里我們來看下“單鏈表(LinkList)”。在上一篇《C#數(shù)據(jù)結構之順序表(SeqList)實例詳解》的最后，我們指出了：順序表要求開辟一組連續(xù)的內存空間，而且插入/刪除元素時，為了保證元素的順序性，必須對后面的元素進行移動。如果你的應用中需要頻繁對元素進行插入/刪除，那么開銷會很大。
而鏈表結構正好相反，先來看下結構：
每個元素至少具有二個屬性：data和next。data用來存放數(shù)據(jù)，而next用來指出它后面的元素是誰(有點“指針”的意思)。
鏈表中的元素，通常也稱為節(jié)點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; }
}
}
}
鏈表在存儲上并不要求所有元素按順序存儲，因為用節(jié)點的next就能找到下一個節(jié)點，這好象一根“用珠子串成的鏈子”，要找到其中的某一顆珠子，只要從第一顆節(jié)點(通常稱為Head節(jié)點)開始，不斷根據(jù)next指向找到下一個，直到找到需要的節(jié)點為止。
鏈表中需要有一個Head節(jié)點做為開始，這跟順序表有所不同，下面是單鏈表的實現(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;//把自己設置為"頭"
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é)點插入(即追加)
{
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(',');
}
}
}
下面是單鏈表插入和刪除的算法圖解：
可以看到：鏈表在元素插入/刪除時，無需對后面的元素進行移動，只需要修改自身以及相鄰節(jié)點的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 鏈表，主要是看：對于元素插入/刪除的頻繁程度以及對于內存分配的苛刻程度。 如果不要求一開始就分配一組連續(xù)的內存區(qū)域，可以根據(jù)元素的增加而自動加大內存的使用量，或者插入/刪除的次數(shù)很多，那么建議使用鏈表，反之用順序表。
最后指出：可以給節(jié)點再添加一個prev元素，用于指出前一個節(jié)點是誰，即同時有next和prev二個指向，這種改進后的鏈表稱為“雙向鏈表”，它有助于某些情況下減少遍歷循環(huán)的次數(shù)，本文中的這種僅有一個next指向的鏈表，稱為“單鏈表”。
希望本文所述對大家C#程序設計有所幫助。
相關文章
很多朋友向小編反饋將Qt項目升級到Qt6頻繁出錯，該如何處理呢，今天小編給大家?guī)砹藢t項目升級到Qt6吐血經驗總結，感興趣的朋友一起看看吧2021-07-07
這篇文章主要為大家詳細介紹了C#實現(xiàn)屬于自己的QQ截圖工具的相關資料，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-04-04
這篇文章主要為大家詳細介紹了unity自定義彈出框功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11
這篇文章主要介紹了c# SpinWait的相關資料,幫助大家更好的理解和學習c# 編程，感興趣的朋友可以了解下2020-10-10
這篇文章主要介紹了.NET中的IEnumerable接口深入研究,分析出了它的實現(xiàn)原理和實現(xiàn)代碼,需要的朋友可以參考下2014-07-07
C#實現(xiàn)監(jiān)聽串口數(shù)據(jù)的方法詳解
這篇文章主要為大家詳細介紹了C#實現(xiàn)監(jiān)聽串口數(shù)據(jù)的相關方法,文中的示例代碼講解詳細,具有一定的借鑒價值,有需要的小伙伴可以參考一下2024-03-03
C#使用System.Environment獲取電腦的相關屬性
這篇文章主要為大家詳細介紹了C#使用System.Environment獲取電腦的相關屬性，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-10-10
mvc C# JavaScript LigerUI oracle實現(xiàn)用戶的注冊、登陸驗證、登陸
這篇文章主要介紹了mvc C# JavaScript LigerUI oracle實現(xiàn)用戶的注冊、登陸驗證、登陸的相關資料，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-04-04
C#實現(xiàn) Server-sent Events的步驟
這篇文章主要介紹了C#實現(xiàn) Server-sent Events的步驟，幫助大家更好的理解和使用c#，感興趣的朋友可以了解下2021-01-01
本文帶領大家學習C#中protobuf-net工具的另一種使用體驗，這個工具的使用體驗屬于Code-First模式，先定義類型，并使用注解進行標記，不需要先編寫.proto文件，感興趣的朋友跟隨小編一起看看吧2021-11-11