.NET Framework-이중 연결 목록(LinkedList) 코드 분석(그림)

---

.NET프레임워크의 LinkList는 이중 연결 목록을 구현합니다. 구현 소스 코드를 요약해 보겠습니다.

먼저 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 유형의 컬렉션을 구성할 때 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
비어 있지 않은 목록인 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에 해당하는 것은 a만 제거하는 것입니다. 추가와 유사하며 자세히 설명하지 않을 특정 노드의 일련의 인터페이스

Clear는 Invalidate()를 호출하고 구현은 매우 간단합니다.

        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 배열 구현에 대한 또 다른 데이터 복사본을 살펴보겠습니다.

        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 중국어 웹사이트의 기타 관련 기사를 참조하세요!