目錄
前置知識:
一、鏈表中的結點類LinkedNode
1、申明字段節點類:
2、申明屬性節點類:
二、兩種方式實現單向鏈表
①定框架:
②增加元素的方法:因為是單鏈表,所以增加元素一定是只能在末尾添加元素,即在頭結點后面添加元素
③刪除元素的方法:刪除鏈表中第一個符合刪除目標值的節點?
④查找節點是否存在,這個就很簡單,直接遍歷一遍就好了。
?⑤更新某一個節點的數據
三、測試?
測試接口:
寫一個測試函數:
開始測試:
測試結果:
前置知識:
? ? ? ? 數據結構:
數據結構:數據元素之間的相互關系
常用的數據結構
數組、鏈表、棧、隊列、樹、圖,堆,散列表
?????????線性表:
線性表是一種數據結構是由n個具有相同特性的數據元素的有限序列
例如:數組、鏈表、棧、隊列,ArrayList
????????順序存儲:
數組、Stack、Queue、ArrayList->順序存儲
只是 數組、Stack、Queue、ArrayList的組織規則不同而已
順序存儲
用一組地址連續的存儲單元依次存儲線性表的各個元素,數據元素之間的邏輯關系由存儲單元的鄰接關系來體現。內存地址連續,一整片的內存
順序存儲和鏈式存儲 是數據結構中的兩種存儲方式??
????????鏈式存儲:
單向鏈表、雙向鏈表、循環鏈表->鏈式存儲
鏈式存儲(鏈接存儲)
用一組任意的存儲單元存儲線性表中的各個數據元素,內存地址不連續跳躍式的。
如需了解更多,可看這一篇文章:
線性表的相關知識
? 好的,回歸主線,今天咱們學習的重點是單向鏈表以及雙向鏈表,循環鏈表。
一、鏈表中的結點類LinkedNode
?????????什么是LinkedNode呢,他有什么作用呢?他其實就是組成鏈表的基本單位,鏈表就是一個個的LinkedNode串起來的,只不過串的方式不太一樣。下面代碼示例中不一定使用的是LinkedNode這個名字,使用的是其他的名字不過沒關系,學習而已。例如:
? ? ? ? 在單向鏈表中:每個鏈表結點有一個指向下一個鏈表結點的類似于C語言中的指針的東西,就是說明了,當前節點的下一個就是你,二者建立了聯系。對于單向鏈表中,第一個結點,我們稱之為頭結點,因為他只能向后指,不能朝前看,所以每次尋找某一個元素,需要進行遍歷,而且你永遠找不到自己的上一個元素是什么。于是有了雙向鏈表。
? ? ? ? 在雙向鏈表中:每個鏈表節點存有兩個指針,一個是指向當前結點的上一個結點,一個是指向當前結點的下一個結點,其余的和單向鏈表相同。
? ? ? ? 所謂循環鏈表:就是在單鏈表中,將最后一個結點的下一個指向第一個結點。
好的,接下來我們實現這個節點類:
? ? ?單向鏈表的節點類:
兩種定義方式:
1、申明字段節點類:
/// <summary>
/// 單向鏈表節點定義(字段版本)
/// </summary>
/// <typeparam name="T">泛型數據類型</typeparam>
public class ListNode_Field<T>
{// 節點存儲的數據(字段)public T data;// 指向下一個節點的指針(字段)// "?" 表示這是一個可空類型,允許值為 nullpublic ListNode_Field<T>? next;/// <summary>/// 構造函數/// </summary>/// <param name="val">節點數據</param>public ListNode_Field(T val){data = val;next = null;}
}
2、申明屬性節點類:
/// <summary>
/// 單向鏈表節點定義(屬性版本)
/// </summary>
/// <typeparam name="T">泛型數據類型</typeparam>
public class SingleListNode<T>
{// 節點存儲的數據(屬性)public T Data { get; set; }// 指向下一個節點的指針(屬性)// "?" 表示這是一個可空類型,允許值為 nullpublic SingleListNode<T>? Next { get; set; }/// <summary>/// 構造函數/// </summary>/// <param name="data">節點數據</param>public SingleListNode(T data){Data = data;Next = null; // 初始化時指針置空}
}
?????????這兩種方式任意選擇一種進行申明即可,推薦使用屬性,因為可以自己處理的手段更多。
二、兩種方式實現單向鏈表
????????好的接下來我們實現一個單向鏈表,因為有了這些基本節點類,所以才會有下面的代碼。同樣我們會使用屬性節點類和字段節點類進行說明。其實都差不多的。
? ? ? ? 總的設計思路:
? ? ? ? 1、提供一個頭結點
? ? ? ? 2、利用這個頭結點進行增刪改查
? ? ? ? 接下來我們一一實現:下面是一個利用字段節點聲明的單向鏈表
①定框架:
public class SingleLinkedList_Field<T>{//設置一個私有頭結點private ListNode_Field<T>? head;}
②增加元素的方法:因為是單鏈表,所以增加元素一定是只能在末尾添加元素,即在頭結點后面添加元素
? ? ? ? 步驟:
(1)先申明一個新的節點
(2)判斷頭結點是否為空,為空則添加的元素就是頭結點元素,反之遍歷找到最后一個節點,然后將最后一個結點的next指向當前新創造的節點
/// <summary>
/// 在鏈表尾部添加新節點
/// </summary>
public void Add(T data)
{ListNode_Field<T> newNode = new ListNode_Field<T>(data);if (head == null){head = newNode;return;}// 遍歷鏈表找到最后一個節點ListNode_Field<T> current = head;while (current.next != null){current = current.next;}current.next = newNode; // 直接操作字段
}
????????當然這個添加元素,你也可以想想怎么在中間插入一個元素,思想是將上一個的next指向插入元素,插入元素的next指向上一個元素的下一個?
③刪除元素的方法:刪除鏈表中第一個符合刪除目標值的節點?
? ? ? ? 步驟:
(1)先看有沒有頭結點,沒有頭結點刪除個屁啊
(2)然后看刪除的是不是頭結點,是的話直接將頭結點的next指向下一個就好啦
(3)不是頭結點的話,就稍微有一點點麻煩,需要先遍歷,和Add方法差不多的
/// <summary>
/// 刪除第一個匹配的節點
/// </summary>
public bool Remove(T data)
{if (head == null) return false;// 處理頭節點匹配的情況if (head.data != null && head.data.Equals(data)){head = head.next; // 直接操作字段return true;}ListNode_Field<T> current = head;while (current.next != null){if (current.next.data != null && current.next.data.Equals(data)){current.next = current.next.next; // 直接操作字段return true;}current = current.next;}return false;
}
④查找節點是否存在,這個就很簡單,直接遍歷一遍就好了。
/// <summary>
/// 查找節點是否存在
/// </summary>
public bool Contains(T data)
{ListNode_Field<T>? current = head;while (current != null){if (current.data != null && current.data.Equals(data)){return true;}current = current.next;}return false;
}
?⑤更新某一個節點的數據
? ? ? ? 步驟:
(1)找到該節點
(2)操作該節點的數據
/// <summary>
/// 更新第一個匹配的節點的值
/// </summary>
public bool Update(T oldData, T newData)
{ListNode_Field<T>? node = FindNode(oldData);if (node == null) return false;node.data = newData; // 直接操作字段return true;
}/// <summary>
/// 輔助方法:查找指定數據的節點
/// </summary>
private ListNode_Field<T>? FindNode(T data)
{ListNode_Field<T>? current = head;while (current != null){if (current.data != null && current.data.Equals(data)){return current;}current = current.next;}return null;
}
????????好的,那么我們就完成了一個最簡單的單向鏈表的數據結構!
附上使用屬性申明的單行鏈表,是一樣的:
/// <summary>/// 單向鏈表實現(屬性版本)/// </summary>/// <typeparam name="T">泛型數據類型</typeparam>public class SingleLinkedList_Property<T> : ISingleLinkedList<T>{// 頭節點(私有屬性)private SingleListNode<T>? head;/// <summary>/// 在鏈表尾部添加新節點/// </summary>/// <param name="data">要添加的數據</param>public void Add(T data){// 顯式聲明類型(不使用 var)SingleListNode<T> newNode = new SingleListNode<T>(data);if (head == null){head = newNode; // 鏈表為空時,新節點作為頭節點return;}// 遍歷鏈表找到最后一個節點SingleListNode<T> current = head;while (current.Next != null){current = current.Next;}current.Next = newNode; // 將新節點鏈接到尾部}/// <summary>/// 刪除第一個匹配的節點/// </summary>/// <param name="data">要刪除的數據</param>/// <returns>是否刪除成功</returns>public bool Remove(T data){if (head == null) return false;// 處理頭節點匹配的情況if (head.Data != null && head.Data.Equals(data)){head = head.Next; // 頭節點指向下一個節點return true;}// 遍歷鏈表查找匹配的節點SingleListNode<T> current = head;while (current.Next != null){if (current.Next.Data != null && current.Next.Data.Equals(data)){current.Next = current.Next.Next; // 跳過匹配的節點return true;}current = current.Next;}return false;}/// <summary>/// 查找節點是否存在/// </summary>/// <param name="data">要查找的數據</param>/// <returns>是否存在</returns>public bool Contains(T data){SingleListNode<T>? current = head;while (current != null){if (current.Data != null && current.Data.Equals(data)){return true;}current = current.Next;}return false;}/// <summary>/// 更新第一個匹配的節點的值/// </summary>/// <param name="oldData">舊數據</param>/// <param name="newData">新數據</param>/// <returns>是否更新成功</returns>public bool Update(T oldData, T newData){SingleListNode<T>? node = FindNode(oldData);if (node == null) return false;node.Data = newData; // 直接修改節點的數據return true;}/// <summary>/// 輔助方法:查找指定數據的節點/// </summary>private SingleListNode<T>? FindNode(T data){SingleListNode<T>? current = head;while (current != null){if (current.Data != null && current.Data.Equals(data)){return current;}current = current.Next;}return null;}}
三、測試?
????????測試部分呢,因為兩種都差不多,所以我們使用一個接口,讓他們都實現里面的方法,然后統一測試
測試接口:
/// <summary>
/// 統一接口(便于測試不同版本的鏈表)
/// </summary>
public interface ISingleLinkedList<T>
{void Add(T data);bool Remove(T data);bool Contains(T data);bool Update(T oldData, T newData);
}
兩個鏈表只要繼承了這個接口就好
寫一個測試函數:
static void TestLinkedList<T>(T list) where T : ISingleLinkedList<int>
{// 添加節點list.Add(1);list.Add(2);list.Add(3);Console.WriteLine("添加 1, 2, 3 后鏈表內容應為:1 -> 2 -> 3");// 測試查找Console.WriteLine("查找 2: " + list.Contains(2)); // 應輸出 TrueConsole.WriteLine("查找 4: " + list.Contains(4)); // 應輸出 False// 測試刪除list.Remove(2);Console.WriteLine("刪除 2 后鏈表內容應為:1 -> 3");Console.WriteLine("查找 2: " + list.Contains(2)); // 應輸出 False// 測試更新list.Update(3, 4);Console.WriteLine("更新 3 為 4 后鏈表內容應為:1 -> 4");Console.WriteLine("查找 4: " + list.Contains(4)); // 應輸出 True
}
開始測試:
static void Main(string[] args){// 測試屬性版本鏈表Console.WriteLine("測試屬性版本鏈表:");TestLinkedList(new SingleLinkedList_Property<int>());// 測試字段版本鏈表Console.WriteLine("\n測試字段版本鏈表:");TestLinkedList(new SingleLinkedList_Field<int>());}
測試結果:
?如果再講雙向鏈表和循環鏈表,會顯得很雜亂,我們將會在下一篇文章討論,諸位共勉!
附:本文所有代碼
namespace 單向鏈表
{/// <summary>/// 單向鏈表節點定義(屬性版本)/// </summary>/// <typeparam name="T">泛型數據類型</typeparam>public class SingleListNode<T>{// 節點存儲的數據(屬性)public T Data { get; set; }// 指向下一個節點的指針(屬性)// "?" 表示這是一個可空類型,允許值為 null(解決 CS8618 警告)public SingleListNode<T>? Next { get; set; }/// <summary>/// 構造函數/// </summary>/// <param name="data">節點數據</param>public SingleListNode(T data){Data = data;Next = null; // 初始化時指針置空}}/// <summary>/// 單向鏈表節點定義(字段版本)/// </summary>/// <typeparam name="T">泛型數據類型</typeparam>public class ListNode_Field<T>{// 節點存儲的數據(字段)public T data;// 指向下一個節點的指針(字段)// "?" 表示這是一個可空類型,允許值為 nullpublic ListNode_Field<T>? next;/// <summary>/// 構造函數/// </summary>/// <param name="val">節點數據</param>public ListNode_Field(T val){data = val;next = null;}}internal class Program{static void Main(string[] args){// 測試屬性版本鏈表Console.WriteLine("測試屬性版本鏈表:");TestLinkedList(new SingleLinkedList_Property<int>());// 測試字段版本鏈表Console.WriteLine("\n測試字段版本鏈表:");TestLinkedList(new SingleLinkedList_Field<int>());}static void TestLinkedList<T>(T list) where T : ISingleLinkedList<int>{// 添加節點list.Add(1);list.Add(2);list.Add(3);Console.WriteLine("添加 1, 2, 3 后鏈表內容應為:1 -> 2 -> 3");// 測試查找Console.WriteLine("查找 2: " + list.Contains(2)); // 應輸出 TrueConsole.WriteLine("查找 4: " + list.Contains(4)); // 應輸出 False// 測試刪除list.Remove(2);Console.WriteLine("刪除 2 后鏈表內容應為:1 -> 3");Console.WriteLine("查找 2: " + list.Contains(2)); // 應輸出 False// 測試更新list.Update(3, 4);Console.WriteLine("更新 3 為 4 后鏈表內容應為:1 -> 4");Console.WriteLine("查找 4: " + list.Contains(4)); // 應輸出 True}}/// <summary>/// 統一接口(便于測試不同版本的鏈表)/// </summary>public interface ISingleLinkedList<T>{void Add(T data);bool Remove(T data);bool Contains(T data);bool Update(T oldData, T newData);}/// <summary>/// 單向鏈表實現(屬性版本)/// </summary>/// <typeparam name="T">泛型數據類型</typeparam>public class SingleLinkedList_Property<T> : ISingleLinkedList<T>{// 頭節點(私有屬性)private SingleListNode<T>? head;/// <summary>/// 在鏈表尾部添加新節點/// </summary>/// <param name="data">要添加的數據</param>public void Add(T data){// 顯式聲明類型(不使用 var)SingleListNode<T> newNode = new SingleListNode<T>(data);if (head == null){head = newNode; // 鏈表為空時,新節點作為頭節點return;}// 遍歷鏈表找到最后一個節點SingleListNode<T> current = head;while (current.Next != null){current = current.Next;}current.Next = newNode; // 將新節點鏈接到尾部}/// <summary>/// 刪除第一個匹配的節點/// </summary>/// <param name="data">要刪除的數據</param>/// <returns>是否刪除成功</returns>public bool Remove(T data){if (head == null) return false;// 處理頭節點匹配的情況if (head.Data != null && head.Data.Equals(data)){head = head.Next; // 頭節點指向下一個節點return true;}// 遍歷鏈表查找匹配的節點SingleListNode<T> current = head;while (current.Next != null){if (current.Next.Data != null && current.Next.Data.Equals(data)){current.Next = current.Next.Next; // 跳過匹配的節點return true;}current = current.Next;}return false;}/// <summary>/// 查找節點是否存在/// </summary>/// <param name="data">要查找的數據</param>/// <returns>是否存在</returns>public bool Contains(T data){SingleListNode<T>? current = head;while (current != null){if (current.Data != null && current.Data.Equals(data)){return true;}current = current.Next;}return false;}/// <summary>/// 更新第一個匹配的節點的值/// </summary>/// <param name="oldData">舊數據</param>/// <param name="newData">新數據</param>/// <returns>是否更新成功</returns>public bool Update(T oldData, T newData){SingleListNode<T>? node = FindNode(oldData);if (node == null) return false;node.Data = newData; // 直接修改節點的數據return true;}/// <summary>/// 輔助方法:查找指定數據的節點/// </summary>private SingleListNode<T>? FindNode(T data){SingleListNode<T>? current = head;while (current != null){if (current.Data != null && current.Data.Equals(data)){return current;}current = current.Next;}return null;}}/// <summary>/// 單向鏈表實現(字段版本)/// </summary>/// <typeparam name="T">泛型數據類型</typeparam>public class SingleLinkedList_Field<T> :ISingleLinkedList<T>{// 頭節點(私有字段)private ListNode_Field<T>? head;/// <summary>/// 在鏈表尾部添加新節點/// </summary>public void Add(T data){ListNode_Field<T> newNode = new ListNode_Field<T>(data);if (head == null){head = newNode;return;}// 遍歷鏈表找到最后一個節點ListNode_Field<T> current = head;while (current.next != null){current = current.next;}current.next = newNode; // 直接操作字段}/// <summary>/// 刪除第一個匹配的節點/// </summary>public bool Remove(T data){if (head == null) return false;// 處理頭節點匹配的情況if (head.data != null && head.data.Equals(data)){head = head.next; // 直接操作字段return true;}ListNode_Field<T> current = head;while (current.next != null){if (current.next.data != null && current.next.data.Equals(data)){current.next = current.next.next; // 直接操作字段return true;}current = current.next;}return false;}/// <summary>/// 查找節點是否存在/// </summary>public bool Contains(T data){ListNode_Field<T>? current = head;while (current != null){if (current.data != null && current.data.Equals(data)){return true;}current = current.next;}return false;}/// <summary>/// 更新第一個匹配的節點的值/// </summary>public bool Update(T oldData, T newData){ListNode_Field<T>? node = FindNode(oldData);if (node == null) return false;node.data = newData; // 直接操作字段return true;}/// <summary>/// 輔助方法:查找指定數據的節點/// </summary>private ListNode_Field<T>? FindNode(T data){ListNode_Field<T>? current = head;while (current != null){if (current.data != null && current.data.Equals(data)){return current;}current = current.next;}return null;}}
}