網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
鏈表的由來(lái)和定義
在現(xiàn)實(shí)生活中，我們把不同的商品放在一個(gè)購(gòu)物車(chē)中。而在面向?qū)ο蟮氖澜缋铮袝r(shí)候，也需要把不同類(lèi)型的數(shù)據(jù)放到一起，組成一個(gè)集合。集合中的元素并不是彼此孤立的，在C#中，如何表達(dá)集合元素間的關(guān)系呢？
借助"自引用類(lèi)"可以確立集合元素間的關(guān)系。比如有這樣一個(gè)自引用類(lèi)：
public class Node
{
public int Data{get;set;}
public Node Next{get;set;}
public Node(int dataValue)
{}
}Node類(lèi)的最大特點(diǎn)是：存在一個(gè)Node類(lèi)型的屬性，這個(gè)屬性指向Node的另一個(gè)實(shí)例，Next屬性也稱(chēng)為"引用鏈"。放到集合的場(chǎng)景中來(lái)說(shuō)就是：把多個(gè)Node實(shí)例放到一個(gè)集合中，每一個(gè)Node實(shí)例包含一個(gè)Next屬性指向下一個(gè)Node實(shí)例。而該集合中的最后一個(gè)Node實(shí)例會(huì)指向null。用圖表示就是：
鏈表就是自引用類(lèi)對(duì)象的線性集合，即序列。
由于每個(gè)自引用對(duì)象是由引用鏈鏈接起來(lái)，所以叫鏈表。堆棧與隊(duì)列是約束版的鏈表，而二叉查找數(shù)是非線性數(shù)據(jù)結(jié)構(gòu)。
鏈表的節(jié)點(diǎn)或元素雖然在邏輯上是連續(xù)的、線性的，當(dāng)其內(nèi)存不是連續(xù)存儲(chǔ)的；數(shù)組元素在內(nèi)存中是連續(xù)的，所以我們才可以通過(guò)索引來(lái)訪問(wèn)數(shù)組元素。
創(chuàng)建一個(gè)單向鏈表
首先創(chuàng)建一個(gè)節(jié)點(diǎn)，是一個(gè)自引用類(lèi)：
namespace LinkedListLibrary
{
public class ListNode
{
//當(dāng)前節(jié)點(diǎn)對(duì)象
public object Data { get; private set; }
//Next屬性也稱(chēng)為鏈，指向另一個(gè)ListNode對(duì)象實(shí)例，這樣就把2個(gè)ListNode對(duì)象實(shí)例鏈接起來(lái)了
public ListNode Next { get; set; }
public ListNode(object dataValue): this(dataValue, null)
{
}
public ListNode(object dataValue, ListNode nextNode)
{
Data = dataValue;
Next = nextNode;
}
}
}再模擬一個(gè)鏈表，如下：
namespace LinkedListLibrary
{
public class List
{
private ListNode firstNode;
private ListNode lastNode;
private string name;
public List(string listName)
{
name = listName;
firstNode = lastNode = null;
}
public List() : this("list"){}
......
//如果第一個(gè)節(jié)點(diǎn)是null，那就說(shuō)明集合為空
public bool IsEmpty()
{
return firstNode == null;
}
}
}以上，如果第一個(gè)節(jié)點(diǎn)為null，那就說(shuō)明該鏈表為空。List類(lèi)提供了IsEmpty方法用來(lái)判斷鏈表是否為空。List還包含另外5個(gè)重要的方法，下面展開(kāi)來(lái)說(shuō)。
在鏈表的的第一個(gè)節(jié)點(diǎn)前插入。
//在最前面插入元素、節(jié)點(diǎn)
public void InsertAtFront(object insertItem)
{
if (IsEmpty())//如果集合為空，加進(jìn)來(lái)一個(gè)元素，相當(dāng)于第一個(gè)節(jié)點(diǎn)和第二個(gè)節(jié)點(diǎn)相同，都是新加的元素
{
firstNode = lastNode = new ListNode(insertItem);
}
else //如果集合不為空，第一個(gè)節(jié)點(diǎn)就是新加的元素,原先的第一個(gè)節(jié)點(diǎn)變?yōu)橄乱粋€(gè)節(jié)點(diǎn)
{
firstNode = new ListNode(insertItem, firstNode);
}
}以上，當(dāng)集合不為空的情況下，實(shí)際上是把新添加的節(jié)點(diǎn)設(shè)為第一個(gè)節(jié)點(diǎn)，并把新的第一個(gè)節(jié)點(diǎn)的引用鏈指向原先的第一個(gè)節(jié)點(diǎn)。
在鏈表的最后一個(gè)節(jié)點(diǎn)后插入。
public void InsertAtBack(object insertItem)
{
if (IsEmpty())//如果原先集合為空，第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)就是新加的節(jié)點(diǎn)
{
firstNode = lastNode = new ListNode(insertItem);
}
else//如果原先的集合不為空，最后一個(gè)節(jié)點(diǎn)的屬性值就是新加的節(jié)點(diǎn)
{
lastNode = lastNode.Next = new ListNode(insertItem);
}
}以上，當(dāng)集合不為空的情況下，實(shí)際上是把新添加的節(jié)點(diǎn)設(shè)置成最后一個(gè)節(jié)點(diǎn)，并把新的最后一個(gè)節(jié)點(diǎn)的引用鏈指向null。
移除鏈表最前面的節(jié)點(diǎn)。
//移除最前面的元素、節(jié)點(diǎn)
//即重新設(shè)置第一個(gè)節(jié)點(diǎn)的Next屬性
public object RemoveFromFront()
{
if (IsEmpty())
throw new EmptyListException(name);
//從第一個(gè)節(jié)點(diǎn)中取出節(jié)點(diǎn)對(duì)象
object removeItem = firstNode.Data;
if (firstNode == lastNode) //如果集合中只有一個(gè)元素
{
firstNode = lastNode = null;
}
else //正常情況下，把firstNode的Next屬性所指向的節(jié)點(diǎn)賦值給第一個(gè)節(jié)點(diǎn)
{
firstNode = firstNode.Next;
}
return removeItem;
}以上，本質(zhì)是把原先排在第二位置的節(jié)點(diǎn)設(shè)置成第一個(gè)節(jié)點(diǎn)。
移除鏈表最后面的節(jié)點(diǎn)。
//移除最后面的元素、節(jié)點(diǎn)
public object RemoveFromBack()
{
if (IsEmpty())
{
throw new EmptyListException();
}
//從最后一個(gè)節(jié)點(diǎn)中獲取節(jié)點(diǎn)對(duì)象
object removeItem = lastNode.Data;
if (firstNode == lastNode)//如果當(dāng)前集合只有一個(gè)節(jié)點(diǎn)
{
firstNode = lastNode = null;
}
else
{
//先把第一個(gè)節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)
ListNode current = firstNode;
//改變除最后一個(gè)節(jié)點(diǎn)之外的節(jié)點(diǎn)的值
while (current.Next != lastNode)
{
current = current.Next;
}
//最后current變成倒數(shù)第二個(gè)節(jié)點(diǎn)
lastNode = current;
current.Next = null;//最后一個(gè)節(jié)點(diǎn)的Next屬性為null，即沒(méi)有指向另一個(gè)節(jié)點(diǎn)
}
return removeItem;
}以上，從第一個(gè)節(jié)點(diǎn)開(kāi)始，一直循環(huán)到倒數(shù)第二個(gè)節(jié)點(diǎn)，current就像一個(gè)指針，每指到一個(gè)節(jié)點(diǎn)，就把該節(jié)點(diǎn)的下面一個(gè)節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)。最后，把倒數(shù)第二個(gè)節(jié)點(diǎn)設(shè)置為最后一個(gè)節(jié)點(diǎn)。 把Current的引用鏈設(shè)置為null，讓其能被垃圾回收機(jī)制回收。
打印鏈表。
//打印顯示
public void Display()
{
if (IsEmpty())
{
Console.WriteLine("集合" + name + "為空");
}
else
{
Console.WriteLine("集合的名稱(chēng)是：" + name);
//先把第一個(gè)節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)
ListNode current = firstNode;
while (current != null)
{
//把當(dāng)前節(jié)點(diǎn)對(duì)象打印出來(lái)
Console.Write(current.Data + " ");
//把下一個(gè)節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
current = current.Next;
}
Console.WriteLine("\n");
}
} 以上，從第一個(gè)節(jié)點(diǎn)開(kāi)始，一直循環(huán)到最后一個(gè)節(jié)點(diǎn)，current就像一個(gè)指針，每打印一個(gè)節(jié)點(diǎn)，就把當(dāng)前節(jié)點(diǎn)設(shè)置為下一個(gè)節(jié)點(diǎn)，一直循環(huán)下去。
EmptyListException用來(lái)拋出鏈表為空的異常。
namespace LinkedListLibrary
{
public class EmptyListException : Exception
{
public EmptyListException() : base("當(dāng)前集合為空"){}
public EmptyListException(string name) : base("集合" + name + "為空"){}
public EmptyListException(string exception, Exception inner) : base(exception, inner){}
}
}客戶端調(diào)用：
using LinkedListLibrary;
namespace ListTest
{
class Program
{
static void Main(string[] args)
{
List list = new List();
bool aBoolean = true;
char aChar = 'a';
int anInt = 12;
string aStr = "hi";
list.InsertAtFront(aBoolean);
list.Display();
list.InsertAtFront(aChar);
list.Display();
list.InsertAtBack(anInt);
list.Display();
list.InsertAtBack(aStr);
list.Display();
object removeObject;
try
{
removeObject = list.RemoveFromFront();
Console.WriteLine(removeObject + "被刪除了...");
list.Display();
removeObject = list.RemoveFromFront();
Console.WriteLine(removeObject + "被刪除了...");
list.Display();
removeObject = list.RemoveFromBack();
Console.WriteLine(removeObject + "被刪除了...");
list.Display();
removeObject = list.RemoveFromBack();
Console.WriteLine(removeObject + "被刪除了...");
list.Display();
}
catch (EmptyListException emptyListException)
{
Console.Error.WriteLine("\n" + emptyListException);
}
Console.ReadKey();
}
}
}
其它鏈表
以上，創(chuàng)建的是單向鏈表，其特點(diǎn)是第一個(gè)節(jié)點(diǎn)開(kāi)始包含引用鏈，每個(gè)節(jié)點(diǎn)的引用鏈指向下一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的引用鏈為null。單向鏈表只能從一個(gè)方向遍歷。
環(huán)形單向鏈表與單向鏈表的區(qū)別是：其最后一個(gè)節(jié)點(diǎn)的引用鏈指向第一個(gè)節(jié)點(diǎn)。環(huán)形單向鏈表也只能從一個(gè)方向遍歷，只不過(guò)遍歷到最后一個(gè)節(jié)點(diǎn)后，又回到第一個(gè)節(jié)點(diǎn)重新開(kāi)始遍歷。
雙向鏈表的第一個(gè)節(jié)點(diǎn)只包含指向下一個(gè)節(jié)點(diǎn)的引用鏈，最后一個(gè)節(jié)點(diǎn)只包含指向上一個(gè)節(jié)點(diǎn)的引用鏈，其它節(jié)點(diǎn)同時(shí)包含指向前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的引用鏈。雙向鏈表支持向前和向后遍歷。
環(huán)形雙向鏈表與雙向鏈表的區(qū)別是：第一個(gè)節(jié)點(diǎn)向后引用鏈指向最后一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)的向前引用鏈指向第一個(gè)節(jié)點(diǎn)。
原文鏈接：https://www.cnblogs.com/darrenji/p/3885635.html
相關(guān)推薦
- 2022-05-14 C++?STL中vector容器的使用_C 語(yǔ)言
- 2022-09-09 python處理xml文件操作詳解_python
- 2023-01-31 利用Rust編寫(xiě)一個(gè)簡(jiǎn)單的字符串時(shí)鐘_Rust語(yǔ)言
- 2022-02-09 深入了解C++異常處理_C 語(yǔ)言
- 2022-05-20 python?關(guān)鍵字與標(biāo)識(shí)符超詳細(xì)整理_python
- 2022-03-12 用C語(yǔ)言實(shí)現(xiàn)圣誕樹(shù)(簡(jiǎn)易版+進(jìn)階版)_C 語(yǔ)言
- 2023-10-13 ECharts日歷熱力圖點(diǎn)擊事件和選中日期加邊框
- 2023-09-12 Nginx安裝與常見(jiàn)命令
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速