当我发现我不太了解和方法的工作原理时,我正在浏览.NET参考来查看aLinkedList<T>
及其相关LinkedListNode<T>
元素的内部工作原理。我会考虑解决我的困惑。AddLast(T item)
AddLast(LinkedListNode<T> node)
AddLast(T item)
我的看法是,该方法首先创建一个新节点,该节点引用当前列表并保存需要添加的值。然后,它通过查看head
,假设曾经添加到列表中的第一项来检查列表是否为空。
head
为空
呼叫被叫方法InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
,其中newNode
在这种情况下将是result
从围绕该方法的范围。它检查列表是否实际上为空,然后在将其设置为head
列表的之前,修改要添加的节点以双向链接到自身。同时更新列表的数量和版本。
private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
{
Debug.Assert( head == null && count == 0, "LinkedList must be empty when this method is called!");
newNode.next = newNode; // i.e. result.next = result
newNode.prev = newNode; // i.e. result.prev = result
head = newNode; // i.e. head = result
version++;
count++;
}
B) head
不为空
呼叫被叫方法InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
,其中node
是head
和newNode
是result
从围绕这一方法的范围。首先,它检查列表是否不为空,但是添加新节点的实际逻辑如下:
private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
{
newNode.next = node; // result.next = head
newNode.prev = node.prev; // result.prev = head.prev (but isn't head.prev just head?)
node.prev.next = newNode; // head.prev.next = result (so result gets added after head?)
node.prev = newNode; // head.prev = result (why does head link back to result?)
version++;
count++;
}
我真的不明白这如何导致在列表的最后一个已知链接之后插入新链接。为什么这不会导致在头之后而不是最后一个已知链接之后添加链接?
LinkedList<T>
是一个双向链接列表:每个节点在引用之前和之后都引用了这些节点。
head
是列表中的第一个元素,但其prev
成员指向列表中的最后一个元素。您可以从Last
属性中看到以下内容:
public LinkedListNode<T> Last {
get { return head == null? null: head.prev;}
}
列表的最后一个元素与之间的这种关系head
是双向的:head.prev
是列表中的最后一个元素,列表中的最后一个元素next
是head
。
所以:
// Remember that 'node' is the 'head'. I've replaced 'node' with
// 'head' to make this clearer.
// The new node's 'next' points to 'head', as it should
newNode.next = head;
// The new node's 'prev' points to the old last element in the list
// (remember that 'head.prev' is the last element in the list)
newNode.prev = head.prev;
// 'head.prev' is the old last element in the list. This is now the second-last
// element in the list, and its 'next' should be our new node. This
// is the reciprocal of 'newNode.prev = head.prev'
head.prev.next = newNode;
// head.prev now points to the new node, as it should. This is the reciprocal of
// 'newNode.next = head'
head.prev = newNode;
尝试绘制“之前”状态:
LinkedList
|
v
oldLastNode <-- prev -- head
-- next -->
后:
LinkedList
|
v
oldLastNode <-- prev -- newNode <-- prev -- head
-- next --> -- next -->
所以我们要做:
oldLastNode.next = newNode
newNode.prev = oldLastNode
newNode.next = head
head.prev = newNode
从第一个图表中,我们可以看到那oldLastNode
是旧的head.prev
。因此,只要我们head.prev
在重新分配之前进行更改head.prev
,我们就可以这样写:
head.prev.next = newNode
newNode.prev = head.prev
newNode.next = head
head.prev = newNode
这些操作与您的问题相同,但已重新安排。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句