在恒定时间内将节点插入链表？ [英] Inserting a node into a linked list in constant-time?

问题描述

我正在进行一项任务，告诉我假设我有一个带有标题和尾节点的单链表。它要我在位置p之前插入一个项目y。任何人都可以查看我的代码并告诉我，我是否在正确的轨道上？如果没有，你可以向我提供任何提示或指示（没有双关语）？

I'm working on an assignment that is telling me to assume that I have a singly linked list with a header and tail nodes. It wants me to insert an item y before position p. Can anybody please look over my code and tell me if I'm on the right track? If not, can you provide me with any tips or pointers (no pun intended)?

tmp = new Node();
tmp.element = p.element;
tmp.next = p.next;
p.element = y;
p.next = tmp;

我想我可能错了，因为我根本没有使用头部和尾部节点，即使他们在问题的描述中特别提到。我正在考虑编写一个while循环来遍历列表，直到找到p并解决问题，但这不是常数时间，是吗？

I think I may be wrong because I do not utilize the header and tail nodes at all even though they are specifically mentioned in the description of the problem. I was thinking of writing a while loop to traverse the list until it found p and tackle the problem that way but that wouldn't be constant-time, would it?

推荐答案

如果您遇到一个算法，请写下来：

Just write it down if you get stuck with an algorithm:

// First we have a pointer to a node containing element (elm) 
// with possible a next element.
// Graphically drawn as:
// p -> [elm] -> ???

tmp = new Node();
// A new node is created. Variable tmp points to the new node which 
// currently has no value.
// p   -> [elm] -> ???
// tmp -> [?]

tmp.element = p.element;

// The new node now has the same element as the original.
// p   -> [elm] -> ???
// tmp -> [elm]

tmp.next = p.next;

// The new node now has the same next node as the original.
// p   -> [elm] -> ???
// tmp -> [elm] -> ???

p.element = y;

// The original node now contains the element y.
// p   -> [y] -> ???
// tmp -> [elm] -> ???

p.next = tmp;

// The new node is now the next node from the following.
// p   -> [y] -> [elm] -> ???
// tmp -> [elm] -> ???

你有所需的效果，但它可以更高效，我打赌你现在可以找到自己。

You have the required effect, but it can be more efficient and I bet you can now find out yourself.

写一些类似的东西更清楚：

It is more clear to write something like:

tmp = new Node();
tmp.element = y;
tmp.next = p;
p = tmp;

如果p不可变，那当然不起作用。但是如果p == NULL你的算法会失败。

Which of course does not work if p is not mutable. But your algorithm fails if p == NULL.

但我想说的是，如果你遇到算法问题，只需写出效果。特别是对于树木和链接列表，你需要确保所有指针指向正方向，否则你会变得很乱。

But what I meant to say, is, if you have problems with an algorithm, just write the effects out. Especially with trees and linked lists, you need to be sure all pointers are pointing to the righ direction, else you get a big mess.

这篇关于在恒定时间内将节点插入链表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！