.NET Framework - 二重リンク リスト (LinkedList) コード分析 (図)

---

.NETフレームワークのLinkListは双方向リンクリストを実装しています。その実装ソースコードを要約してみましょう。

まず、LinkedList によって提供されるパブリック プロパティとメソッドのマップを確認します:

1 LinkedList によって実装される インターフェイス:

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

2 LinkedList のグローバル 変数 には、以下が含まれます。

head はカプセル化されたクラスの 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 Constructor:

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

IEnumerable 型のコレクションを構築する場合、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 つのメソッド、セマンティクスは、特定のノードを挿入し、
空のリストに新しいノードを挿入し、InternalInsertNodeToEmptyList
new を挿入します。空のリスト 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 で呼び出されます。は非常に単純です:

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

7 ノード値が値として存在するかどうかを判断するには、 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 データを 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); //双向链表，再次遍历到头结点时
            }
        }

以上が.NET Framework - 二重リンク リスト (LinkedList) コード分析 (図)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。