Geek Answers Handbook

Implement an algorithm to insert a node into a circular linked list without going through it

I was thinking about solving this problem.

My input:
1. Have a tail pointer pointing 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 you think of a better solution without using a tail pointer? Also as indicated in the problem without going through? This is an interview question, some materials are just needed to find the best solution.

+4
source share
6 answers

I assume that you have one linked circular list and only a pointer to one element (call it head node). Each node of the list, therefore, consists of a value and a pointer to the next element. The tail of the node points to the head of the node. Inserting a node immediately after the head of a node is trivial. I assume that you want to insert a node directly in front of the node head. To do this, you will need a new node to become the last node that the previous last node points to and that points to the head of the node. Now you want to avoid moving the list to find the last node. This means that you cannot access the last node and therefore do not change its pointer. The only way to do this work is to change the location that the last node points to, i.e.:

  • insert new node after node header
  • copy the current value of the head of a node to a new node
  • add a new value to the current head node
  • create new node new node header
+13
source

you also have a head node. You can also insert it. I assume that there are no restrictions on where to insert the new node (the question does not explicitly indicate this).

Inserting it on the head is trivial.

Edit Insert it after the head

+1
source

If your measure of “better” is to not support pointers to the head and tail, instead you can just maintain pointers to the tail. The chapter pointer is implicit (given by the tail. Next).

In practice, access to the list is often quite common (say, if you use a circular list as a queue), and an extra step to access the head can add some overhead. In the test for the project I did, removing the head pointer in this way reduced memory (our lists were usually short, but we had a lot of them), but the time has increased since we often turned to the head of the list. YMMV.

+1
source

No, you need a pointer to the tail. Otherwise, you have to cross the list. How else do you know where the list ends.

You can come up with some kind of smart indexing arithmetic, but it will still be a pointer to the head / tail.

0
source

I simplified your code a bit. There is no need for the temp variable, you didn’t even use it for anything after setting 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; }
0
source

Instead of storing the head and 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; }
0
source

More articles:


All Articles