.NETフレームワークのLinkListは双方向リンクリストを実装しています。その実装ソースコードを要約してみましょう。
まず、LinkedList によって提供されるパブリック プロパティとメソッドのマップを確認します:
1 LinkedList によって実装される インターフェイス:
public class LinkedList<T> : ICollection<T>, ICollection, IReadOnlyCollection<T>, ISerializable, IDeserializationCallback
2 LinkedList のグローバル 変数 には、以下が含まれます。
head はカプセル化されたクラスの head ノード です。
// 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 Constructor:
public LinkedList() //默认的构造函数 { } //带有参数的 public LinkedList(IEnumerable<T> collection) { if (collection == null) { throw new ArgumentNullException(nameof(collection)); } foreach (T item in collection) { AddLast(item); } }
IEnumerable 型のコレクションを構築する場合、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 つのメソッド、セマンティクスは、特定のノードを挿入し、
空のリストに新しいノードを挿入し、InternalInsertNodeToEmptyList
new を挿入します。空のリスト 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++; }
4 リンク リストは当然のことです。これはノードを挿入するパブリック メソッドと切り離すことができません。
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++; }
6 にのみ対応します。ノードの一連のインターフェイスの削除は追加と同様なので、詳細は説明しません。
Clear で呼び出されます。は非常に単純です:
internal void Invalidate() { list = null; next = null; prev = null; }
7 ノード値が値として存在するかどうかを判断するには、 Find メソッド、
public bool Contains(T value) { return Find(value) != null; }
Find メソッド実装の詳細を呼び出します。これは、 API と FindLast に似ています。これは二重リンクリストであるため、リンクされたリストを端からたどるだけです、
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 }
8 データを array にコピーする実装を見てみましょう :
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 Framework - 二重リンク リスト (LinkedList) コード分析 (図)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。