Module 3

3.1
 Introduction,
 Representation of Linked List,
 Linked List v/s Array

3.2
 Types of Linked List - Singly Linked List,
 Circular Linked List,
 Doubly Linked List

3.3
 Operations on Singly Linked List and Doubly
Linked List

3.4
 Stack and Queue using Singly Linked List,
 Singly Linked List Application: Polynomial
Representation and Addition

Self-Learning: Polynomial Multiplication

 Linked List can be defined as collection of objects
called nodes that are randomly stored in the
memory.

 A node contains two fields i.e. data stored at that

particular address and the pointer which contains
the address of the next node in the memory.

 The last node of the list contains pointer to the

null.
 Singly Linked List

 Doubly Linked List

 Singly linked list can be defined as the collection of
ordered set of elements.

 The number of elements may vary according to need of the

program.

 Singly Linked List is good for dynamically allocating

memory.

 A node in the singly linked list consist of two parts:

◦ Data part - Stores actual information that is to be
represented by the node
◦ Link part- stores the address of its immediate successor

 Singly linked list can be traversed only in one direction. i.e,

each node contains only next pointer, therefore we can not
traverse the list in the reverse direction.
 Singly linked list
A singly linked list is a type of linked list that is unidirectional, i.e,
it can be traversed in only one direction from head to the last node
(tail)
head

Head Tail

15 4000 8 5000 20 3004 6 8002 7 6008 41 2000 None

INFO LINK
It provides all the basic operations of the linked list.

 Insertion − Adds an element in the list.

 Deletion − Deletes an element from the list.

 Display − Displays the complete list.

 Search − Searches an element using the given key.

 Sorting − Sort the element of the list.

 head points to the first node of the linked list
 next pointer of the last node is NULL, so if
the next current node is NULL, we have
reached the end of the linked list.

struct node {
int data;
struct node *next;
};
1. START
While the list is not
struct node *temp = head;
2.
printf("\n\nList elements are - \n");
empty and did not while(temp != NULL)
reach the end of the {
list, print the data in printf("%d --->",temp->data);
each node temp = temp->next;
3. END }
 Linked List - Traversal Operation
struct node *temp = head;
Traverse Linked List printf("\n\nList elements are - \n");
while(temp != NULL) {
printf("%d --->",temp->data);
head
temp = temp->next;
}

15 4000 8 5000 20 3004 6 8002 7 6008 41 2000 Null

INFO LINK

temp temp temp temp temp temp temp

1. START // Search a node
2. If the list is not bool searchNode(struct Node*
empty, iteratively head, int key) {

check if the list struct Node* current = head;

contains the key

while (current != NULL) {
3. If the key element is if (current->data == key)
not present in the list, return true;
unsuccessful search current = current->next;
4. END }
return false;
}
 Linked List - Search Operation
// Search a node
bool searchNode(struct Node* head, int key)
{
Search Node
struct Node* current = head;

while (current != NULL) {

if (current->data == key)
return true;
current = current->next;
head Position }
=5
1
2
3
4 return false;
}

40 link 15 link 8 link 20 None

link 50 Null

p p p p p
 Insertion at Beginning

 Insert at the End

 Insert at the Middle

1. START
2. Create a node to store the
data
3. Check if the list is empty
struct node *newNode;
newNode = malloc(sizeof(struct node));
4. If the list is empty, add the
newNode->data = 15;
data to the node and
newNode->next = head;
assign the head pointer to
it.
head = newNode;

5. If the list is not empty, add

the data to a node and link
to the current head. Assign
the head to the newly
added node.
6. END
1. START
struct node *newNode;
2. Create a new node and newNode = malloc(sizeof(struct node));
assign the data newNode->data = 8;
3. Find the last node
newNode->next = NULL;
4. Point the last node to
new node struct node *temp = head;
5. END
while(temp->next != NULL){
temp = temp->next;
}
temp->next = newNode;
 struct node *newNode;
newNode = malloc(sizeof(struct node));

1. START newNode->data = 20;

2. Create a new node

and assign data to it struct node *temp = head;
3. Iterate until the node
at position is found for(int i=2; i < position; i++) {
4. Point first to new first if(temp->next != NULL) {
node temp = temp->next;
5. END }
}
newNode->next = temp->next;
temp->next = newNode;
 Insert at the Middle
struct node *newNode;
Insert Node after given Node newNode = malloc(sizeof(struct node));
newNode->data = 20;

20 Null struct node *temp = head;

New node for(int i=2; i < position; i++) {

if(temp->next != NULL) {
temp = temp->next;
}
}
head
newNode->next = temp->next;
temp->next = newNode;
Got
you

5 next 10 next 30
20 next
next 40
30 Null
next 40 Null

temp temp
 Delete from beginning

 Delete from end

 Delete from middle

1. START
2. Assign the head
pointer to the next head = head->next;

node in the list

3. END
 Delete from beginning

Remove node from front

head head

40 next 15 next 8 next 20 Null

Notice that no shifting of elements needed after

node is removed unlike list or array where all
elements shifts after this operation
1. START
2. Iterate until you find struct node* temp = head;
the second last while(temp->next->next!=NULL){
element in the list. temp = temp->next;
3. Assign NULL to the }
second last element in temp->next = NULL;

the list.
4. END
 Delete from end
struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
temp->next = NULL;

head

40 next 15 next 8 Null

next 20 Null

temp temp temp

1. START
2. Iterate until find the for(int i=2; i< position; i++) {
current node at if(temp->next!=NULL) {
position in the list. temp = temp->next;
3. Assign the adjacent }
node of current node }

in the list to its

previous node. temp->next = temp->next->next;

4. END
 Delete from middle
for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}

head temp->next = temp->next->next;

40 next 15 next 8 next 20 Null

temp
 Make the head as the current node and create
another node index for later use.
 If head is null, return.
 Else, run a loop till the last node (i.e. NULL).
 In each iteration, follow the following step 5-
6.
 Store the next node of current in index.
 Check if the data of the current node is
greater than the next node. If it is greater,
swap current and index.
void sortLinkedList(struct Node* head) {
struct Node *current, *index;
int temp;

if (head == NULL) return; // empty list

current = head;
while (current != NULL) {
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
// swap data
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
 Linked List - Sort Operation
while (current != NULL) {
Sort the list index = current->next;
while (index != NULL) {
if (current->data > index->data) {
// swap data
temp = current->data;
current->data = index->data;
end p
None index->data = temp;
}
index = index->next;
}
head
current = current->next;
}

40
15 next 15
40
8 next
link
next 8
40
20 next
next
link 20
40 next
None
next 50 Null

p p p p p
[Link]
on13ejava/[Link]
 It works only for a fixed number of data
values.

 Amount of data must be specified at the

beginning of the implementation itself.

 Stack implemented using an array is not

suitable, when we don't know the size of data
which we are going to use.
 The stack implemented using linked list can
work for an unlimited number of values.

 That means, stack implemented using linked

list works for the variable size of data.

 So, there is no need to fix the size at the

beginning of the implementation.

 The Stack implemented using linked list can

organize as many data values as we want.
 In linked list implementation of a
stack, every new element is inserted
as 'top' element. That means every
newly inserted element is pointed by
'top'.

 Whenever we want to remove an

element from the stack, simply
remove the node which is pointed
by 'top' by moving 'top' to its
previous node in the list.

 The next field of the first element

must be always NULL.
1. Define a 'Node' structure with two
members data and next.
2. Define a Node pointer 'top' and set it
to NULL.
3. Implement the main method by displaying
Menu with list of operations and make
suitable function calls in the main method.
 Algorithm for push(value) void push(int val)
{
//create new node
1. Create a newNode with given struct node *newNode =
value. malloc(sizeof(struct node));

2. Check whether stack newNode->data = val;

is Empty (top == NULL)
//make the new node points to the
3. If it is Empty, then head node
set newNode → next = NULL. newNode->next = head;
4. If it is Not Empty, then //make the new node as head
set newNode → next = top. node
5. Finally, set top = newNode.
//so that head will always point
the last inserted data
head = newNode;
}
 Algorithm for pop() void pop()
{
1. Check //temp is used to free the head node
whether stack is Empty (top struct node *temp;
== NULL).
if(head == NULL)
2. If it is Empty, then printf("Stack is Empty\n");
display "Stack is else
Empty!!!" and terminate the {
function. printf("Poped element = %d\n", head->data);
3. If it is Not Empty, then
define a Node pointer //backup the head node
'temp' and set it to 'top'. temp = head;
4. Then set 'top = top → next'. //make the head node points to the next node.
//logically removing the node
5. Finally, delete 'temp'. head = head->next;
(free(temp)).
//free the poped element's memory
*you can head instead of top free(temp);
}
}
Algorithm for display()

1. Check whether stack is Empty (top == NULL).

2. If it is Empty, then display 'Stack is Empty!!!' and
terminate the function.
3. If it is Not Empty, then define a Node
pointer 'temp' and initialize with top.
4. Display 'temp → data --->' and move it to the next
node. Repeat the same until temp reaches to the
first node in the stack. (temp → next != NULL).
5. Finally! Display 'temp → data ---> NULL'.
 The queue which is implemented using a
linked list can work for an unlimited number
of values.

 That means, queue using linked list can work

for the variable size of data (No need to fix
the size at the beginning of the
implementation).

 The Queue implemented using linked list can

organize as many data values as we want.
In linked list implementation of a queue, the
last inserted node is always pointed by 'rear'
and the first node is always pointed by 'front'.
1. Define a 'Node' structure with two
members data and next.
2. Define two Node pointers 'front' and 'rear'
and set both to NULL.
3. Implement the main method by displaying
Menu of list of operations and make
suitable function calls in the main method
to perform user selected operation.
 Algorithm for void enqueue(int val)
enqueue(value) {
struct node *newNode =

Create a newNode with

malloc(sizeof(struct node));
1. newNode->data = val;
given value and set newNode->next = NULL;
'newNode → next'
to NULL. //if it is the first node
2. Check whether queue
if(front == NULL && rear == NULL)
is Empty (rear == NULL)
//make both front and rear points to the
new node
3. If it is Empty then, front = rear = newNode;
set front = newNode and r else
ear = newNode. {
4. If it is Not Empty then,
//add newnode in rear->next
rear->next = newNode;
set rear →
next = newNode and rear //make the new node as the rear node
= newNode. rear = newNode;
}
}
 Algorithm for dequeue( ) void dequeue() {
//used to freeing the first node after dequeue
struct node *temp;
1. Check
whether queue is Empty if(front == NULL)
(front == NULL). printf("Queue is Empty. Unable to perform
dequeue\n");
2. If it is Empty, then else {
display "Queue is Empty!!! //take backup
Deletion is not temp = front;
possible!!!" and terminate
from the function //make the front node points to the next node
//logically removing the front element
3. If it is Not Empty then, front = front->next;
define a Node pointer
'temp' and set it to 'front'. //if front == NULL, set rear = NULL
4. Then set 'front = front → if(front == NULL)
next' and delete 'temp' rear = NULL;

(free(temp)). //free the first node

free(temp);
}
}
Algorithm for display()

1. Check whether queue is Empty (front == NULL).

2. If it is Empty then, display 'Queue is
Empty!!!' and terminate the function.
3. If it is Not Empty then, define a Node
pointer 'temp' and initialize with front.
4. Display 'temp → data --->' and move it to the
next node. Repeat the same until 'temp' reaches
to 'rear' (temp → next != NULL).
5. Finally! Display 'temp → data ---> NULL'.
Singly Linked List Applications are :

 Polynomial Representation

 Polynomial Addition

 Polynomial Multiplication
 Polynomial Representation
Polynomials

Polynomial in one variable can be represented as

below:

Example:

First term: degree 2 & coefficient 12

Second term: degree 1 & coefficient -3
Third term: degree 0 & coefficient 7
Polynomial ADT
struct Node
{
int coefficient;
int exponent;
struct Node *next;
};
Polynomial Representation
1. Decidethe data values i.e.
coefficient and the exponent that
the new node should contain. struct Node* createNode(int coeff, int
exp)
{
2. Store
the given coefficient in the struct Node* newNode = (struct
coeff field of the node. Node*) malloc(sizeof(struct Node));

3. Store
the given exponent in the newNode->coefficient = coeff;
exp field of the node. newNode->exponent = exp;
newNode->next = NULL;
return newNode;
4. Setthe next pointer of the node to }
NULL (because when a node is
first created, it does not point to
any other node).

5. Returnthe address of this newly

created node so it can be linked
into the polynomial.
Terms can be inserted in various ways
(e.g., at the beginning, at the end, or in
sorted order by exponent). Inserting in
sorted order simplifies operations like
addition.
struct Node* insertTerm(struct Node* head,
int coeff, int exp) { // If a term with the same exponent
struct Node* newNode = createNode(coeff, exists, add coefficients
exp); if (current != NULL && exp == current-
>exponent) {
// If the list is empty or the new term has a current->coefficient += coeff;
higher exponent than the head free(newNode); // Free the newly
if (head == NULL || exp > head->exponent) created node as it's not needed
{ } else { // Insert the new term
newNode->next = head; if (prev == NULL) { // Insert at the
return newNode; // New head beginning (already handled above for
} higher exponent)
newNode->next = head;
struct Node* current = head; head = newNode;
struct Node* prev = NULL; } else {
newNode->next = current;
// Traverse to find the correct insertion prev->next = newNode;
point (maintaining sorted order by exponent) }
while (current != NULL && }
exp < current->exponent) { return head;
prev = current; }
current = current->next;
}
1. Start with the head of the polynomial.

2. For each node in the list:

void displayPolynomial(struct Node*
3. Printthe coefficient and the variable x head) {
with the exponent. if (head == NULL) {
printf("Polynomial is empty.\n");
4. If
the coefficient is positive and it is not return;
the first term, print a “+” sign before it.
}
struct Node* current = head;
5. If
the coefficient is negative, print a “-” while (current != NULL) {
sign.
printf("%dX^%d ", current-
>coefficient, current->exponent);
6. If
the exponent is 0, only print the if (current->next != NULL) {
coefficient.
printf("+ ");
}
7. If
the exponent is 1, print only x (not current = current->next;
x^1).
}
printf("\n");
8. Continue until all terms are displayed.
}
1. Declare variables that point to the head of the linked
list.
2. Compare the exponent of the first polynomial in
both lists.
3. If the value of a node's exponent is greater than
other, then store the greater node into the result
node, and increment the variable also towards the
next node.
4. If the values of both nodes' exponents are the same,
add the coefficients and then store the value in the
result.
5. Repeat steps 2nd and 3rd until one of the variables
reaches the end of the list.
6. After that, when the variable reaches the end of the
list, store all the remaining polynomials in the result
list as it is.
struct Node* addPolynomials(struct Node*
poly1, struct Node* poly2) {
struct Node* result = NULL;
while (poly1 != NULL && poly2 != NULL) {
// Copy remaining terms
if (poly1->exp > poly2->exp) {
while (poly1 != NULL) {
insertTerm(&result, poly1->coeff,
insertTerm(&result, poly1->coeff,
poly1->exp);
poly1->exp);
poly1 = poly1->next;
poly1 = poly1->next;
}
}
else if (poly2->exp > poly1->exp) {
while (poly2 != NULL) {
insertTerm(&result, poly2->coeff,
insertTerm(&result, poly2->coeff,
poly2->exp);
poly2->exp);
poly2 = poly2->next;
poly2 = poly2->next;
}
}
else {
return result;
insertTerm(&result, poly1->coeff +
}
poly2->coeff, poly1->exp);
poly1 = poly1->next;
poly2 = poly2->next;
}
}
Polynomial Multiplication
A circular linked list is a data structure where
the last node points back to the first node,
forming a closed loop.
Circular Linked List can be further divided into-

1. Circular Singly Linked List

2. Circular Doubly Linked List
 In Circular Singly Linked List, each node has
just one pointer called the "next" pointer.
 The next pointer of the last node points back
to the first node and this results in forming a
circle.
 In this type of Linked list, we can only move
through the list in one direction.
struct Node* addToEmpty(struct Node*
last, int data) {
if (last != NULL) return last;

// allocate memory to the new node

struct Node* newNode = (struct
Node*)malloc(sizeof(struct Node));

// assign data to the new node

newNode->data = data;

// assign last to newNode

last = newNode;

// create link to iteself

last->next = last;

return last;
}
1. Insertion
◦ Insertion at the beginning
◦ Insertion in-between nodes
◦ Insertion at the end

2. Deletion
◦ Deletion at the beginning
◦ Deletion in-between nodes
◦ Deletion at the end
 store the address of the current first node in
the newNode (i.e. pointing the newNode to
the current first node)
 point the last node to newNode (i.e making
newNode as head)
// add node to the front
struct Node* addFront(struct Node* last, int data) {
// check if the list is empty
if (last == NULL) return addToEmpty(last, data);

// allocate memory to the new node

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

// add data to the node

newNode->data = data;

// store the address of the current first node in the newNode

newNode->next = last->next;

// make newNode as head

last->next = newNode;
return last;
}
 Let's insert newNode after the first node.
 travel to the node given (let this node be p)
 point the next of newNode to the node next
to p
 store the address of newNode at next of p
// insert node after a specific node // make the next of the current node as
the next of newNode
struct Node* addAfter(struct Node* last,
int data, int item) { newNode->next = p->next;
// check if the list is empty
if (last == NULL) return NULL; // put newNode to the next of p
p->next = newNode;
struct Node *newNode, *p;
// if p is the last node, make newNode
as the last node
p = last->next;
if (p == last)
do {
last = newNode;
// if the item is found, place newNode
after it return last;
if (p->data == item) { }
// allocate memory to the new node p = p->next;
newNode = (struct } while (p != last->next);
Node*)malloc(sizeof(struct Node));
printf("\nThe given node is not present
// add data to the node in the list");
newNode->data = data; return last;
}
 store the address of the head node to next of
newNode (making newNode the last node)
 point the current last node to newNode
 make newNode as the last node
// add node to the end
struct Node* addEnd(struct Node* last, int data) {
// check if the node is empty
if (last == NULL) return addToEmpty(last, data);

// allocate memory to the new node

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = data; // add data to the node

// store the address of the head node to next of newNode

newNode->next = last->next;

// point the current last node to the newNode

last->next = newNode;

last = newNode; // make newNode as the last node

return last;
}
If the node to be deleted is the only node

1. free the memory occupied by the node

2. store NULL in last
 find the node before the last node (let it be
temp)
 store the address of the node next to the last
node in temp
 free the memory of last
 make temp as the last node
 travel to the node to be deleted (here we are
deleting node 2)
 let the node before node 2 be temp
 store the address of the node next to 2 in
temp
 free the memory of 2
// delete a node // Case 3: Deleting last or middle node
struct Node* deleteNode(struct Node* last, int key) do {
{ prev = temp;
temp = temp->next;
// Case 1: Empty list if (temp->data == key)
if (last == NULL) return NULL; {
prev->next = temp->next;
struct Node *temp = last, *prev = NULL;
// If deleting last, update last
// Case 2: List has only one node if (temp == last)
if (last->data == key && last->next == last) { {
free(last); last = prev;
return NULL; }
} free(temp);
return last;
}
} while (temp != last);
// Key not found
return last;
}
 Doubly linked list is a complex type of linked
list in which a node contains a pointer to the
previous as well as the next node in the
sequence.

 Therefore, in a doubly linked list, a node

consists of three parts:

◦ Prev: Each node is linked to its previous node. It is

used as a pointer or link.
◦ Next: Each node is linked to its next node. It is used
as a pointer or link.
◦ Data: This is used to store data in a node.
struct node {
int data;
struct node *next;
struct node *prev;
}
 Insertion

 Deletion
We can insert elements at 3 different positions
of a doubly-linked list:

1. Insertion at the beginning

2. Insertion in-between nodes
3. Insertion at the End
1. Create a new node with the given data.
2. Set the next pointer of the new node to the current
head.
3. If the list is not empty, update the prev pointer of
the current head to point to the new node.
4. Update the head of the list to the new node.
// insert node at the front
void insertFront(struct Node** head, int data)
{
struct Node* newNode = malloc(sizeof(struct Node)); // allocate memory for newNode

newNode->data = data; // assign data to newNode

// point next of newNode to the first node of the doubly linked list
newNode->next = (*head);

newNode->prev = NULL; // point prev to NULL

// point previous of the first node (now first node is the second node) to newNode
if ((*head) != NULL)
(*head)->prev = newNode;

(*head) = newNode; // head points to newNode

}
 Create a new node
 Set the next pointer of new node and previous node
 Set the prev pointer of new node and the next node
// insert a node after a specific node
void insertAfter(struct Node* prev_node, int data)
{
struct Node* newNode = malloc(sizeof(struct Node));// allocate memory for newNode

newNode->data = data; // assign data to newNode

newNode->next = prev_node->next; // set next of newNode to next of prev node

prev_node->next = newNode; // set next of prev node to newNode

newNode->prev = prev_node; // set prev of newNode to the previous node

// set prev of newNode's next to newNode

if (newNode->next != NULL)
newNode->next->prev = newNode;
}
 Create a new node
 Set prev and next pointers of new node and the
previous node
// insert a newNode at the end of the list
void insertEnd(struct Node** head, int data) {
struct Node* newNode = malloc(sizeof(struct Node)); // allocate memory for node
newNode->data = data; // assign data to newNode
newNode->next = NULL; // assign NULL to next of newNode
struct Node* temp = *head;

// if the linked list is empty, make the newNode as head node

if (*head == NULL) {
newNode->prev = NULL;
*head = newNode;
return;
}
// if the linked list is not empty, traverse to the end of the linked list
while (temp->next != NULL)
temp = temp->next;
// now, the last node of the linked list is temp
// point the next of the last node (temp) to newNode.
temp->next = newNode;
newNode->prev = temp; // assign prev of newNode to temp
}
 Delete the First Node of Doubly Linked List

 Deletion of the Inner Node

 Delete the Last Node of Doubly Linked List

if (*head == del_node)
*head = del_node->next;

free(del_node);
if (del_node->next != NULL)
del_node->next->prev = del_node->prev;

if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
if (del_node->prev != NULL)
del_node->prev->next = del_node->next;
 In circular doubly linked list, each node has two
pointers prev and next, similar to doubly linked list.

 The prev pointer points to the previous node and

the next points to the next node.

 Here, in addition to the last node storing the

address of the first node, the first node will also
store the address of the last node.
 Insertion
◦ Insertion at the Beginning
◦ Insertion at the End
◦ Insertion after a given node

 Deletion
◦ Deletion from the Beginning
◦ Deletion from the End
◦ Deletion after a given node
1. Allocate memory for the struct Node* insertAtBeginning(struct Node* head, int
new node. data) {
2. If the list is empty, set struct Node* newNode = (struct
the new Node*)malloc(sizeof(struct Node));
node’s next and prev to newNode->data = data;
point to itself, and // Case 1: Empty list
update the head to this
new node.
if (head == NULL) {
newNode->next = newNode->prev = newNode;
3. For a non-empty list,
insert the new node: head = newNode;
1. Set the new node’s next to }
the current head. // Case 2: Non-empty list
2. Set the new node’s prev to else {
the last node. struct Node* last = head->prev; // get last node
3. Update
the current head’s prev to newNode->next = head;
the new node. newNode->prev = last;
4. Update head->prev = newNode;
the last node’s next to the last->next = newNode;
new node.
4. Set the new node as head = newNode;
the new head of the list. }
return head;
}
 Allocate memory for the
new node. struct Node* insertAtEnd(struct Node* head, int data)
 If the list is empty, set {
the new struct Node* newNode = (struct
node’s next and prev poi Node*)malloc(sizeof(struct Node));
nters to point to itself,
and update the head to newNode->data = data;
this new node.
 For a non-empty list, struct Node* last = head->prev;
insert the new node:
 Find the current last node (the
node whose next pointer newNode->next = head;
points to the head). newNode->prev = last;
 Set the new last->next = newNode;
node’s next pointer to point to
the head. head->prev = newNode;
 Set the new
node’s prev pointer to point to
the current last node. return head;
 Update the current last node’s }
next pointer to point to the
new node.
 Update the head’s prev pointer
to point to the new node.
 Allocate memory for the struct Node* insertAfterNode(struct Node* head,
new node. int data, int key) {

 Traverse the list struct Node* curr = head;

to locate given node.

do {
if (curr->data == key) {
 Insert the newNode: struct Node* newNode = (struct
 Set newNode->next to given Node*)malloc(sizeof(struct Node));
node'next. newNode->data = data;
 Set newNode->prev to
givenNode. newNode->next = curr->next;
 Update givenNode->next- newNode->prev = curr;
>prev to newNode. curr->next->prev = newNode;
 Update givenNode->next to curr->next = newNode;
newNode. }
 If givenNode is the last node curr = curr->next;
(i.e., points to head), } while (curr != head);
update head->prev to
newNode. // key not found → no change
return head;
}
 Adjust the next struct Node* deleteFromBeginning(struct Node* last)
pointer of the last {
node to point to struct Node* head = last->next; // first node
the second node. // Case 1: Only one node
if (head == last) {

 Set the second free(head);

node as the new last = NULL;

head. }
// Case 2: More than one node
else {
 Adjust the struct Node* temp = head; // node to delete
previous pointer head = head->next;
of the new head head->prev = last;
to point to the last->next = head;
last node. free(temp);
}
return last; // return updated last
}
 Adjust the next struct Node* deleteFromEnd(struct Node* last)
pointer of the {
second-to-last struct Node* temp = last; // node to delete

node to point to struct Node* newLast = last->prev;

the head. newLast->next = last->next;

last->next->prev = newLast;

Adjust the
free(temp);

last = newLast; // update last
previous pointer of
the head to point return last;

to the second-to- }

last node.
 struct Node* deleteAfter(struct Node* last, int key) {

Traverse the list

struct Node* curr = last->next; // start from head
 // Traverse to find the node with data = key
to find the node. do {
if (curr->data == key) {
struct Node* delNode = curr->next;
 Adjust the
pointers of the
// Adjust links
curr->next = delNode->next;
previous and delNode->next->prev = curr;

next nodes to free(delNode);

bypass the node return last;
to be deleted. }
curr = curr->next;
} while (curr != last->next);

printf("Key %d not found in the list.\n", key);

return last;
}