Program No.
02
Objective:- Write a program that uses functions to perform the
following operations on doubly linked list (i) Creation (ii) Insertion
(iii) Deletion (iv) Traversal.
Algorithm for Doubly Linked List Operations:-
(i) Creation (createList):
Input : Data Value
Output : A new Node created
Steps:
1. Start
2. Allocate memory for a new node
3. Store the given data in data field
4. Set prev = NULL and next = NULL
5. Return the newly created node
6. Stop
(ii) Insertion :
(ii) a. Insertion at Beginning :-
Input: Value to be Inserted
Output: Node inserted at beginning of the list
Steps:
1. Start
2. Create a new node with the given value
3. If the list is empty (head == NULL), set head = newNode
4. Else:
o Set newNode->next = head
o Set head->prev = newNode
o Update head = newNode
5. Stop
(ii) b. Insertion at End:
Input: Value to be inserted
Output: Node inserted at the end of the list Steps:
1. Start
2. Create a new node with the given value
3. If the list is empty (head == NULL), set head = newNode
4. Else:
o Traverse the list until the last node (temp->next == NULL)
o Set temp->next = newNode
o Set newNode->prev = temp
5. Stop
(iii) Deletion of a Node (By Value):
Input: Value to be deleted Output:
Node deleted if found Steps:
1. Start
2. If list is empty (head == NULL), print "List is empty" and Stop
3. Traverse the list to find the node with given value
4. If node not found, print "Value not found" and Stop
5. If node is found:
o If it is the first node, update head = head->next and set head->prev = NULL
o Else if it is the last node, update temp->prev->next = NULL
o Else (middle node):
Update temp->prev->next = temp->next
Update temp->next->prev = temp->prev
o Free the memory of temp
6. Stop
(iv) Traversal:
(iv) a. Traversal (Forward):
Input: None
Output: Display list from head to tail Steps:
1. Start
2. Set temp = head
3. While temp != NULL
o Print temp->data
o Move temp = temp->next
4. Stop
(iv) b. Traversal (Backward):
Input: None
Output: Display list from tail to head Steps:
1. Start
2. Set temp = head
3. Traverse to the last node (while temp->next != NULL)
4. While temp != NULL
o Print temp->data
o Move temp = temp->prev
5. Stop
Code:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
// Structure for a doubly linked list node
struct Node
{ int data;
struct Node* prev; struct
Node* next;
};
struct Node* head = NULL;
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
// Insert at end
void insertAtEnd(int value) {
struct Node* newNode = createNode(value); if
(head == NULL) {
head = newNode; return;
}
struct Node* temp = head; while
(temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
// Insert at beginning
void insertAtBeginning(int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
head = newNode;
return;
}
newNode->next = head;
head->prev = newNode;
head = newNode;
// Delete a node by value
void deleteNode(int value) {
struct Node* temp = head;
while (temp != NULL && temp->data != value)
{ temp = temp->next;
if (temp == NULL) {
printf("Node with value %d not found.\n", value);
return;
}
if (temp->prev != NULL) {
temp->prev->next = temp->next;
} else {
head = temp->next; // deleting first node
}
if (temp->next != NULL) {
temp->next->prev = temp->prev;
}
free(temp);
printf("Node with value %d deleted successfully.\n", value);
// Traversal (Display list forward)
void displayForward()
{ struct Node* temp =
head;
printf("Doubly Linked List (Forward): ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
// Traversal (Display list backward)
void displayBackward() {
if (head == NULL) {
printf("List is empty.\
n"); return;
}
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
printf("Doubly Linked List (Backward): ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}
// Main function (Menu driven)
void main() {
int choice, value;
clrscr(); // clear screen (Turbo C++ feature)
while (1) {
printf("\n---- Doubly Linked List Menu----\n");
printf("1. Insert at Beginning\n");
printf("2. Insert at End\n");
printf("3. Delete a Node\n");
printf("4. Display Forward\n");
printf("5. Display Backward\n");
printf("6. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtBeginning(value);
break;
case 2:
printf("Enter value to insert: ");
scanf("%d", &value);
insertAtEnd(value);
break;
case 3:
printf("Enter value to delete: ");
scanf("%d", &value);
deleteNode(value);
break;
case 4:
displayForward();
break;
case 5:
displayBackward();
break;
case 6:
printf("Exiting program...\n");
getch();
exit(0);
default:
printf("Invalid choice! Try again.\n");
}
}
getch(); // wait for a key press before closing
}
Output: