.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范例的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)代码剖析(图)的细致内容,更多请关注ki4网别的相干文章!