.NET框架-雙向鍊錶（LinkedList）程式碼分析（圖）
.NET框架中的LinkList，實作的是雙向鍊錶，總結下它的實作原始碼。
先看下LinkedList提供的公有屬性與方法的導圖：
1 LinkedList實作的介面：
public class LinkedList<T> : ICollection<T>, ICollection, IReadOnlyCollection<T>, ISerializable, IDeserializationCallback
2 LinkedList的全域變數包括，
# #是封裝的類別內頭節點;
// This LinkedList is a doubly-Linked circular list.
internal LinkedListNode<T> head;
internal int count;
internal int version;
private object _syncRoot;
//A temporary variable which we need during deserialization.
private SerializationInfo _siInfo;
// names for serialization
private const string VersionName = "Version";
private const string CountName = "Count";
private const string ValuesName = "Data";封裝的每個節點的資料結構為：
public sealed class LinkedListNode<T>
{ public LinkedListNode(T value);
//获取LinkedListNode所属的LinkedList
public LinkedList<T> List { get; }
public LinkedListNode<T> Next { get; }
public LinkedListNode<T> Previous { get; }
//获取节点中包含的值。
public T Value { get; set; }
}3 建構子
：
public LinkedList() //默认的构造函数
{
} //带有参数的
public LinkedList(IEnumerable<T> collection)
{ if (collection == null)
{ throw new ArgumentNullException(nameof(collection));
} foreach (T item in collection)
{
AddLast(item);
}
}在建構IEnumerable類型的collection時，用到了AddLast(T)方法，它還有一個
重載，工作細節如下：
public LinkedListNode<T> AddLast(T value)
{
LinkedListNode<T> result = new LinkedListNode<T>(this, value);
if (head == null)
{
InternalInsertNodeToEmptyList(result);
} else
{
InternalInsertNodeBefore(head, result);
} return result;
}
public void AddLast(LinkedListNode<T> node)
{
ValidateNewNode(node);
if (head == null)
{
InternalInsertNodeToEmptyList(node);
} else
{
InternalInsertNodeBefore(head, node);
}
node.list = this; //结合LinkedListNode看
}以上2個方法，語意是插入某個節點，
分插入新節點到空list中，InternalInsertNodeToEmptyList插入新節點到不為空的list中，InternalInsertNodeBefore，並且給出在哪個節點前插入newNode，還判斷了新插入的節點是不是一個有效的新節點。
internal void ValidateNewNode(LinkedListNode<T> node)
{ if (node == null)
{ throw new ArgumentNullException(nameof(node));
} if (node.list != null)
{ throw new InvalidOperationException(SR.LinkedListNodeIsAttached);
}
}同時，也給出判斷一個節點是不是有效節點：
internal void ValidateNode(LinkedListNode<T> node)
{ if (node == null)
{ throw new ArgumentNullException(nameof(node));
} if (node.list != this)
{ throw new InvalidOperationException(SR.ExternalLinkedListNode);
}
}這是雙向鍊錶比較重要的內部方法，
InternalInsertNodeToEmptyList的實作細節：
private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
{
Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!");
newNode.next = newNode;
newNode.prev = newNode;
head = newNode;
version++;
count++;
}InternalInsertNodeBefore的實作細節： private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
newNode.next = node;
newNode.prev = node.prev;
node.prev.next = newNode;
node.prev = newNode;
version++;
count++;
}
public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value)
{
ValidateNode(node);
LinkedListNode<T> result = new LinkedListNode<T>(node.list, value);
InternalInsertNodeBefore(node.next, result); return result;
} public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
ValidateNode(node);
ValidateNewNode(newNode);
InternalInsertNodeBefore(node.next, newNode);
newNode.list = this;
} public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value)
{
ValidateNode(node);
LinkedListNode<T> result = new LinkedListNode<T>(node.list, value);
InternalInsertNodeBefore(node, result); if (node == head)
{
head = result;
} return result;
} public void AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
ValidateNode(node);
ValidateNewNode(newNode);
InternalInsertNodeBefore(node, newNode);
newNode.list = this; if (node == head)
{
head = newNode;
}
} public LinkedListNode<T> AddFirst(T value)
{
LinkedListNode<T> result = new LinkedListNode<T>(this, value);
if (head == null)
{
InternalInsertNodeToEmptyList(result);
} else
{
InternalInsertNodeBefore(head, result);
head = result;
} return result;
} public void AddFirst(LinkedListNode<T> node)
{
ValidateNewNode(node); if (head == null)
{
InternalInsertNodeToEmptyList(node);
} else
{
InternalInsertNodeBefore(head, node);
head = node;
}
node.list = this;
} public LinkedListNode<T> AddLast(T value)
{
LinkedListNode<T> result = new LinkedListNode<T>(this, value);
if (head == null)
{
InternalInsertNodeToEmptyList(result);
} else
{
InternalInsertNodeBefore(head, result);
} return result;
} public void AddLast(LinkedListNode<T> node)
{
ValidateNewNode(node); if (head == null)
{
InternalInsertNodeToEmptyList(node);
} else
{
InternalInsertNodeBefore(head, node);
}
node.list = this;
}5 再看下，清除鍊錶所有節點，此處是設定所有節點不在指向記憶體堆，然後等GC回收， public void Clear()
{
LinkedListNode<T> current = head;
while (current != null)
{
LinkedListNode<T> temp = current;
current = current.Next;
// use Next the instead of "next", otherwise it will loop forever
temp.Invalidate();
}
head = null;
count = 0;
version++;
}
Clear裡面呼叫了Invalidate()，實作很簡單： internal void Invalidate()
{
list = null;
next = null;
prev = null;
}
public bool Contains(T value)
{ return Find(value) != null;
} public LinkedListNode<T> Find(T value)
{
LinkedListNode<T> node = head;
//调用默认相等比较器
EqualityComparer<T> c = EqualityComparer<T>.Default;
if (node != null)//链表为null
{
if (value != null)
{
do
{
if (c.Equals(node.item, value)) //Equals：某个节点node的item与value相等
{
return node;
}
node = node.next;
} while (node != head);
}
else
{
do
{
if (node.item == null)
{
return node;
}
node = node.next;
} while (node != head);
}
} return null; //链表为null，直接返回null
} public void CopyTo(T[] array, int index)
{
if (array == null)
{
throw new ArgumentNullException(nameof(array));
}
if (index < 0)
{
throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_NeedNonNegNum);
}
if (index > array.Length)
{
throw new ArgumentOutOfRangeException(nameof(index), index, SR.ArgumentOutOfRange_BiggerThanCollection);
}
if (array.Length - index < Count)
{
throw new ArgumentException(SR.Arg_InsufficientSpace);
}
LinkedListNode<T> node = head;
if (node != null)
{
do
{
array[index++] = node.item;
node = node.next;
} while (node != head); //双向链表，再次遍历到头结点时
}
}以上是.NET框架-雙向鍊錶（LinkedList）程式碼分析（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
Video Face Swap
使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
使用LinkedList類別的removeLast()方法刪除鍊錶中的最後一個元素
Jul 24, 2023 pm 05:13 PM
使用LinkedList類別的removeLast()方法刪除鍊錶中的最後一個元素LinkedList是Java集合框架中常見的一種資料結構，它以雙向鍊錶的形式儲存元素。透過LinkedList類別提供的方法，我們可以方便地對鍊錶進行操作，例如新增、刪除和修改元素。在某些場景下，我們可能需要刪除鍊錶中的最後一個元素。 LinkedList類別提供了removeLas
Java程式為LinkedList新增元素
Aug 26, 2023 pm 10:21 PM
LinkedList是JavaCollectionFramework的通用類別，它實作了List、Deque和Queue三個介面。它提供了LinkedList資料結構的功能，LinkedList是一種線性資料結構，其中每個元素相互連結。我們可以對LinkedList執行多種操作，包括新增、刪除和遍歷元素。要將元素加入LinkedList集合中，我們可以使用各種內建方法，例如add()、addFirst()和addLast()。我們將探索如何使用這些方法將元素新增至LinkedList。在Java
使用C++按給定大小將雙向鍊錶分組反轉
Sep 04, 2023 am 09:49 AM
在這個問題中，我們得到一個指向鍊錶頭部的指標和一個整數k。在大小為k的群組中，我們需要反轉鍊錶。例如-Input:1<->2<->3<->4<->5(doublylinkedlist),k=3Output:3<->2<->1<->5<->4尋找解決方案的方法在這個問題中，我們將制定一個遞歸演算法來解決這個問題。在這種方法中，我們將使用遞歸並使用遞歸來解決問題。範例#include<iostream&
Java中如何使用LinkedList.addFirst()方法將元素新增至鍊錶頭部？
Nov 18, 2023 pm 03:51 PM
Java中的LinkedList類別提供了addFirst()方法，可以將元素加入鍊錶的頭部。此方法的作用是在鍊錶的開頭添加一個元素，並將原始鍊錶的其他元素後移。以下是使用LinkedList.addFirst()方法將元素加入到鍊錶頭部的範例程式碼：importjava.util.LinkedList;publicclassMain{pu
Java文件解讀：LinkedList類別的addFirst()方法功能解析
Nov 03, 2023 am 09:09 AM
Java文件解讀：LinkedList類別的addFirst()方法功能解析LinkedList是Java集合框架中的雙向鍊錶實作類，它提供了一系列在清單中進行新增、刪除和尋找操作的方法。其中，addFirst()方法是LinkedList類別中的重要方法之一。本文將深入解析addFirst()方法的功能，並附帶具體的程式碼範例。 addFirst()方法的
如何在Java中將LinkedList轉換為Array？
Aug 29, 2023 pm 11:09 PM
LinkedList類別的toArray()方法將目前的LinkedList物件轉換為物件類型的陣列並傳回它。此數組按正確順序（從第一個元素到最後一個元素）包含此列表中的所有元素。它充當基於數組和基於集合的API之間的橋樑。因此，將LinkedList轉換為陣列-實例化LinkedList類別。使用add()方法填充它。呼叫上面建立的鍊錶上的toArray()方法並檢索物件數組。將物件數組的每個元素轉換為字串。範例 即時示範importjava.util.Arrays;importjava.uti
Java文件解讀：LinkedList類別的addLast()方法功能解析
Nov 03, 2023 pm 02:26 PM
Java文件解讀：LinkedList類別的addLast()方法功能解析在Java的集合框架中，LinkedList類別是雙向鍊錶實作的List介面。 LinkedList類別提供了許多操作鍊錶的方法，其中包括addLast()方法。本文將對LinkedList的addLast()方法進行詳細解析，並提供具體的程式碼範例。 addLast()方法的功能是將指定的元
使用LinkedList類別的removeFirstOccurrence()方法刪除鍊錶中第一次出現的指定元素
Jul 24, 2023 pm 04:50 PM
使用LinkedList類別的removeFirstOccurrence()方法刪除鍊錶中第一次出現的指定元素鍊錶是一種常用的資料結構，它由許多節點組成，每個節點包含一個資料元素和指向下一個節點的引用。 LinkedList類別是Java集合框架中提供的一種實作鍊錶的類，它提供了豐富的方法來操作鍊錶。其中，removeFirstOccurrence()方法可以用來
