Inserting a node into a linked list in constant-time?

Question

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;

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?

Thank you!

Answer 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.

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.

Answer 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.

Answer 3

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

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.

Answer 4

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

Answer 5

1.create a node ptr 2.ptr->info=item //item is the element to be inserted... 3.ptr->next=NULL 4.if (start==NULL)//insertion at the end... 5.start=ptr 6.else 7.temp=ptr 8.while(temp->next!=NULL) 9.temp=temp->next 10.end while 11.end if 12.if (start==NULL)//insertion at the beginning... 13.start=ptr 14.else 15.temp=start 16.ptr->info=item 17.ptr->next=start 18.start=ptr 19.end if 20.temp=start//insertion at specified location... 21.for(i=1;inext 27.end if 28.end for 29.t->next=ptr->next 30.t->next=ptr

Answer 6

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.