Implement an algorithm to insert a node into a circular linked list without traversing it.

Question

I was thinking of a solution to this problem.

My input:
1. Have a tail pointer which points to the last node.
2. Once you know the last pointer you can easily add a new node next to it.

Void Insert(Node N)
{  
    if (head == null) // linked list is empty
    {
       head = N; tail = N; tail.Next = head;
    } 
    else
    {        
      Node temp = tail.Next; // since this is circular tail will point to head
      Tail.Next = N;
      N.Next = temp; // correct 
      tail = N;       
    }
}

Can any1 think of better solution without using tail pointer? Also as stated in problem without traversing? This is an interview question, just need some inputs to find the best solution.

Answer 1

Nope, you need the tail pointer. Otherwise you will have to traverse the list. How else would you know where the list ends.

You could come up with some sort of clever indexing arithmetic, but it would still be a pointer to the head/tail.

Answer 2

you also have the head node. you can insert using it too. I am assuming there is no restriction on where to insert the new node (question doesnt explicitly specify that).

Inserting it on head is trivial.

Edit Insert it after the head

Answer 3

If your measure of "better" is to not maintain both the head and tail pointers, you could instead just maintain the tail pointer. The head pointer is implicit (given by tail.Next).

In practice, access to a list is often quite common (say if you are using the circular list as a queue), and having an extra step to access the head can add some overhead. In a test for a project I did, eliminating the head pointer in this way lowered the memory some (our lists were typically short, but we had many of them), but the time increased since we often accessed the head of the list. YMMV.

Answer 4

I guess that you have a singly linked circular list, and only a pointer to one element (call this the head node). Each node of the list thus consists of a value and a pointer to the next element. The tail node points to the head node. Inserting a node directly after the head node is trivial. I guess that you want to insert a node directly before the head node. For that, you need the new node to become the last node, which is pointed to from the former last node, and which points to the head node. Now, you want to avoid traversing the list to find the last node. This means that you cannot access that last node and thus, not modify its pointer. The only other way to make this work is to modify the place that last node points to, i.e.:

1. insert a new node after the head node
2. copy the current head node's value to that new node
3. put the new value into the current head node
4. make the new node the new head node

Answer 5

I've simplified your code a bit. No need for the temp variable, you did't even use it for anything after you set it.

Void Insert(Node N) {  
    if (head == null) { // linked list is empty
       head = tail = N;
    } 
    else { // insert after tail
      tail.Next = N;
      tail = N;       
    }
    tail.Next = head;
}

Answer 6

Instead of storing the head and the tail, just store the tail.

Void Insert(Node N)
{  
    if (tail == null) // linked list is empty
    {
       tail = N.Next = N;
    } 
    else
    {
      N.Next = tail.Next;
      tail = tail.Next = N;
    }
}
Node Head() { return tail == null ? null : tail.next; }