.NET框架中的LinkList，实现的是双向链表，总结下它的实现源码。
先看下LinkedList提供的公有属性和方法的导图：
1 LinkedList实现的接口：
public class LinkedList : ICollection, ICollection, IReadOnlyCollection, ISerializable, IDeserializationCallback
Copy after login
2 LinkedList的全局变量包括，
head是封装的类内头节点；
// 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 构造函数：
public LinkedList() //默认的构造函数
{
} //带有参数的
public LinkedList(IEnumerable collection)
{ if (collection == null)
{ throw new ArgumentNullException(nameof(collection));
} foreach (T item in collection)
{
AddLast(item);
}
}Copy after login
在构造IEnumerable类型的collection时，用到了AddLast(T)方法，它还有一个重载，工作细节如下：
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
以上2个方法，语义是插入某个节点，
分插入新节点到空list中，InternalInsertNodeToEmptyList
插入新节点到不为空的list中，InternalInsertNodeBefore，并且给出在哪个节点前插入newNode，还判断了新插入的节点是不是一个有效的新节点。
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
同时，还给出判断一个节点是不是有效节点：
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
这是双向链表比较重要的内部方法，
InternalInsertNodeToEmptyList的实现细节：
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的实现细节：
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 链表自然离不开插入某个节点的公有方法，
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 再看下，清除链表所有节点，此处是设置所有节点不在指向内存堆，然后等GC回收，
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 与只相对应的是移除某个节点的一些列接口，与添加类似，不再赘述，
Clear里面调用了Invalidate()，实现很简单：
internal void Invalidate()
{
list = null;
next = null;
prev = null;
}Copy after login
7 判断某个节点值为value的存在性，里面调用Find方法，
public bool Contains(T value)
{ return Find(value) != null;
}Copy after login
Find方法实现细节，类似的API还有FindLast，因为是双向链表，所以从尾部开始遍历链表即可，
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
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 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框架-双向链表（LinkedList）代码分析（图）. For more information, please follow other related articles on the PHP Chinese website!
0
2
481
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
