write a c code to implement it. You also need to code for insertion (at start, at end, at a specific position), deletion (at start, at end, at node) and display operation.

Question

a doubly circular linked list data structure

Answer 1

Hello Xiana!

So, this is a rather in-depth piece of code, and would take up a lot of space here; however, I can certainly help get you on the right track.

Firstly, comes the data definition. You will need a struct that represents each node in the linked list. Because it is double linked, it will have not one but two pointers, as well as the data it holds. If, for example, it is holding integers, it would look like this:

struct Node {

struct Node* next;

struct Node* prev;

int val;

};

typedef struct Node Node;

Note: You could wrap the struct Node definition with the type def (i.e. typedef struct Node {...} Node;); however, I've kept them separate for clarification.

Insertion and deletion are operations that are relatively easy when you understand the use of a linked list. For example, in the case of the Node at the very end of the list, what would it's "next" value be? The answer is NULL.

So, if that is the case, how could you get to the very end of the double-linked list? Well, you could have a Node* that is originally equal to the first Node in the list, and move it forward until that Node*'s "next" value would be NULL. That would mean that the current Node it is on is the end of the list! Then, you could set it's "next" value to be the new Node (in the case of insertion). You would also set that new node's previous ptr to point to the old end-of-list. Here is an example:

void insertAtEnd(Node* root, int val)

{

Node* ptr = root;

Node* new_node = malloc(sizeof(Node));

new_node->next = NULL;

new_node->val = val;

while (ptr->next != NULL)

ptr = ptr->next;

ptr->next = new_node;

new_node->prev = ptr;

}

Note: I set the ->next value to be NULL. This is important, as otherwise ->next is some undefined value, which can lead to undefined behavior.

In the case of insertion, it's a matter of deleting this node with free, and setting the ->next pointer that pointed to it to be NULL. This would mean using something fancy like ptr->prev->next = NULL then calling free(ptr);

Please feel free to reach out if you need more help with this assignment :)