.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<T> : ICollection<T>, ICollection, IReadOnlyCollection<T>, 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<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";

The data structure of each node encapsulated is:

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

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

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<T> 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<T> 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<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 implementation details:

        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 A linked list is naturally inseparable from the public method of inserting a node,

        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 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<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 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<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 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<T> 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!