In this doubly linked list program in C blog, we will explore the fundamentals of doubly linked lists, their algorithms, and examples, as well as some typical operations that can be done on them.
Here is a C Programming video by Intellipaat to help you learn from scratch
Watch this Video on C Tutorial for Beginners
What is a Doubly Linked List?
A doubly linked list is a kind of linked list in which each node has two pointers or references: one to the previous node in the sequence and one to the next node in the series. This enables the traversal of the list in both forward and backward directions.
In a doubly linked list, the first node is connected to a NULL reference in the previous pointer because there is no node before it. And the final node is connected to a NULL reference in the next pointer because there is no node after it. Each node in the list contains a data element as well as two pointers to the previous and next nodes in the sequence.
Doubly linked lists are handy data structures for implementing lists, queues, and stacks, among other data structures. They have various advantages over singly-linked lists, including the ability to traverse the list in both ways, which makes them efficient for some algorithms. Nevertheless, because of the extra pointer in each node, they require more memory than singly-linked lists.
Here is a doubly linked list Structure syntax:
struct node.
{
struct node *prev;
int data;
struct node *next;
}
Algorithm for Doubly Linked List in C
Here is the coding algorithm for the doubly linked list program in C:
struct node {
int data;
struct node* next;
struct node* prev;
};
struct node* head = NULL;
struct node* tail = NULL;
// create a new node with the given data and return a pointer to it
struct node* create_node(int data) {
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
new_node->prev = NULL;
return new_node;
}
// insert a node at the beginning of the list
void insert_at_head(int data) {
struct node* new_node = create_node(data);
if (head == NULL) {
head = new_node;
tail = new_node;
} else {
new_node->next = head;
head->prev = new_node;
head = new_node;
}
}
// insert a node at the end of the list
void insert_at_tail(int data) {
struct node* new_node = create_node(data);
if (tail == NULL) {
head = new_node;
tail = new_node;
} else {
new_node->prev = tail;
tail->next = new_node;
tail = new_node;
}
}
// delete the node at the beginning of the list
void delete_at_head() {
if (head == NULL) {
return;
}
struct node* temp = head;
if (head == tail) {
head = NULL;
tail = NULL;
} else {
head = head->next;
head->prev = NULL;
}
free(temp);
}
// delete the node at the end of the list
void delete_at_tail() {
if (tail == NULL) {
return;
}
struct node* temp = tail;
if (head == tail) {
head = NULL;
tail = NULL;
} else {
tail = tail->prev;
tail->next = NULL;
}
free(temp);
}
// display the list in forward direction
void display_forward() {
struct node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("n");
}
// display the list in backward direction
void display_backward() {
struct node* current = tail;
while (current != NULL) {
printf("%d ", current->data);
current = current->prev;
}
printf("n");
}
// main function to test the doubly linked list
int main() {
insert_at_head(1);
insert_at_head(2);
insert_at_tail(3);
display_forward(); // expected output: 2 1 3
display_backward(); // expected output: 3 1 2
delete_at_head();
delete_at_tail();
display_forward(); // expected output: 1
display_backward(); // expected output: 1
return 0;
}
Output:
________________________________________
2 1 3
3 1 2
1
1
________________________________________
Circular Doubly Linked List in C
A circular doubly linked list in C is a data structure that consists of a collection of nodes, where each node contains a data element and two pointers, one that points to the next node and another that points to the previous node. The circular doubly linked list is called “circular” because the last node in the list points back to the first node, creating a loop.
A circular doubly linked list is a data structure similar to a doubly linked list, except that the last node in the list refers back to the first node, forming a loop. This implies you can go through the list in both directions, from beginning to end and end to beginning.
The circular doubly linked list is made up of nodes, each of which has a data element and two pointers, one pointing to the next node and the other pointing to the previous node. The following figure depicts the construction of a circular doubly linked list:
Each node in the list, as shown in the figure, contains two pointers, one pointing to the previous node and one pointing to the next node. The circular loop is formed by the first node’s “prev” pointer pointing to the last node and the final node’s “next” pointer pointing to the first node.
Some of the operations that may be performed on a circular doubly linked list are as follows:
Insertion
To add a new node to a circular doubly linked list, construct a new node, set its data element, and then update the pointers of the nodes around it to include the new node. To insert a new node at the beginning of the list, for example, set the new node’s “prev” reference to the last node in the list and its “next” pointer to the current first node in the list. The last node’s “next” pointer would then be updated to refer to the new node, as would the first node’s “prev” pointer.
Deletion
To remove a node from a circular doubly linked list, adjust the pointers of the nodes around it to skip over the node you wish to remove. For example, if you wish to delete a node in the midst of the list, you would alter the previous node’s “next” reference to link to the next node, and the next node’s “prev” value to point to the prior node.
Traversal
To traverse a circular doubly linked list, start at any node and then follow the “next” pointers to travel ahead or the “prev” points to move backward. You can keep going down the list until you get back to the beginning.
Searching
To find a specific node in a circular doubly linked list, start at any node and compare its data element to the value you’re looking for. You’ve located the node if the data element matches. If the data element does not match, you can advance to the next node and retry the comparison by following the “next” or “prev” pointers.
Algorithm for Circular Doubly Linked List in C
In C, here’s a method for creating a circular doubly linked list:
- Specify the structure of a list node.
- Declare a variable to maintain track of the list’s head node.
- Create a new node by implementing a function.
- Create a function to add a new node to the list.
- Create a function to remove a node from the list.
- Create a function that traverses the list.
- Create a function that searches the list for a node.
Here’s some C code that implements a circular doubly linked list using these algorithms:
// Define the node structure for the circular doubly linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// Function to create a new node with the given data
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// Function to insert a new node into the circular doubly linked list
void insertNode(struct Node** head, struct Node* newNode) {
if (*head == NULL) {
*head = newNode;
newNode->next = newNode;
newNode->prev = newNode;
return;
}
struct Node* last = (*head)->prev;
newNode->next = *head;
(*head)->prev = newNode;
newNode->prev = last;
last->next = newNode;
*head = newNode;
}
// Function to delete a node from the circular doubly linked list
void deleteNode(struct Node** head, struct Node* nodeToDelete) {
if (*head == NULL)
return;
if (*head == nodeToDelete)
*head = (*head)->next;
nodeToDelete->prev->next = nodeToDelete->next;
nodeToDelete->next->prev = nodeToDelete->prev;
free(nodeToDelete);
}
// Function to traverse the circular doubly linked list
void traverseList(struct Node* head) {
if (head == NULL)
return;
struct Node* current = head;
do {
printf("%d ", current->data);
current = current->next;
} while (current != head);
printf("n");
}
// Function to search for a node with the given data in the circular doubly linked list
struct Node* searchList(struct Node* head, int searchKey) {
if (head == NULL)
return NULL;
struct Node* current = head;
do {
if (current->data == searchKey)
return current;
current = current->next;
} while (current != head);
return NULL;
}
int main() {
struct Node* head = NULL;
// Insert nodes into the circular doubly linked list
insertNode(&head, createNode(1));
insertNode(&head, createNode(2));
insertNode(&head, createNode(3));
// Traverse the circular doubly linked list
printf("The circular doubly linked list is: ");
traverseList(head);
// Delete a node from the circular doubly linked list
struct Node* nodeToDelete = searchList(head, 2);
deleteNode(&head, nodeToDelete);
// Traverse the circular doubly linked list after deletion
printf("The circular doubly linked list after deletion is: ");
traverseList(head);
return 0;
}
Output:
________________________________________
The circular doubly linked list is: 3 2 1
The circular doubly linked list after deletion is: 3 1
________________________________________
Conclusion
To summarize, doubly linked lists are a strong data structure that provides rapid access to both the previous and next members in the list. They have various advantages over singly-linked lists, including simpler implementation of operations like deletion and insertion at random points in the list. Nevertheless, doubly-linked lists use more memory than singly-linked lists and may be less efficient in terms of space utilization.
We hope this article helped you comprehend the concept of a doubly linked list in C. If you have any further queries, please post them on our .