.NET Framework-Doubly Linked List (LinkedList) Code Analysis (Figure)-C#.Net Tutorial-php.cn

.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:

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

## 1

public class LinkedList<T> : ICollection<T>, ICollection, IReadOnlyCollection<T>, ISerializable, IDeserializationCallback

Copy after login

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

Copy after login

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

Copy after login

Constructor

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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

Copy after login

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
        }

Copy after login

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); //双向链表，再次遍历到头结点时
            }
        }

Copy after login

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!