为什么 AddAfter() 有常量时间?

Question

在链表操作中，Addbefore(node，key(具有线性时间，即O(n(，但AddAfter(node，key(具有恒定时间，即O(1(。谁能说出原因？

Answer 1

想象一下单链表是如何组织的：

A->B->C->D

现在，假设您想在 B 之后添加一个节点。您可以直接访问节点并访问其next指针以链接新节点。因此，如果您创建一个新节点，使用传递的密钥将其称为 X，您可以执行以下操作：

Copy B's next pointer to X  // B and X both point to C
Set B's next pointer to X   // B points to X and X points to C
AddAfter(node,key)
{
newNode = CreateNewNode(key);
newNode.next = node.next;
node.next = newNode;
}

但是如果你想在之前添加，你不知道哪个节点在 B之前。因此，您必须扫描列表以找出：

AddBefore(node, key)
{
parent = head;
// find the node that points to the passed node
while (parent.next != node)
{
parent = parent.next;
}
// Then add the new node after parent
AddAfter(parent, key);
}

对于双向链表来说，这不是必需的，因为每个节点都有一个指向其前身及其后继节点的指针。

吉姆