.NETLinkList im Framework implementiert eine doppelt verknüpfte Liste. Fassen wir den Implementierungsquellcode zusammen.
Schauen Sie sich zunächst die von LinkedList bereitgestellte Karte der öffentlichen Eigenschaften und Methoden an:
1 Die von LinkedList implementierte Schnittstelle:
public class LinkedList<T> : ICollection<T>, ICollection, IReadOnlyCollection<T>, ISerializable, IDeserializationCallback
Nach dem Login kopieren
2 Die globale -Variable von LinkedList enthält
Kopf ist der Hauptknoten in der gekapselten Klasse; die Datenstruktur jedes von
// 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";Nach dem Login kopieren
gekapselten Knotens ist:
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; }
}Nach dem Login kopieren
3 Strukturfunktion :
public LinkedList() //默认的构造函数
{
} //带有参数的
public LinkedList(IEnumerable<T> collection)
{ if (collection == null)
{ throw new ArgumentNullException(nameof(collection));
} foreach (T item in collection)
{
AddLast(item);
}
}Nach dem Login kopieren
Beim Erstellen einer Sammlung vom Typ IEnumerable wird die AddLast(T)-Methode verwendet. Sie verfügt auch über eine -Überladung wie folgt:
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看
}Nach dem Login kopieren
Die Semantik der beiden oben genannten Methoden besteht darin, einen Knoten einzufügen.
Einen neuen Knoten in eine leere Liste einfügen. InternalInsertNodeToEmptyList
Einen neuen Knoten in eine nicht leere Liste einfügen list, InternalInsertNodeBefore und geben Sie „NewNode vor welchem Knoten einfügen“ an und bestimmen Sie außerdem, ob der neu eingefügte Knoten ein gültiger neuer Knoten ist.
internal void ValidateNewNode(LinkedListNode<T> node)
{ if (node == null)
{ throw new ArgumentNullException(nameof(node));
} if (node.list != null)
{ throw new InvalidOperationException(SR.LinkedListNodeIsAttached);
}
}Nach dem Login kopieren
Gleichzeitig bietet es auch eine Möglichkeit zu bestimmen, ob ein Knoten ein gültiger Knoten ist:
internal void ValidateNode(LinkedListNode<T> node)
{ if (node == null)
{ throw new ArgumentNullException(nameof(node));
} if (node.list != this)
{ throw new InvalidOperationException(SR.ExternalLinkedListNode);
}
}Nach dem Login kopieren
Dies ist eine wichtige interne Methode einer doppelt verknüpften Liste.
Details zur Implementierung von 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++;
}Nach dem Login kopieren
Details zur Implementierung von 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++;
}Nach dem Login kopieren
4 Natürlich sind verknüpfte Listen untrennbar mit der öffentlichen Methode zum Einfügen eines Knotens verbunden ,
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;
}Nach dem Login kopieren
5 Dann werfen Sie einen Blick darauf, löschen Sie alle Knoten in der verknüpften Liste. Hier werden alle Knoten so eingestellt, dass sie nicht auf den Speicherheap verweisen, und dann auf das GC-Recycling warten >
6 entspricht dem Entfernen einer Reihe von Schnittstellen eines bestimmten Knotens. Ich werde nicht auf Details eingehen.
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++;
}Nach dem Login kopieren
Die Implementierung ist sehr einfach 🎜>
7 Um die Existenz eines Knotenwerts als Wert zu ermitteln, rufen Sie
Methode suchen
internal void Invalidate()
{
list = null;
next = null;
prev = null;
}Nach dem Login kopieren
,
Methodenimplementierungsdetails suchen, ähnlich
API< auf 🎜> und FindLast, da es sich um eine doppelt verknüpfte Liste handelt. Beginnen Sie also einfach mit dem Durchlaufen der verknüpften Liste am Ende,
public bool Contains(T value)
{ return Find(value) != null;
}Nach dem Login kopieren
8 Schauen wir uns eine andere Implementierung des Kopierens von Daten in das Array
an :
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
}Nach dem Login kopieren
Das obige ist der detaillierte Inhalt vonCodeanalyse für .NET Framework – doppelt verknüpfte Liste (LinkedList) (Abbildung). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
