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?

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

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.

Answer 4

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

every other inserting operation will take O(n).

Answer 5

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

Answer 6

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 7

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

Answer 8

The whole explanation and the 2 codes are in Java... but its easy to translate it to any other language of your choice. I do want to help you however I am a beginner myself... Still I have used the logic, sharing it from the queues implementation... I have pasted two codes one is in O(N) the other contains a method called append which is in O(1) Now, the explanation

1. declare the tail node with head node in the class

2. now in the method append class in the 2nd code below just look at the tail pointer

3. CASE 1: when LL empty usually people check if (head == null) if true then they point the head to the new Node and return

   whereas what I have done is I checked if (tail == null) and if it was true then tail = head = newnode meaning that the tail and head both now point to the new Node to be added.

4. CASE 2: when LL is not empty wait, haha, hear me out first, I know you might be thinking that what if the LL has just 1 node currently, then what? well... for that...

   this case 2 handles it automatically, in case 1 it sets the head and tail equal to the newnode right, so it now just changes and modifies the tail node keeping the head node intact.

   this way, the head keeps pointing to the first node and the tail keeps updating and pointing to the newnodes created with each append function call.

Hope this explanation helps...

PS. check from line 24 for O(N) and 102 for O(1) and every time a newnode is added to the LL by the append method call, the tail will point to the new node to be added.

import java.io.*;
import java.util.*;

public class Solution {
    
    // class Solution is what should be called as the LINKEDLIST class but its ok
    
    Node head;  // declaring a head for the LL
    
    class Node {    // Node class
    
        int data;   // the .data variable
        Node ref;   // .ref aka .next 

        Node(int data) {    // constructor for initializing the values
        
            this.data = data;
            this.ref = null;
            
        }
    }
    
    public void append(int data) {  // i call 'to join at the end' as append
        // O(N)
    
        Node newnode = new Node(data);  // new node creation
        
        if (head == null) {     // checking is head is null aka None in Py
            head = newnode;
            return;
        }
        
        Node curr = head;   // assigning head to a curr node ready for traversal
        
        while (curr.ref != null) {  // traversal begins
            curr = curr.ref;
        }                           // traversal ends
        
        curr.ref = newnode; // this is the last node where the join happens
        
    }
    
    public void p() {   // i name printing function as p()
    
        if (head == null) { // if head is null then print empty
            System.out.println("Empty");
            return;
        }
        
        Node curr = head;   // same thing - traversal begins here
        
        while (curr != null) {
            System.out.println(curr.data);
            curr = curr.ref;
        }   // by now all data values have been printed out already
        
    }

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);    // scanner class for input
        
        Solution l = new Solution();    // object creating for LL as Solution class name
        
        int numberOfNodes = sc.nextInt();   // input for number of NODEs in LL
        
        for (int i = 0; i < numberOfNodes; i++) {   // loop for .data values
        
            int data = sc.nextInt();    
            l.append(data); // function append call for each (i)
            
        }
        
        l.p();  // finally print func call to display output LL
        
    }
}


class PractGG {
    Node head;
    Node tail;

    class Node {
        int data;
        Node ref;
        Node(int data) {
            this.data = data;
            this.ref = null;
        }
    }
    public void push(int data) {
        Node newnode = new Node(data);
        if (head == null) {
            tail = head = newnode;
            return;
        }
        newnode.ref = head;
        head = newnode;
    }
    public void append(int data) {
        // O(1)
        Node newnode = new Node(data);
        if (tail == null) {
            tail = head = newnode;
            return;
        }
        tail.ref = newnode;
        tail = newnode;
    }
    
    public void p() {
        if (head == null) {
            System.out.println("Empty");
        }
        Node curr = head;
        while (curr!=null) {
            System.out.print(curr.data + "==>");
            curr = curr.ref;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        PractGG l = new PractGG();
        l.append(1);
        l.append(2);
        l.append(3);
        l.p();
    }
}