which one is right. Also pleasse explain in few words.

Question

. Consider an implementation of unsorted circular linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?

1. Insertion at the front of the linked list
2. Insertion at the end of the linked list
3. Deletion of the front node of the linked list
4. Deletion of the end node of the linked list

(a) I and II                                                                   (b) I and III

(c) I, II, III and IV                                                       (d) None

Comments

Its hard to say anything right now, I will need some time.

---

To me its B)

---

answer should be d)none

Answer 1

Option B:

There is a concept of Sentinel node(a dummy node to which the last node will point to).

Address of Sentinel node is stored in head pointer. 

So when we want to delete a node from front we do

1. struct  node * temp=head->next; // gives the address of first node.
2. head->next=head->next->next;// moving the address of second node to address field of Sentinel node
3. //The data part of sentinel node is generally used to maintain count . In this line head->data=head->data - 1;
4. free(temp);// freeing up the first node space

So we can delete first node in constant time O(1).

we can add new node in O(1).

• create new node
• move address part of sentinel node to address part of newly created node.
• move the address of newly created node to address part of sentinel node and increment the count in sentinel node.

Ref below for sentinel node:

https://www.quora.com/What-is-the-sentinel-node-in-a-circular-linked-list