Codeanalyse für .NET Framework – doppelt verknüpfte Liste (LinkedList) (Abbildung)

---

.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

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";

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; }
}

3 Strukturfunktion :

        public LinkedList() //默认的构造函数
        {
        }        //带有参数的
        public LinkedList(IEnumerable<T> collection)
        {            if (collection == null)
            {                throw new ArgumentNullException(nameof(collection));
            }            foreach (T item in collection)
            {
                AddLast(item);
            }
        }

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看
        }

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);
            }
        }

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);
            }
        }

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++;
        }

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++;
        }

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;
        }

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++;
        }

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;
        }

,

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;
        }

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
        }

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!