.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:
## 1
Interface implemented by LinkedList:
public class LinkedList : ICollection, ICollection, IReadOnlyCollection, 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 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
public sealed class LinkedListNode
{ public LinkedListNode(T value);
//获取LinkedListNode所属的LinkedList
public LinkedList List { get; }
public LinkedListNode Next { get; }
public LinkedListNode Previous { get; }
//获取节点中包含的值。
public T Value { get; set; }
}
Copy after login
3
Constructor
: public LinkedList() //默认的构造函数
{
} //带有参数的
public LinkedList(IEnumerable collection)
{ if (collection == null)
{ throw new ArgumentNullException(nameof(collection));
} foreach (T item in collection)
{
AddLast(item);
}
}Copy after login
overload
. The working details are as follows: public LinkedListNode AddLast(T value)
{
LinkedListNode result = new LinkedListNode(this, value);
if (head == null)
{
InternalInsertNodeToEmptyList(result);
} else
{
InternalInsertNodeBefore(head, result);
} return result;
}
public void AddLast(LinkedListNode node)
{
ValidateNewNode(node);
if (head == null)
{
InternalInsertNodeToEmptyList(node);
} else
{
InternalInsertNodeBefore(head, node);
}
node.list = this; //结合LinkedListNode看
}
Copy after login
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 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 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 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 node, LinkedListNode 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 AddAfter(LinkedListNode node, T value)
{
ValidateNode(node);
LinkedListNode result = new LinkedListNode(node.list, value);
InternalInsertNodeBefore(node.next, result); return result;
} public void AddAfter(LinkedListNode node, LinkedListNode newNode)
{
ValidateNode(node);
ValidateNewNode(newNode);
InternalInsertNodeBefore(node.next, newNode);
newNode.list = this;
} public LinkedListNode AddBefore(LinkedListNode node, T value)
{
ValidateNode(node);
LinkedListNode result = new LinkedListNode(node.list, value);
InternalInsertNodeBefore(node, result); if (node == head)
{
head = result;
} return result;
} public void AddBefore(LinkedListNode node, LinkedListNode newNode)
{
ValidateNode(node);
ValidateNewNode(newNode);
InternalInsertNodeBefore(node, newNode);
newNode.list = this; if (node == head)
{
head = newNode;
}
} public LinkedListNode AddFirst(T value)
{
LinkedListNode result = new LinkedListNode(this, value);
if (head == null)
{
InternalInsertNodeToEmptyList(result);
} else
{
InternalInsertNodeBefore(head, result);
head = result;
} return result;
} public void AddFirst(LinkedListNode node)
{
ValidateNewNode(node); if (head == null)
{
InternalInsertNodeToEmptyList(node);
} else
{
InternalInsertNodeBefore(head, node);
head = node;
}
node.list = this;
} public LinkedListNode AddLast(T value)
{
LinkedListNode result = new LinkedListNode(this, value);
if (head == null)
{
InternalInsertNodeToEmptyList(result);
} else
{
InternalInsertNodeBefore(head, result);
} return result;
} public void AddLast(LinkedListNode 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 current = head;
while (current != null)
{
LinkedListNode 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
API
and FindLast, because it is a two-way linked list, so just traverse the linked list from the end, public LinkedListNode Find(T value)
{
LinkedListNode node = head;
//调用默认相等比较器
EqualityComparer c = EqualityComparer.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
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 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!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
