欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

.NET框架-双向链表(LinkedList)代码分析(图)

程序员文章站 2022-04-06 19:36:40
...



.NET框架中的LinkList,实现的是双向链表,总结下它的实现源码。

先看下LinkedList提供的公有属性和方法的导图:


.NET框架-双向链表(LinkedList)代码分析(图)

1 LinkedList实现的接口

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

2 LinkedList的全局变量包括,

head是封装的类内头节点

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

封装的每个节点的数据结构为:

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 构造函数

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

在构造IEnumerable类型的collection时,用到了AddLast(T)方法,它还有一个重载,工作细节如下:

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

以上2个方法,语义是插入某个节点,
分插入新节点到空list中,InternalInsertNodeToEmptyList
插入新节点到不为空的list中,InternalInsertNodeBefore,并且给出在哪个节点前插入newNode,还判断了新插入的节点是不是一个有效的新节点。

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

同时,还给出判断一个节点是不是有效节点:

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

这是双向链表比较重要的内部方法,

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

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 链表自然离不开插入某个节点的公有方法,

        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 再看下,清除链表所有节点,此处是设置所有节点不在指向内存堆,然后等GC回收,

        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 与只相对应的是移除某个节点的一些列接口,与添加类似,不再赘述,

Clear里面调用了Invalidate(),实现很简单:

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

7 判断某个节点值为value的存在性,里面调用Find方法

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

Find方法实现细节,类似的API还有FindLast,因为是双向链表,所以从尾部开始遍历链表即可,

       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 再看一个复制数据到数组的实现:

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

以上就是.NET框架-双向链表(LinkedList)代码分析(图)的详细内容,更多请关注其它相关文章!