.NET Framework-Doubly Linked List (LinkedList) Code Analysis (Figure)

---

.NETLinkList in the framework implements a two-way linked list. Let’s summarize its implementation source code.

Let’s first look at the map of the public properties and methods provided by LinkedList:

## 1

Interface implemented by LinkedList:

public class LinkedList : ICollection, ICollection, IReadOnlyCollection, ISerializable, IDeserializationCallback

2 Global

variables of LinkedList include,

head is the head node in the encapsulated class;

        // This LinkedList is a doubly-Linked circular list.
        internal LinkedListNode 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";

The data structure of each node encapsulated is:

public sealed class LinkedListNode
{   public LinkedListNode(T value);   
//获取LinkedListNode所属的LinkedList
   public LinkedList List { get; }   
   public LinkedListNode Next { get; }   
   public LinkedListNode Previous { get; }   
   //获取节点中包含的值。
   public T Value { get; set; }
}

3

Constructor

:

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

When constructing a collection of IEnumerable type, the AddLast(T) method is used. It also has an

overload

. The working details are as follows:

        public LinkedListNode AddLast(T value)
        {
            LinkedListNode result = new LinkedListNode(this, value);            
            if (head == null)
            {
                InternalInsertNodeToEmptyList(result);
            }            else
            {
                InternalInsertNodeBefore(head, result);
            }            return result;
        }        

        public void AddLast(LinkedListNode node)
        {
            ValidateNewNode(node);            
            if (head == null)
            {
                InternalInsertNodeToEmptyList(node);
            }            else
            {
                InternalInsertNodeBefore(head, node);
            }
            node.list = this; //结合LinkedListNode看
        }

The above 2 methods , the semantics is to insert a node,

Insert new nodes into empty lists, InternalInsertNodeToEmptyList

Insert new nodes into non-empty lists, InternalInsertNodeBefore, and give the node before which newNode is inserted, and also judge The newly inserted node is not a valid new node.

 internal void ValidateNewNode(LinkedListNode node)
        {            if (node == null)
            {                throw new ArgumentNullException(nameof(node));
            }            if (node.list != null)
            {                throw new InvalidOperationException(SR.LinkedListNodeIsAttached);
            }
        }

At the same time, it also provides a way to determine whether a node is a valid node:

        internal void ValidateNode(LinkedListNode node)
        {            if (node == null)
            {                throw new ArgumentNullException(nameof(node));
            }            if (node.list != this)
            {                throw new InvalidOperationException(SR.ExternalLinkedListNode);
            }
        }

This is an important internal method of a doubly linked list,

InternalInsertNodeToEmptyList implementation details:

        private void InternalInsertNodeToEmptyList(LinkedListNode 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 implementation details:

        private void InternalInsertNodeBefore(LinkedListNode node, LinkedListNode newNode)
        {
            newNode.next = node;
            newNode.prev = node.prev;
            node.prev.next = newNode;
            node.prev = newNode;
            version++;
            count++;
        }

4 A linked list is naturally inseparable from the public method of inserting a node,

        public LinkedListNode AddAfter(LinkedListNode node, T value)
        {
            ValidateNode(node);
            LinkedListNode result = new LinkedListNode(node.list, value);
            InternalInsertNodeBefore(node.next, result);            return result;
        }        public void AddAfter(LinkedListNode node, LinkedListNode newNode)
        {
            ValidateNode(node);
            ValidateNewNode(newNode);
            InternalInsertNodeBefore(node.next, newNode);
            newNode.list = this;
        }        public LinkedListNode AddBefore(LinkedListNode node, T value)
        {
            ValidateNode(node);
            LinkedListNode result = new LinkedListNode(node.list, value);
            InternalInsertNodeBefore(node, result);            if (node == head)
            {
                head = result;
            }            return result;
        }        public void AddBefore(LinkedListNode node, LinkedListNode newNode)
        {
            ValidateNode(node);
            ValidateNewNode(newNode);
            InternalInsertNodeBefore(node, newNode);
            newNode.list = this;            if (node == head)
            {
                head = newNode;
            }
        }        public LinkedListNode AddFirst(T value)
        {
            LinkedListNode result = new LinkedListNode(this, value);            
            if (head == null)
            {
                InternalInsertNodeToEmptyList(result);
            }            else
            {
                InternalInsertNodeBefore(head, result);
                head = result;
            }            return result;
        }        public void AddFirst(LinkedListNode node)
        {
            ValidateNewNode(node);            if (head == null)
            {
                InternalInsertNodeToEmptyList(node);
            }            else
            {
                InternalInsertNodeBefore(head, node);
                head = node;
            }
            node.list = this;
        }        public LinkedListNode AddLast(T value)
        {
            LinkedListNode result = new LinkedListNode(this, value);            
            if (head == null)
            {
                InternalInsertNodeToEmptyList(result);
            }            else
            {
                InternalInsertNodeBefore(head, result);
            }            return result;
        }        public void AddLast(LinkedListNode node)
        {
            ValidateNewNode(node);            if (head == null)
            {
                InternalInsertNodeToEmptyList(node);
            }            else
            {
                InternalInsertNodeBefore(head, node);
            }
            node.list = this;
        }

5 Let’s look at it again, clearing all nodes in the linked list, here It is to set all nodes to no longer point to the memory heap, and then wait for GC recycling,

        public void Clear()
        {
            LinkedListNode current = head;            
            while (current != null)
            {
                LinkedListNode temp = current;
                current = current.Next;   
                // use Next the instead of "next", otherwise it will loop forever
                temp.Invalidate();
            }

            head = null;
            count = 0;
            version++;
        }

6 Corresponding to only is to remove a series of interfaces of a certain node, which is similar to adding, and will not be repeated,

Clear calls Invalidate(), and the implementation is very simple:

        internal void Invalidate()
        {
            list = null;
            next = null;
            prev = null;
        }

7 To determine the existence of a node value as value, it calls the

Find method

,

        public bool Contains(T value)
        {            return Find(value) != null;
        }

Find method implementation details, similar

API

and FindLast, because it is a two-way linked list, so just traverse the linked list from the end,

       public LinkedListNode Find(T value)
        {
            LinkedListNode node = head;            
            //调用默认相等比较器
            EqualityComparer c = EqualityComparer.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 Let’s look at another copy of the data to

Implementation of 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 node = head;            
            if (node != null)
            {
                do
                {
                    array[index++] = node.item;
                    node = node.next;
                } while (node != head); //双向链表，再次遍历到头结点时
            }
        }

The above is the detailed content of .NET Framework-Doubly Linked List (LinkedList) Code Analysis (Figure). For more information, please follow other related articles on the PHP Chinese website!