在恒定时间内将节点插入链表？

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)?

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

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

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?

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

7 个解决方案

#1

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;

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

如果p不可变,那当然不起作用。但是如果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.

但我想说的是,如果你对算法有问题,那就把效果写出来吧。特别是对于树和链表,你需要确保所有指针都指向正方向,否则你会变得很乱。

#2

Hint: insertion into a linked list is only constant when position n = 0, or the head of the list. Otherwise, the worst-case complexity is O(n). That's not to say that you cannot create a reasonably efficient algorithm, but it will always have at least linear complexity.

提示:当位置n = 0或列表的头部时,插入到链表中只是常量。否则,最坏情况的复杂性是O(n)。这并不是说你不能创造一个合理有效的算法,但它总是至少具有线性复杂性。

#3

The reason why the header and tail node is given in the question is to the update the header and tail reference if the the replacement node that your creating happens to become the header or tail. In other is words, the given previous node is either a header or tail.

在问题中给出头部和尾部节点的原因是,如果替换节点的创建恰好成为头部或尾部,则更新头部和尾部引用。换句话说,给定的前一个节点是标题或尾部。

#4

What you are not doing is linking the element that was before p prior to insertion of y to y. So while y is inserted before p, no one is pointing to y now (at-least not in the code snipped you showed).

你没做的是将y插入之前的p之前的元素链接到y。所以当y在p之前插入时,现在没有人指向y(至少在你所显示的代码中没有)。

You can only insert in constant time if you know the positions of the elements between which you have to insert y. If you have to search for that position, then you can never have a constant time insertion in a single link list.

如果您知道必须插入y的元素的位置,则只能在常量时间插入。如果您必须搜索该位置,那么您永远不能在单个链接列表中插入常量时间。

#5

How about using code that is already there? LinkedHashMap, LinkedList, LinkedHashSet. You can also check out the code and learn from it.

如何使用已存在的代码? LinkedHashMap,LinkedList,LinkedHashSet。您还可以查看代码并从中学习。

#6

create a node ptr
ptr->info = item //item is the element to be inserted...
ptr->next = NULL
if (start == NULL) //insertion at the end...
    start = ptr
else
    temp = ptr
    while (temp->next != NULL)
        temp = temp->next
    end while 
end if
if (start == NULL) //insertion at the beginning...
    start = ptr
else
    temp = start
    ptr->info = item
    ptr->next = start
    start = ptr
end if
temp = start //insertion at specified location...
for (i = 1; i < pos-1; i++)
    if (start == NULL)
        start = ptr
    else
        t = temp
        temp = temp->next
    end if
end for
t->next = ptr->next
t->next = ptr

#7

In a singly LinkedList only adding a Node to the beginning of the list or creating a List with only one Node would take O(1). OR as they have provided the TailNode also Inserting the Node at End of list would take O(1).

在单链接列表中,仅将节点添加到列表的开头或创建仅具有一个节点的列表将采用O(1)。或者,因为他们提供了TailNode,在列表末尾插入节点也需要O(1)。

every other inserting operation will take O(n).

每隔一次插入操作都需要O(n)。

#1