Lab Assignment-02
Submitted to:
Somonindro Roy
Lecturer
Department of Computer Science and Engineering
ULAB School of Science & Engineering
University of Liberal Arts Bangladesh
Submitted by:
Name: Eusha Mohtasim
ID: 241014028
Course Title: Data structures Lab
Course Code: CSE1302
Section: 01
Date of Submission: 11 November 2024
Title: Linked List Deletion
Objective: To implement deletion function for Doubly Linked Lists
(DLL) and gain an understanding of their time complexities. As a
bonus task, implement an deletion function for a Singly Circular
Linked List (SCLL).
Tools Used:
1. Language: C
2. Compiler: GCC
3. IDE: CodeBlocks
Theory:
A doubly linked list is type of linked list where each node contains
three fields.
1. Data: Stores the data of different types like
int,float,char,double.
2. Left Pointer: Points to the previous node.
3. Right Pointer: Points to the next node.
A doubly linked list allows traversal in both forward and backward
directions, making certain operations more efficient.
Tasks:
Program Code
#include<stdio.h>
#include<stdlib.h>
//structure of a node
struct node{
struct node* left;
int data;
struct node* right;
};
struct node* head = NULL; //global variable
//creating node
void createnode(){
struct node* temp;
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter the node data: ");
scanf("%d",&temp->data);
temp->left = NULL;
temp->right = NULL;
if(head==NULL){
head=temp;
}
else{
struct node*p;
p=head;
while(p->right!=NULL){
p=p->right;
}
p->right = temp;
temp->left = p;
}
struct node* display = head;
while (display != NULL){
printf("%d-> ",display->data);
display= display->right;
}
printf("NULL\n");
}
//TASK-01: Deletion in doubly linked list
//delete node at begining
void deletenodeatbegin(){
struct node* temp;
temp = head;
head = temp->right;
temp->right=NULL;
free(temp);
struct node* display = head;
while (display != NULL){
printf("%d-> ",display->data);
display= display->right;
}
printf("NULL\n");
}
//delete node at the end
void deletenodeatend(){
struct node* temp;
if(head==NULL){
printf("NULL");}
else if(head->right==NULL){
head=NULL;
free(head);
}
else{temp = head;
while(temp->right!=NULL){
temp=temp->right;
}
temp->left->right=NULL;
temp->left=NULL;
free(temp);
}
struct node* display = head;
while (display != NULL){
printf("%d-> ",display->data);
display= display->right;
}
printf("NULL\n");
}
//delete node at a specific location
void deleteatanywhere() {
struct node* temp;
struct node* p;
int location;
printf("Enter the location: ");
scanf("%d", &location);
if (location == 1) {
temp = head;
head = temp->right;
temp->right = NULL;
free(temp);
} else {
p = head;
for (int i = 1; i < location - 1; i++) {
p = p->right;
}
temp = p->right;
if (temp == NULL) {
printf("Invalid location!\n");
return;
}
p->right = temp->right;
if (temp->right != NULL) {
temp->right->left = p;
}
temp->left = NULL;
temp->right = NULL;
free(temp);
}
struct node* display = head;
while (display != NULL){
printf("%d-> ",display->data);
display= display->right;
}
printf("NULL\n");
}
//TASK-02: Reversal of doubly linked list
void reverselist() {
struct node* current = head;
struct node* temp = NULL;
while (current != NULL) {
temp = current->left;
current->left = current->right;
current->right = temp;
current = current->left;
}
if (temp != NULL) {
head = temp->left;
}
struct node* display = head;
while (display != NULL){
printf("%d-> ",display->data);
display= display->right;
}
printf("NULL\n");
}
int main() {
int option;
printf("Doubly Linked List\n");
do {
printf("1. Create New Node\n");
printf("2. Delete node at beginning\n");
printf("3. Delete node at the end\n");
printf("4. Delete node in specific location in the list\n");
printf("5. Reverse the list\n");
printf("6. Exit\n");
printf("Enter the option:\n");
scanf("%d", &option);
switch (option) {
case 1:
createnode();
break;
case 2:
deletenodeatbegin();
break;
case 3:
deletenodeatend();
break;
case 4:
deleteatanywhere();
break;
case 5:
reverselist();
break;
case 6:
printf("Exited\n");
break;
default:
printf("Enter a correct option.\n");
break;
}
} while (option != 7);
return 0;
}
Time complexity Analysis:
Functions Best Case Worst Case Explanation
createnode() O(1) O(n) Adding the node at the
end requires traversal
deletenodeatbegi O(1) O(1) Only head pointer update
n() is needed.
dcreeletenodeaten O(1) O(n) Traversal required to find
d() the last node
deleteatanywhere O(1) O(n) Traversal needed to locate
() the specified node.
reverselist() O(n) O(n) Each node is visited once
to swap pointers.
Explanation of Approach:
1. createnode() Function:
This function create a node And it starts by dynamically allocating
memory for a new node using malloc(). The user is prompt to input
the data for that new node. If the list is empty( head = = NULL),
the new node is assigned as the head of the list. If the list is not
empty, a pointer (p) is initialized to traverse the list starting from the
head. The loop continues until the last node is reached(p ->right ==
NULL). The new node is appended at the end updating the right
pointer of the last node and the left pointer of the new node. The
challenges I faced during writing this code was handling the case
when the list is initially empty. The head pointer needs to be
correctly assigned while creating node. However this problem was
solved by adding a condition to check if head = = NULL and
setting the new node as head.
2. deletenodeatbegin() Function:
In this function We delete the first node. For doing this,first, we
check if the list is empty or not. If it is not empty It stores the head
node in a temporary variable, Update the head pointer to the second
node, and frees the memory of the original head node By using free
() function. The main challenge I faced in this function was properly
updating the head pointer when deleting the first node was critical
.However, ensuring the list does not become corrupted when the
first note is removed by addressed by setting temp-> right to NULL
before freeing it.
3.deletenodeatend() Function:
In this function,we delete the last node of the linked list. This
function first checks if the list is empty or has only one node if the
list has more than one node,it traverses to the last node and updates
the right pointer to the second last node to NULL. Then, finally it
free the last node by using free() function. The challenge is while
writing this function traversing the list without going out of bounds
was tricky, especially when deleting the only node in the list.
However,this challenge was overcome by checking if head-> right
== NULL And directly setting head to NULL.
4.deleteatanywhere() Function:
This functions successfully deletes a node at any valid location
specified by the user. In this function,the function first asks the user
to enter the location of the node to be deleted. To delete the node at
a specific location it traverses to the specific node and updates the
pointers to adjacent nodes to bypass the target node. Then it frees
that targeted node by using free() function.The challenges during
writing this code was handling invalid locations. However, this
problem was solved by checking if the location exceeds the length
of the list and displaying an error message.
5.reverselist() Function:
This function currently reverses the list, Allowing traversal in the
opposite direction. and traverses through the list and swaps the left
and right pointers of each node after reaching the end of the list, it
updates the head pointer to the last node. Here ensuring the head
pointer is correctly updated after the reversal. However, this
problem was solved by updating head to temp->left after the
traversal completes.
Bonus Task: Deletion in Singly Circular Linked List
Program code
#include<stdio.h>
#include<stdlib.h>
//structure of node
struct node{
int data;
struct node* next;
};
struct node* head = NULL; //Global Variable
//create new node
void createnewnode(){
struct node* temp;
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter the Node Data:");
scanf("%d",&temp->data);
temp->next = NULL;
if (head == NULL){
head = temp;
temp->next=head;
}
else{
struct node* p=head;
while(p->next!=head){
p=p->next;
}
p->next=temp;
temp->next=head;
}
if (head == NULL) {
printf("List is empty.\n");
return;
}
temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
//delete node at the begining
void deletenodeatbegin() {
if (head == NULL) {
printf("List is empty. Cannot delete.\n");
return;
}
struct node* temp = head;
if (temp->next == head) {
head = NULL;
free(temp);
return;
}
struct node* last = head;
while (last->next != head) {
last = last->next;
}
head = temp->next;
last->next = head;
free(temp);
if (head == NULL) {
printf("List is empty.\n");
return;
}
temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
//delete the last node
void deletelastnode(){
if(head==NULL){
printf("The list is empty.Can not delete the node\n");
return;
}
struct node* temp=head;
if(temp->next==head){
head=NULL;
free(temp);
return;
}
struct node*p =NULL;
while(temp->next!=head){
p=temp;
temp=temp->next;
}
p->next=head;
free(temp);
if (head == NULL) {
printf("List is empty.\n");
return;
}
temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
//delete the node in specific location
void deletenodeanywhere() {
if (head == NULL) {
printf("The list is empty.Cannot delete the node.\n");
return;
}
int location;
printf("Enter the location: ");
scanf("%d", &location);
struct node* temp = head;
struct node* p;
int count = 1;
do {
temp = temp->next;
count++;
} while (temp != head);
if (location <= 0 || location > count) {
printf("Invalid position. The list has %d nodes.\n", count);
return;
}
if (location == 1) {
struct node* last = head;
while (last->next != head) {
last = last->next;
}
temp = head;
head = head->next;
last->next = head;
free(temp);
} else {
temp = head;
for (int i = 1; i < location - 1; i++) {
temp = temp->next;
}
p = temp->next;
temp->next = p->next;
free(p);
}
if (head == NULL) {
printf("List is empty.\n");
return;
}
temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
int main() {
int option;
printf("Singly Linked List\n");
do {
printf("1. Create New Node\n");
printf("2. Delete node at beginning\n");
printf("3. Delete node at the end\n");
printf("4. Delete node in specific location in the list\n");
printf("5. Exit\n");
printf("Enter the option:\n");
scanf("%d", &option);
switch (option) {
case 1: createnewnode();
break;
case 2: deletenodeatbegin();
break;
case 3: deletelastnode();
break;
case 4: deletenodeanywhere();
break;
case 5: printf("Exited\n");
break;
default: printf("Enter correct option.\n");
break;
}
} while (option != 5);
return 0;
}
Time Complexity Analysis:
Functions Best Case Worst Case Explanation
createnewnode() O(1) O(n) If the list is empty, a new
node can be inserted in
O(1). If the list is not
empty, traversal is
required to reach the end,
resulting in O(n).
deletenodeatbegin() O(1) O(n) Removing the first
node takes O(1), but
updating the last
node’s next pointer
requires traversal if
there’s more than one
node, giving O(n) in
the worst case.
deletelastnode() O(1) O(n) If there is only one
node, deletion is O(1).
If there are multiple
nodes, traversal to
reach the
second-to-last node
takes O(n).
deletenodeanywhere() O(1) O(n) If deleting at the
beginning, the
operation is O(1).
Otherwise, traversal
up to the specified
location is required,
resulting in O(n) in
the worst case.
Explanation of Approch:
1. createnewnode() Function:
This function creates nodes and adds one node with another node.
Firstly, This function allocates memory for a new node and stores
the user input in the data. If the list is empty(head = = NULL), It
sets node’s next pointer to point itself, Creating a Single circle and
node. If the list contains nodes, it traverses to the last node and
updates it’s next pointer to the new node, then sets the new node’s
next pointer to head. Then it prints the entire list to confirm the node
has been added.The challenge while creating this node was ensuring
the circular property of the list when the first node is inserted and
when adding additional nodes.
2. deletenodeatbegin() Function:
This function deletes the first node of the linked list. In this
function, if the list is empty, it prints an error message. If only one
node is present in the linked list, then the function sets head pointer
to NULL. Then it frees the node. If there is more than one node is
present in the linked list then the function traverses to the last node
to update its next pointer to the new head. Then it updates the head
to point the next node and frees the original head. Then it prints the
updated list after deletion of the first node. The challenges I faced
during writing this code is maintaining the circular structure by
adjusting the last node’s next pointer when deleting the first node.
3.deletelastnode() Function:
This function deletes the last nodes of the linked list. Firstly, this
function checks if the list is empty or not. If the list is empty, it
prints an error message. If only one node is present in the linked list
then the function sets head to NULL. Then it frees the node. If there
is more than one node is present in the linked list, then the function
traverses to the second last node and updates its next pointer to point
to head effectively by passing the last node.Then, it frees the node.
Lastly, it prints the List to after the deletion of last node of the
linked list. In this function, the main challenge was correctly
identifying the second-to-last node and updating the next pointer to
maintain the circular link after deletion.
4.deletenodeanywhere() Function:
This function deletes the nodes of a specific location. Firstly, the
function checks if the list is empty or not. If the list is empty,it
displays an error message. Then, it prompts the user for a location
and verifies it within the list bounds. If the location is 1, it deletes
the node same as deleting the first node. If then node is in another
specified location,then it traverses to the node before the specified
location, update its next pointer to bypass the target node and free
the target node. Then, prints the least to confirm the deletion. In this
function, the main challenges was ensuring that the specified
location is valid within the bounds of the list and updating the
circular links correctly after deleting the node at a non beginning
position.
