I have one question in my mind that in case of circular doubly linked list the head pointer of the doubly linked list also logically point to the next pointer of the tail node of the linked list and tail’s next pointer also point to the previous pointer of head.
Please Answer me this question I am a bit confused.
1
It depends.
Is it a circular or linear list?
If it’s a circular list then there is no “head” or “tail” as each element’s next and prev pointers will be set. You can start traversing the list anywhere and have to remember where you started so you know when to stop.
If it’s a linear list then the prev pointer of the head element will be null and the next pointer of the tail element will be null. You use this information to know when to stop.
Assume you have a circular doubly linked list with three nodes at position 1, 2 and 3:
[1] next->2 prev->3
[2] next->3 prev->1
[3] next->1 prev->2
In some sense there is no “head” and “tail” in a circular doubly linked list. Though you will have a pointer outside as an entry point to access the list like head->1, which would be identical to 3:next->1.
So the heads prev points to the “tail”
The tails next points to the “head”
1
I’ve used a circular doubly linked list like this:
typedef struct List {
struct List *next;
struct List *prev;
void *data;
} List;
I decided to define the head of a List as one that has data == NULL. So an empty List is one where next and prev point to itself and data == NULL. You can then insert before or after the head at will. You can iterate the list by starting at head->next and going till you hit head again.
And here is the fun part: You can have multiple heads. Nothing prevents you from inserting a second List with data == NULL. Now there are two ways to iterate over the list: You can iterate till you hit the next head (data == NULL) or skip over heads and keep going till you hit the original head again.