DOUBLY LINKED LIST
A Doubly linked list is a dynamic data structure where each node contains three parts:
1. Data: The value stored in the node.
2. Next Pointer (`next`): Points to the next node in the sequence.
3. Previous Pointer (`prev`): Points to the previous node in the sequence.
This bidirectional linkage allows traversal in both forward and backward directions, offering more flexibility compared to singly linked lists.
Review of Your Implementation:
Your implementation includes the following operations:
1. Insertion at the Beginning
2. Insertion at the End
3. Insertion at a Specified Location
4. Deletion from the Beginning
5. Deletion from the End
6. Deletion After a Node with Given Data
7. Searching for an Element
8. Displaying the List
Overall, the structure is solid, but there are a few areas where the code can be improved for correctness, efficiency, and adherence to best practices.
Identified Issues and Improvements:
1. Function: `insertion_specified`
- Issue:
1. Incorrectly updating the `prev` pointer after insertion.
2. Potential segmentation fault if inserting at the end of the list.
2. Potential segmentation fault if inserting at the end of the list.
- Original Code Snippet:
ptr->next = temp->next;
ptr->prev = temp;
temp->next = ptr;
temp->next->prev = ptr; // Incorrect
- Improvement:
1.Update the `prev` pointer of the node that comes after the newly inserted node only if it exists.
- Corrected Code Snippet:
ptr->next = temp->next;
ptr->prev = temp;
if(temp->next != NULL) {
temp->next->prev = ptr;
}
temp->next = ptr;
2. Function: `deletion_last`
- Issue:
1.The current implementation only moves `ptr` one node ahead, which doesn't necessarily reach the last node.
- Original Code Snippet:
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr->prev->next = NULL;
free(ptr);
- Improvement:
1.Traverse the list until the last node is reached.
- Corrected Code Snippet:
ptr = head;
if(ptr == NULL) {
printf("\n UNDERFLOW");
return;
}
while(ptr->next != NULL) {
ptr = ptr->next;
}
if(ptr->prev != NULL) {
ptr->prev->next = NULL;
} else { // List had only one node
head = NULL;
}
free(ptr);
printf("\nNode deleted\n");
3. Function: `search`
- Issue:
- The `flag` variable is used without initialization, which can lead to undefined behavior.
- Original Code Snippet:
int item,i=0,flag;
...
if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
...
if(flag==1)
{
printf("\nItem not found\n");
}
- Improvement:
- Initialize `flag` to `1` (assuming the item is not found) before starting the search.
- Only set `flag` to `0` when the item is found.
- Corrected Code Snippet:
int item, i = 0, flag = 1;
...
if(ptr->data == item)
{
printf("\nItem found at location %d\n", i+1);
flag = 0;
break;
}
i++;
...
if(flag == 1)
{
printf("\nItem not found\n");
}
4. Function: `main` Declaration
- Issue:
Using `void main()` is not standard-compliant in C.
- Original Code Snippet:
void main ()
{
...
}
- Improvement:
Change the return type to `int` and return `0` at the end to indicate successful execution.
- Corrected Code Snippet:
int main ()
{
...
return 0;
}
5. General Improvements
- Memory Leak Prevention: Ensure all dynamically allocated memory is freed before program termination.
- Input Validation: alidate user inputs to prevent undefined behavior (e.g., inserting at invalid locations).
- Consistent Formatting: Maintain consistent indentation and formatting for better readability.
Revised and Corrected Code:
Below is the revised version of your doubly linked list implementation incorporating the above corrections and improvements:
#include <stdio.h>
#include <stdlib.h>
struct node {
struct node *prev;
int data;
struct node *next;
} *head = NULL;
// Function Prototypes
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
int main() {
int choice = 0;
while(choice != 9) {
printf("\n*********Main Menu*********\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at Last\n");
printf("3. Insert at Any Location\n");
printf("4. Delete from Beginning\n");
printf("5. Delete from Last\n");
printf("6. Delete the Node After Given Data\n");
printf("7. Search\n");
printf("8. Show\n");
printf("9. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
// Free all nodes before exiting
while(head != NULL) {
deletion_beginning();
}
printf("\nExited..\n");
break;
default:
printf("Please enter a valid choice..\n");
}
}
return 0;
}
void insertion_beginning() {
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL) {
printf("\nOVERFLOW\n");
}
else {
printf("Enter Item value: ");
scanf("%d", &item);
ptr->data = item;
ptr->prev = NULL;
ptr->next = head;
if(head != NULL) {
head->prev = ptr;
}
head = ptr;
printf("\nNode inserted at the beginning\n");
}
}
void insertion_last() {
struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL) {
printf("\nOVERFLOW\n");
}
else {
printf("Enter value: ");
scanf("%d", &item);
ptr->data = item;
ptr->next = NULL;
if(head == NULL) {
ptr->prev = NULL;
head = ptr;
}
else {
temp = head;
while(temp->next != NULL) {
temp = temp->next;
}
temp->next = ptr;
ptr->prev = temp;
}
printf("\nNode inserted at the end\n");
}
}
void insertion_specified() {
struct node *ptr, *temp;
int item, loc, i;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL) {
printf("\nOVERFLOW\n");
}
else {
printf("Enter the location after which you want to insert: ");
scanf("%d", &loc);
temp = head;
for(i = 0; i < loc; i++) {
if(temp == NULL) {
printf("\nThere are less than %d elements\n", loc);
free(ptr);
return;
}
temp = temp->next;
}
if(temp == NULL) {
printf("\nCannot insert at the specified location\n");
free(ptr);
return;
}
printf("Enter value: ");
scanf("%d", &item);
ptr->data = item;
ptr->next = temp->next;
ptr->prev = temp;
if(temp->next != NULL) {
temp->next->prev = ptr;
}
temp->next = ptr;
printf("\nNode inserted at the specified location\n");
}
}
void deletion_beginning() {
struct node *ptr;
if(head == NULL) {
printf("\nUNDERFLOW\n");
}
else {
ptr = head;
head = head->next;
if(head != NULL) {
head->prev = NULL;
}
printf("\nNode deleted from the beginning\n");
free(ptr);
}
}
void deletion_last() {
struct node *ptr;
if(head == NULL) {
printf("\nUNDERFLOW\n");
}
else {
ptr = head;
if(ptr->next == NULL) { // Only one node
head = NULL;
}
else {
while(ptr->next != NULL) {
ptr = ptr->next;
}
ptr->prev->next = NULL;
}
printf("\nNode deleted from the end\n");
free(ptr);
}
}
void deletion_specified() {
struct node *ptr, *temp;
int val;
if(head == NULL) {
printf("\nList is empty\n");
return;
}
printf("Enter the data after which the node is to be deleted: ");
scanf("%d", &val);
ptr = head;
while(ptr != NULL && ptr->data != val) {
ptr = ptr->next;
}
if(ptr == NULL) {
printf("\nData not found in the list\n");
return;
}
if(ptr->next == NULL) {
printf("\nNo node exists after the given data to delete\n");
return;
}
temp = ptr->next;
ptr->next = temp->next;
if(temp->next != NULL) {
temp->next->prev = ptr;
}
printf("\nNode deleted after the given data\n");
free(temp);
}
void display() {
struct node *ptr;
if(head == NULL) {
printf("\nList is empty\n");
return;
}
printf("\nPrinting values...\n");
ptr = head;
while(ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
printf("\n");
}
void search() {
struct node *ptr;
int item, i = 0, flag = 1;
if(head == NULL) {
printf("\nEmpty List\n");
return;
}
printf("Enter item which you want to search: ");
scanf("%d", &item);
ptr = head;
while(ptr != NULL) {
if(ptr->data == item) {
printf("\nItem found at location %d\n", i+1);
flag = 0;
break;
}
i++;
ptr = ptr->next;
}
if(flag == 1) {
printf("\nItem not found\n");
}
}
Key Enhancements in the Revised Code:
1. Corrected `insertion_specified` Function:
Ensures that the `prev` pointer of the node following the inserted node is correctly updated.
Handles insertion at the end of the list gracefully.
2. Improved `deletion_last` Function:
Properly traverses to the last node before deletion.
Handles the scenario where the list has only one node.
3. Safe `search` Function:
Initializes the `flag` variable to prevent undefined behavior.
Provides clear output based on whether the item is found.
4. Standard-Compliant `main` Function:
Changed from `void main()` to `int main()` and added a `return 0;` statement.
5. Memory Leak Prevention:
Added a loop in the `main` function to delete all nodes before exiting, ensuring no memory leaks.
6. User Input Validation:
Added checks to handle cases where the specified location for insertion or deletion doesn't exist.
7. Consistent and Clear Output Messages:
Enhanced user prompts and output messages for better clarity and user experience.
Sample Output
Here's how the revised program behaves, similar to the output you provided:
*********Main Menu*********
1. Insert at Beginning
2. Insert at Last
3. Insert at Any Location
4. Delete from Beginning
5. Delete from Last
6. Delete the Node After Given Data
7. Search
8. Show
9. Exit
Enter your choice: 1
Enter Item value: 12
Node inserted at the beginning
*********Main Menu*********
