Clever Geek Handbook

Inserting a node into a linked list at constant time?

I'm working on an assignment that tells me to assume that I have a separate list with header and tail nodes. It wants me to insert the y element up to position p. Can someone please review my code and tell me if I am on the right track correctly? 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 am wrong because I do not use header and tail at all, although they are specifically mentioned in the problem description. I was thinking about writing a while loop to loop through the list until it finds p and fixes the problem, but that won't be permanent, right?

+1


source to share


7 replies


Just write it down if you get stuck with the 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 effect you want, but it could be more effective, and I'm sure you can now recognize yourself.

It is clearer to write something like:



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

Which of course doesn't work if p doesn't change. But your algorithm fails if p == NULL.

But I wanted to say, is, if you have problems with the algorithm, just write the effects. Especially with trees and linked lists, you have to make sure that all pointers point forward or you end up with a lot of mess.

+5


source


Tip : 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). This does not mean that you cannot create a sufficiently efficient algorithm, but it will always have at least linear complexity.



+4


source


The reason the header and tail node is mentioned in the question is to update the header and tail link, if replacing the node that your creation becomes the header or tail. In other words, a given previous node is either a header or a tail.

+1


source


What you are not doing is bind the element that was before p before y was inserted into y. So when y is inserted before p, no one is pointing to y now (at least not in the code you described).

You can only insert at constant time if you know the positions of the elements between which you must insert y. If you need to search for that position, you can never insert constant time in the same link list.

0


source


How about using code that already exists? LinkedHashMap, LinkedList, LinkedHashSet. You can also check the code and find out.

0


source 


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
0


source


In a single LinkedList, just adding a Node to the beginning of the list, or creating a list with only one Node will take O (1). OR, as they provided the TailNode, also inserting the Node at the end of the list will take O (1).

every other insert operation will take O (n).

0


source






More articles:


All Articles