C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)實(shí)例詳解
更新時(shí)間：2015年11月27日 14:22:52 作者：Jimmy.Yang
這篇文章主要介紹了C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList),結(jié)合實(shí)例形式較為詳細(xì)的講解了雙向鏈表的概念及C#實(shí)現(xiàn)雙向鏈表的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
本文實(shí)例講述了C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)。分享給大家供大家參考，具體如下：
這是繼上一篇《C#數(shù)據(jù)結(jié)構(gòu)之單鏈表(LinkList)實(shí)例詳解》的繼續(xù)，對(duì)于雙向鏈接，節(jié)點(diǎn)上除了Next屬性外，還要有Prev屬性用來(lái)指向前一個(gè)節(jié)點(diǎn)，DbNode定義如下：
namespace 線性表
{
public class DbNode<T>
{
private T data;
private DbNode<T> prev;
private DbNode<T> next;
public DbNode(T data, DbNode<T> next,DbNode<T> prev)
{
this.data = data;
this.next = next;
this.prev = prev;
}
public DbNode(T data, DbNode<T> next)
{
this.data = data;
this.next = next;
this.prev = null;
}
public DbNode(DbNode<T> next)
{
this.data = default(T);
this.next = next;
this.prev = null;
}
public DbNode(T data)
{
this.data = data;
this.next = null;
this.prev = null;
}
public DbNode()
{
data = default(T);
next = null;
prev = null;
}
public T Data
{
set { this.data = value; }
get { return this.data; }
}
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
}
}
雙鏈表的插入操作要稍微復(fù)雜一點(diǎn)，示意圖如下：
同樣對(duì)于刪除操作，也要額外處理prev指向
完整實(shí)現(xiàn)DbLinkList<T>：
using System;
using System.Text;
namespace 線性表
{
public class DbLinkList<T> : IListDS<T>
{
private DbNode<T> head;
public DbNode<T> Head
{
get { return head; }
set { head = value; }
}
public DbLinkList()
{
head = null;
}
/// <summary>
/// 類索引器
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return this.GetItemAt(index);
}
}
/// <summary>
/// 返回單鏈表的長(zhǎng)度
/// </summary>
/// <returns></returns>
public int Count()
{
DbNode<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)
{
DbNode<T> d = new DbNode<T>(item);
DbNode<T> n = new DbNode<T>();
if (head == null)
{
head = d;
return;
}
n = head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = d;
d.Prev = n;
}
//前插
public void InsertBefore(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//在最開頭插入
if (i == 0)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head;//把"頭"改成第二個(gè)元素
head.Prev = q;
head = q;//把自己設(shè)置為"頭"
return;
}
DbNode<T> n = head;
DbNode<T> d = new DbNode<T>();
int j = 0;
//找到位置i的前一個(gè)元素d
while (n.Next != null && j < i)
{
d = n;
n = n.Next;
j++;
}
if (n.Next == null) //說(shuō)明是在最后節(jié)點(diǎn)插入(即追加)
{
DbNode<T> q = new DbNode<T>(item);
n.Next = q;
q.Prev = n;
q.Next = null;
}
else
{
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
d.Next = q;
q.Prev = d;
q.Next = n;
n.Prev = q;
}
}
}
/// <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)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head.Next;
head.Next.Prev = q;
head.Next = q;
q.Prev = head;
return;
}
DbNode<T> p = head;
int j = 0;
while (p != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = p.Next;
if (p.Next != null)
{
p.Next.Prev = q;
}
p.Next = q;
q.Prev = p;
}
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);
}
DbNode<T> q = new DbNode<T>();
if (i == 0)
{
q = head;
head = head.Next;
head.Prev = null;
return q.Data;
}
DbNode<T> p = head;
int j = 0;
while (p.Next != null && j < i)
{
j++;
q = p;
p = p.Next;
}
if (j == i)
{
p.Next.Prev = q;
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);
}
DbNode<T> p = new DbNode<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;
}
DbNode<T> p = new DbNode<T>();
p = head;
int i = 0;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
i++;
}
return i;
}
/// <summary>
/// 元素反轉(zhuǎn)
/// </summary>
public void Reverse()
{
DbLinkList<T> result = new DbLinkList<T>();
DbNode<T> t = this.head;
result.Head = new DbNode<T>(t.Data);
t = t.Next;
//(把當(dāng)前鏈接的元素從head開始遍歷，逐個(gè)插入到另一個(gè)空鏈表中，這樣得到的新鏈表正好元素順序跟原鏈表是相反的)
while (t!=null)
{
result.InsertBefore(t.Data, 0);
t = t.Next;
}
this.head = result.head;//將原鏈表直接掛到"反轉(zhuǎn)后的鏈表"上
result = null;//顯式清空原鏈表的引用，以便讓GC能直接回收
}
//得到某個(gè)指定的節(jié)點(diǎn)(為了下面測(cè)試從后向前遍歷)
private DbNode<T> GetNodeAt(int i){
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return null;
}
DbNode<T> p = new DbNode<T>();
p = head;
if (i == 0)
{
return p;
}
int j = 0;
while (p.Next != null && j < i)
{
j++;
p = p.Next;
}
if (j == i)
{
return p;
}
else
{
Console.WriteLine("The node is not exist!");
return null;
}
}
/// <summary>
/// 測(cè)試用prev屬性從后面開始遍歷
/// </summary>
/// <returns></returns>
public string TestPrevErgodic()
{
DbNode<T> tail = GetNodeAt(Count() - 1);
StringBuilder sb = new StringBuilder();
sb.Append(tail.Data.ToString() + ",");
while (tail.Prev != null)
{
sb.Append(tail.Prev.Data.ToString() + ",");
tail = tail.Prev;
}
return sb.ToString().TrimEnd(',');
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
DbNode<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(',');
}
}
}
測(cè)試代碼片段：
Console.WriteLine("-------------------------------------");
Console.WriteLine("雙鏈表測(cè)試開始...");
DbLinkList<string> dblink = new DbLinkList<string>();
dblink.Head = new DbNode<string>("x");
dblink.InsertBefore("w", 0);
dblink.InsertBefore("v", 0);
dblink.Append("y");
dblink.InsertBefore("z", dblink.Count());
Console.WriteLine(dblink.Count());//5
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink[1]);//w
Console.WriteLine(dblink[0]);//v
Console.WriteLine(dblink[4]);//z
Console.WriteLine(dblink.IndexOf("z"));//4
Console.WriteLine(dblink.RemoveAt(2));//x
Console.WriteLine(dblink.ToString());//v,w,y,z
dblink.InsertBefore("x", 2);
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink.GetItemAt(2));//x
dblink.Reverse();
Console.WriteLine(dblink.ToString());//z,y,x,w,v
dblink.InsertAfter("1", 0);
dblink.InsertAfter("2", 1);
dblink.InsertAfter("6", 5);
dblink.InsertAfter("8", 7);
dblink.InsertAfter("A", 10);//Position is error!
Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8
string _tail = dblink.GetItemAt(dblink.Count()-1);
Console.WriteLine(_tail);
Console.WriteLine(dblink.TestPrevErgodic());//8
Console.ReadKey(); //8,v,6,w,x,y,2,1,z
當(dāng)然從上面的測(cè)試代碼中，似乎并不能看出雙鏈表的優(yōu)點(diǎn)，雙鏈表的好處在于，如果需要在鏈表中，需要通過(guò)某個(gè)節(jié)點(diǎn)得到它的前驅(qū)節(jié)點(diǎn)時(shí)，雙鏈表直接用prev屬性就能找到；而單鏈表要做到這一點(diǎn)，必須再次從Head節(jié)點(diǎn)開始一個(gè)一個(gè)用Next向下找，這樣時(shí)間復(fù)雜度從O(n)降到O(1)，顯然更有效率。
注：如果把雙鏈表再做一下改造，讓頭尾接起來(lái)，即Head的Prev屬性指向最后一個(gè)節(jié)點(diǎn)(就叫做Tail吧)，同時(shí)把Tail節(jié)點(diǎn)的Next屬性指向Head節(jié)點(diǎn)，就形成了所謂的“循環(huán)雙向鏈表”
當(dāng)然，這樣的結(jié)構(gòu)可以在鏈表中再增加一個(gè)Tail節(jié)點(diǎn)屬性，在做元素插入或刪除時(shí)，可以循環(huán)到底以更新尾節(jié)點(diǎn)Tail(當(dāng)然這樣會(huì)給插入/刪除元素帶來(lái)一些額外的開銷)，但是卻可以給GetItemAt(int i)方法帶來(lái)優(yōu)化的空間，比如要查找的元素在前半段時(shí)，可以從Head開始用next向后找；反之，如果要找的元素在后半段，則可以從Tail節(jié)點(diǎn)用prev屬性向前找。
注：.Net中微軟已經(jīng)給出了一個(gè)內(nèi)置的雙向鏈表System.Collections.Generic.LinkedList<T>，在了解雙鏈表的原理后，建議大家直接系統(tǒng)內(nèi)置的鏈表。
希望本文所述對(duì)大家C#程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:
- C#中WPF ListView綁定數(shù)據(jù)的實(shí)例詳解
- C#如何將Access中以時(shí)間段條件查詢的數(shù)據(jù)添加到ListView中
- C#使用checkedListBox1控件鏈接數(shù)據(jù)庫(kù)的方法示例
- C# ListView 點(diǎn)擊表頭對(duì)數(shù)據(jù)進(jìn)行排序功能的實(shí)現(xiàn)代碼
- C#中數(shù)組、ArrayList、List、Dictionary的用法與區(qū)別淺析(存取數(shù)據(jù))
- C#實(shí)現(xiàn)導(dǎo)出List數(shù)據(jù)到xml文件的方法【附demo源碼下載】
- C#使用DropDownList綁定添加新數(shù)據(jù)的方法匯總
- C#數(shù)據(jù)結(jié)構(gòu)之單鏈表(LinkList)實(shí)例詳解
- C#數(shù)據(jù)結(jié)構(gòu)之順序表(SeqList)實(shí)例詳解
- C#實(shí)現(xiàn)讀取DataSet數(shù)據(jù)并顯示在ListView控件中的方法
- C# 多線程處理List數(shù)據(jù)的示例代碼
相關(guān)文章
C#序列化與反序列化集合對(duì)象并進(jìn)行版本控制
這篇文章介紹了C#序列化與反序列化集合對(duì)象并實(shí)現(xiàn)版本控制的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-09-09
淺析c#范型中的特殊關(guān)鍵字where & default
以下是對(duì)c#范型中的特殊關(guān)鍵字where和default進(jìn)行了詳細(xì)的介紹，需要的朋友可以過(guò)來(lái)參考下2013-09-09
本文詳細(xì)講解了C#中參數(shù)的傳遞方式，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
在.NET應(yīng)用中，導(dǎo)出Excel是很常見的需求，導(dǎo)出Excel報(bào)表大致有以下三種方式：Office PIA，文件流和NPOI開源庫(kù)，本文只介紹前兩種方式2013-12-12
該例子使用 BinaryStream 和 BinaryWriter 對(duì)二進(jìn)制文件進(jìn)行讀寫操作先上代碼再根據(jù)我理解的所分享給各位朋友2013-04-04
C#中38個(gè)常用運(yùn)算符的優(yōu)先級(jí)的劃分和理解
這只我自己在學(xué)C#中的一些總結(jié)，其中對(duì)于各級(jí)的劃分方式、各操作符的優(yōu)先級(jí)的理解并不見得正確，只是自己的看法，拿出來(lái)與大家分享2012-08-08
C#實(shí)現(xiàn)將網(wǎng)址生成二維碼圖片方法介紹
這篇文章介紹了C#實(shí)現(xiàn)將網(wǎng)址生成二維碼圖片的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-04-04
C#中把FastReport.Net報(bào)表控件的數(shù)據(jù)保存到數(shù)據(jù)庫(kù)
這篇文章介紹了在數(shù)據(jù)庫(kù)中保存FastReport.Net報(bào)表的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
C#中驗(yàn)證sql語(yǔ)句是否正確(不執(zhí)行語(yǔ)句)
C#中驗(yàn)證sql語(yǔ)句是否正確(不執(zhí)行語(yǔ)句)，需要的朋友可以參考一下2013-03-03
這篇文章介紹了C#對(duì)文件名智能排序的算法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06