Top List List

Doubly circular linked list in C

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a doubly circular linked list and a Key. We have to delete the first occurrence of this Key in the list.

Problem Statement Understanding

Suppose the given circular doubly linked list is:

and the key is 2. So, we have to find the node with the value 2 and delete it.

The final linked list will be:

Input
The given Doubly Circular Linked List.

Key** - 2

Output
The final Doubly Circular Linked List after deletion:

Explanation: As we can see, the first occurrence of key - 2 is deleted from the doubly circular linked list.

This question is not a very complex one. We just have to keep in mind that this is a circular as well as a doubly-linked list. During the deletion, we have to take special care of the link changing part. Let us have a glance at the approach.

Approach

Firstly, we will check if the given list is empty or not. If it is empty, then we will simply return it.

Now, we will create two pointers current and previous. The current pointer will point to the head of the list and the previous pointer will point to NULL. Now, we are going to traverse through the list using the current pointer till we find the node that is to be deleted.

If the node is found, then we have three cases:
1] If the node is the head node, then we will delete it, make the second node as head and the last node will now point to the new head.
2] If the node is the last node, then we will remove the tail node, and make the second last node the tail node. Now, the new tail node will point to the head node.
3] If the node is neither the head nor the tail of the list, then we will simply delete the node by changing links.

Algorithm

If the list is empty, return.
If the list is not empty, create two nodes, say, current and previous. Current will point to the head and previous will point to NULL.
Traverse using the current pointer to find the node that is to be deleted. In every traversal, we have to make the current as previous as this is a doubly circular linked list.
Now, if the node is found but is the only node present in the list, then we will make the head NULL and return.
If the found node is the head node i.e. if [ current==head ], move previous to the last node. Now, do head = head -> next. The node has been deleted successfully, but now, the last node will point to the new head and to do so make prev -> next = head and head -> prev = previous. By doing this, all the required links have been changed. In the end, free the node pointed by the current.
If the found node is the tail node i.e. if [ current -> next == head ], then the second last node will now point to the head node and to do so make previous -> next = head and head ->prev = previous. By doing this, the links have been successfully changed. In the end, free the node pointed by the current.
If the found node is neither the first nor the last, then we will simply store the next of current in temp. Now, the previous will point to the temp and the prev of temp will point to the previous. In the end, free the node pointed by the current.

Dry Run

Code Implementation

C++
Java

#include using namespace std; struct Node { int data; struct Node* next; struct Node* prev; }; void insert[struct Node** start, int value] { if [*start == NULL] { struct Node* new_node = new Node; new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } Node* last = [*start]->prev; struct Node* new_node = new Node; new_node->data = value; new_node->next = *start; [*start]->prev = new_node; new_node->prev = last; last->next = new_node; } void deleteNode[struct Node** start, int key] { if [*start == NULL] return; struct Node *curr = *start, *prev_1 = NULL; while [curr->data != key] { if [curr->next == *start] { printf["\nList doesn't have node with value = %d", key]; return; } prev_1 = curr; curr = curr->next; } if [curr->next == *start && prev_1 == NULL] { [*start] = NULL; free[curr]; return; } if [curr == *start] { prev_1 = [*start]->prev; *start = [*start]->next; prev_1->next = *start; [*start]->prev = prev_1; free[curr]; } else if [curr->next == *start] { prev_1->next = *start; [*start]->prev = prev_1; free[curr]; } else { struct Node* temp = curr->next; prev_1->next = temp; temp->prev = prev_1; free[curr]; } } void display[struct Node* start] { struct Node* temp = start; while [temp->next != start] { printf["%d ", temp->data]; temp = temp->next; } printf["%d ", temp->data]; } int main[] { struct Node* start = NULL; insert[&start, 1]; insert[&start, 2]; insert[&start, 3]; insert[&start, 4]; printf["List Before Deletion: "]; display[start]; deleteNode[&start, 2]; printf["\nList After Deletion: "]; display[start]; return 0; }

public class PrepBytes { static class Node { int data; Node next; Node prev; }; static Node insert[Node start, int value] { if [start == null] { Node new_node = new Node[]; new_node.data = value; new_node.next = new_node.prev = new_node; start = new_node; return start; } Node last = [start].prev; Node new_node = new Node[]; new_node.data = value; new_node.next = start; [start].prev = new_node; new_node.prev = last; last.next = new_node; return start; } static Node deleteNode[Node start, int key] { if [start == null] return null; Node curr = start, prev_1 = null; while [curr.data != key] { if [curr.next == start] { System.out.printf["\nList doesn't have node with value = %d", key]; return start; } prev_1 = curr; curr = curr.next; } if [curr.next == start && prev_1 == null] { [start] = null; return start; } if [curr == start] { prev_1 = [start].prev; start = [start].next; prev_1.next = start; [start].prev = prev_1; } else if [curr.next == start] { prev_1.next = start; [start].prev = prev_1; } else { Node temp = curr.next; prev_1.next = temp; temp.prev = prev_1; } return start; } static void display[Node start] { Node temp = start; while [temp.next != start] { System.out.printf["%d ", temp.data]; temp = temp.next; } System.out.printf["%d ", temp.data]; } public static void main[String args[]] { Node start = null; start = insert[start, 1]; start = insert[start, 2]; start = insert[start, 3]; start = insert[start, 4]; System.out.printf["List Before Deletion: "]; display[start]; start = deleteNode[start, 2]; System.out.printf["\nList After Deletion: "]; display[start]; } }

Output

List Before Deletion: 1 2 3 4
List After Deletion: 1 3 4

Let us check your understanding!!

Think before you answer

What is the Time complexity for this algorithm? O[n] O[1] O[m] None of these

Space Complexity: O[1], as only temporary variables are being created.

So, in this article, we have tried to explain the most efficient approach to delete a node in a doubly circular linked list. The question isnt a complex one, but the link changing part is a bit tricky. Hence, it is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Introduction

Problem Statement

Problem Statement Understanding

Approach

Algorithm

Dry Run

Code Implementation

Output

Let us check your understanding!!

Video liên quan

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề