Linked Lists

Introduction
We have studied that an array is a linear collection of data elements in which the elements are stored in
consecutive memory locations.
While declaring arrays, we have to specify the size of the array, which will restrict the number of
elements that the array can store. For example, if we declare an array as int marks[10], then the array can
store a maximum of 10 data elements but not more than that.
But what if we are not sure of the number of elements in advance? Moreover, to make efficient use of
memory, the elements must be stored randomly at any location rather than in consecutive locations.
So, there must be a data structure that removes the restrictions on the maximum number of elements and
the storage condition to write efficient programs.

Linked list is a data structure that is free from the aforementioned restrictions. A linked list does not
store its elements in consecutive memory locations and the user can add any number of elements to it.
However, unlike an array, a linked list does not allow random access of data.
Elements in a linked list can be accessed only in a sequential manner. But like an array, insertions and
deletions can be done at any point in the list in a constant time.

Basic Terminologies
A linked list, in simple terms, is a linear collection of data elements.
These data elements are called nodes.
Linked list is a data structure which in turn can be used to implement other data structures. Thus, it acts
as a building block to implement data structures such as stacks, queues, and their variations.
A linked list can be perceived as a train or a sequence of nodes in which each node contains one or more
data fields and a pointer to the next node.

We can see a linked list in which every node contains two parts, an integer and a pointer to the next
node.
The left part of the node which contains data may include a simple data type, an array, or a structure.
The right part of the node contains a pointer to the next node (or address of the next node in sequence).
The last node will have no next node connected to it, so it will store a special value called NULL.
Here, the NULL pointer is represented by X. While programming, we usually define NULL as –1. Hence,
a NULL pointer denotes the end of the list.
Since in a linked list, every node contains a pointer to another node which is of the same type, it is also
called a self-referential data type.

Linked lists contain a pointer variable START that stores the address of the first node in the list.
We can traverse the entire list using START which contains the address of the first node; the next part of
the first node in turn stores the address of its succeeding node. Using this technique, the individual nodes
of the list will form a chain of nodes.

1
If START = NULL, then the linked list is empty and contains no nodes.
A Linked List can be implemented using the following code:

Linked lists provide an efficient way of storing related data and perform basic operations such as
insertion, deletion, and updation of information at the cost of extra space required for storing address of
the next node.

Let us see how a linked list is maintained in the memory.

In order to form a linked list, we need a structure called
node which has two fields, DATA and NEXT.
DATA will store the information part and NEXT will store
the address of the next node in sequence.

In the figure, we can see that the variable START is used to

store the address of the first node. Here, in this example,
START = 1, so the first data is stored at address 1, which is
H.
The corresponding NEXT stores the address of the next
node, which is 4. So, we will look at address 4 to fetch the
next data item. The second data element obtained from
address 4 is E.
Again, we see the corresponding NEXT to go to the next node. From the entry in the NEXT, we get the
next address, that is 7, and fetch L as the data.
We repeat this procedure until we reach a position where the NEXT entry contains –1 or NULL, as this
would denote the end of the linked list.
When we traverse DATA and NEXT in this manner, we finally see that the linked list in the above
example stores characters that when put together form the word HELLO.
In this example, a chunk of memory locations which range from 1 to 10. The shaded portion contains data
for other applications. Remember that the nodes of a linked list need not be in consecutive memory
locations. In our example, the nodes for the linked list are stored at addresses 1, 4, 7, 8, and 10.

Linked Lists vs Arrays

Both arrays and linked lists are a linear collection of data elements.
But unlike an array, a linked list does not store its nodes in consecutive memory locations.
Another point of difference between an array and a linked list is that a linked list does not allow random
access of data. Nodes in a linked list can be accessed only in a sequential manner.
But like an array, insertions and deletions can be done at any point in the list in a constant time.

Another advantage of a linked list over an array is that we can add any number of elements in the list.
This is not possible in case of an array. For example, if we declare an array as int marks[20], then the
array can store a maximum of 20 data elements only. There is no such restriction in case of a linked list.

2
Thus, linked lists provide an efficient way of storing related data and performing basic operations such as
insertion, deletion, and updation of information at the cost of extra space required for storing the address
of next nodes.

Memory Allocation and Deallocation for a Linked List

We have seen how a linked list is represented in the memory.
If we want to add a node to an already existing linked list in the memory, we first find free space in the
memory and then use it to store the information.
For example, consider the linked list shown below. The linked list contains the roll number of students,
marks obtained by them in Biology, and finally a NEXT field which stores the address of the next node in
sequence.

(a) Students’ linked list and (b) linked list after the insertion of new student’s record
Now, if a new student joins the class and is asked to appear for the same test that the other students had
taken, then the new student’s marks should also be recorded in the linked list. For this purpose, we find a
free space and store the information there.
In the above figure, the grey shaded portion shows free space, and thus we have 4 memory locations
available. We can use any one of them to store our data. This is illustrated in figure (a) and (b).

Now, the question is which part of the memory is available and which part is occupied? When we delete a
node from a linked list, then who changes the status of the memory occupied by it from occupied to
available? The answer is the operating system.
Discussing the mechanism of how the operating system does all this is out of the scope of this book. So,
in simple language, we can say that the computer does it on its own without any intervention from the
user or the programmer. As a programmer, you just have to take care of the code to perform insertions and
deletions in the list.
However, let us briefly discuss the basic concept behind it. The computer maintains a list of all free
memory cells. This list of available space is called the free pool.

3
We have seen that every linked list has a pointer variable START which stores the address of the first
node of the list.
Likewise, for the free pool (which is a linked list of all free memory cells), we have a pointer variable
AVAIL which stores the address of the first free space.
Let us revisit the memory representation of the linked list storing all the students’ marks in Biology.

Now, when a new student’s record has to be added, the memory address pointed by AVAIL will be taken
and used to store the desired information. After the insertion, the next available free space’s address will
be stored in AVAIL.

In the above figure, when the first free memory space is utilized for inserting the new node, AVAIL will
be set to contain address 6.
This was all about inserting a new node in an already existing linked list. Now, we will discuss deleting a
node or the entire linked list.
When we delete a particular node from an existing linked list or delete the entire linked list, the space
occupied by it must be given back to the free pool so that the memory can be reused by some other
program that needs memory space.
The operating system does this task of adding the freed memory to the free pool. The operating system
will perform this operation whenever it finds the CPU idle or whenever the programs are falling short of
memory space. The operating system scans through all the memory cells and marks those cells that are
being used by some program. Then it collects all the cells which are not being used and adds their address
to the free pool, so that these cells can be reused by other programs. This process is called garbage
collection.

Singly Linked Lists

A singly linked list is the simplest type of linked list in which every node contains some data and a
pointer to the next node of the same data type. By saying that the node contains a pointer to the next node,
we mean that the node stores the address of the next node in sequence. A singly linked list allows
traversal of data only in one way.

4
 Fig: Singly Linked List

Traversing a Linked List

Traversing a linked list means accessing the nodes of the list in order to perform some processing on
them.
A linked list always contains a pointer variable START which stores the address of the first node of the
list. End of the list is marked by storing NULL or –1 in the NEXT field of the last node.
For traversing the linked list, we also make use of another pointer variable PTR which points to the node
that is currently being accessed.

In this algorithm, we first initialize PTR with the address of START. So now, PTR points to the first node
of the linked list. Then in Step 2, a while loop is executed which is repeated till PTR processes the last
node, that is until it encounters NULL. In Step 3, we apply the process (e.g., print) to the current node,
that is, the node pointed by PTR. In Step 4, we move to the next node by making the PTR variable point
to the node whose address is stored in the NEXT field.

Let us now write an algorithm to count the number of nodes in a linked list. To do this, we will traverse
each and every node of the list and while traversing every individual node, we will increment the counter
by 1. Once we reach NULL, that is, when all the nodes of the linked list have been traversed, the final
value of the counter will be displayed.

Searching for a Value in a Linked List

Searching a linked list means to find a particular element in the linked list.

5
As already discussed, a linked list consists of nodes which are divided into two parts, the information
part and the next part.
So searching means finding whether a given value is present in the information part of the node or not.
If it is present, the algorithm returns the address of the node that contains the value.

In Step 1, we initialize the pointer variable PTR with START that contains the address of the first node. In
Step 2, a while loop is executed which will compare every node’s DATA with VAL for which the search is
being made. If the search is successful, that is, VAL has been found, then the address of that node is
stored in POS and the control jumps to the last statement of the algorithm. However, if the search is
unsuccessful, POS is set to NULL which indicates that VAL is not present in the linked list.

Consider the linked list shown in Fig. 6.11. If we have VAL = 4, then the flow of the algorithm can be
explained as shown in the figure.

Inserting a New Node in a Linked List

In this section, we will see how a new node is added into an already existing linked list. We will take four
cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.

6
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.
Before we describe the algorithms to perform insertions in all these four cases, let us first discuss an
important term called OVERFLOW. Overflow is a condition that occurs when AVAIL = NULL or no free
memory cell is present in the system. When this condition occurs, the program must give an appropriate
message.

Inserting a Node at the Beginning of a Linked List

This algorithm shows the steps to insert a new node at

the beginning of a linked list. In Step 1, we first check
whether memory is available for the new node. If the
free memory has exhausted, then an OVERFLOW
message is printed. Otherwise, if a free memory cell
is available, then we allocate space for the new node.
Set its DATA part with the given VAL and the next
part is initialized with the address of the first node of
the list, which is stored in START. Now, since the
new node is added as the first node of the list, it will
now be known as the START node, that is, the
START pointer variable will now hold the address of
the NEW_NODE.
Note the following two steps:

These steps allocate memory for the new node. In C, there are functions like malloc(), alloc, and calloc()
which automatically do the memory allocation on behalf of the user.

7
Inserting a Node at the End of a Linked List
Suppose we want to add a new node with data 9 as the last node of the list. Then the following changes
will be done in the linked list.

Fig: Inserting an element at the end of a linked list

The algorithm shows the algorithm to insert a

new node at the end of a linked list. In Step 6, we
take a pointer variable PTR and initialize it with
START. That is, PTR now points to the first node
of the linked list. In the while loop, we traverse
through the linked list to reach the last node.
Once we reach the last node, in Step 9, we
change the NEXT pointer of the last node to store
the address of the new node. Remember that the
NEXT field of the new node contains NULL,
which signifies the end of the linked list.

Inserting a Node After a Given Node in a

Linked List
Suppose we want to add a new node with value 9
after the node containing data 3. Before
discussing the changes that will be done in the linked list, let us first look at the algorithm.

In Step 5, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the
first node of the linked list. Then we take another pointer variable PREPTR which will be used to store

8
the address of the node preceding PTR. Initially, PREPTR is initialized to PTR. So now, PTR, PREPTR,
and START are all pointing to the first node of the
linked list.
In the while loop, we traverse through the linked
list to reach the node that has its value equal to
NUM. We need to reach this node because the
new node will be inserted after this node. Once
we reach this node, in Steps 10 and 11, we change
the NEXT pointers in such a way that a new node
is inserted after the desired node.

9
Inserting a Node Before a Given Node in a Linked List
Suppose we want to add a new node with value 9 before the node containing 3. Before discussing the
changes that will be done in the linked
list, let us first look at the algorithm.
In Step 5, we take a pointer variable
PTR and initialize it with START.
That is, PTR now points to the first
node of the linked list. Then, we take
another pointer variable PREPTR and
initialize it with PTR. So now, PTR,
PREPTR, and START are all pointing
to the first node of the linked list.
In the while loop, we traverse through
the linked list to reach the node that
has its value equal to NUM. We need
to reach this node because the new
node will be inserted before this node.
Once we reach this node, in Steps 10
and 11, we change the NEXT pointers
in such a way that the new node is inserted before the desired node.

Fig: Inserting an element before a given node in a linked list

10
Deleting a Node from a Linked List
In this section, we will discuss how a node is deleted from an already existing linked list. We will
consider three cases and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.
Case 3: The node after a given node is deleted.
Before we describe the algorithms in all these three cases, let us first discuss an important term called
UNDERFLOW.
Underflow is a condition that occurs when we try to delete a node from a linked list that is empty. This
happens when START = NULL or when there are no more nodes to delete.
Note that when we delete a node from a linked list, we actually have to free the memory occupied by that
node. The memory is returned to the free pool so that it can be used to store other programs and data.
Whatever be the case of deletion, we always change the AVAIL pointer so that it points to the address that
has been recently vacated.

Deleting the First Node from a Linked List

Consider the linked list in Fig. 6.20. When we want to delete a node from the beginning of the list, then
the following changes will be done in the linked list.

Figure 6.21 shows the algorithm to delete the first node

from a linked list. In Step 1, we check if the linked list
exists or not. If START = NULL, then it signifies that there
are no nodes in the list and the control is transferred to the
last statement of the algorithm.
However, if there are nodes in the linked list, then we use a
pointer variable PTR that is set to point to the first node of
the list. For this, we initialize PTR with START that stores
the address of the first node of the list. In Step 3, START is
made to point to the next node in sequence and finally the
memory occupied by the node pointed by PTR (initially the
first node of the list) is freed and returned to the free pool.

Deleting the Last Node from a Linked List

Consider the linked list shown in Fig. 6.22. Suppose we want to delete the last node from the linked list,
then the following changes will be done in the linked list.
Figure 6.23 shows the algorithm to delete the last node from a linked list. In Step 2, we take a pointer
variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In
the while loop, we take another pointer variable PREPTR such that it always points to one node before the

11
PTR. Once we reach the last node and the second last node, we set the NEXT pointer of the second last
node to NULL, so that it now becomes the (new) last node of the linked list. The memory of the previous
last node is freed and returned back to the free pool.

Deleting the Node After a

Given Node in a Linked List
Consider the linked list shown in
Fig. 6.24. Suppose we want to
delete the node that succeeds the
node which contains data value 4.
Then the following changes will
be done in the linked list.
Figure 6.25 shows the algorithm
to delete the node after a given
node from a linked list. In Step 2,
we take a pointer variable PTR

12
and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop,
we take another pointer variable PREPTR such that it always points to one node before the PTR. Once we
reach the node containing VAL and the node succeeding it, we set the next pointer of the node containing
VAL to the address contained in the next field of the node succeeding it. The memory of the node
succeeding the given node is freed and returned back to the free pool.

Circular Linked List

● In a circular linked list, the last node contains a pointer to the first node of the list.
● We can have a circular singly linked list as well as a circular doubly linked list.
● While traversing a circular linked list, we can begin at any node and traverse the list in any
direction, forward or backward, until we reach the same node where we started. Thus, a circular
linked list has no beginning and no ending.

The only downside of a circular linked list is the complexity of iteration. Note that there are no NULL
values in the NEXT part of any of the nodes of the list.

13
Circular linked lists are widely used in operating systems for task maintenance.

Example
Implementation of a Queue: A circular linked list can be used to implement a queue, where the front
and rear of the queue are the first and last nodes of the list, respectively. In this implementation, when an
element is enqueued, it is added to the rear of the list and when an element is dequeued, it is removed
from the front of the list.
Music or Media Player: Circular linked lists can be used to create a playlist for a music or media player.
The playlist can be represented as a circular linked list, where each node contains information about a
song or media item, and the next node points to the next song in the playlist. This allows continuous
playback of the playlist I.e., each node in the list can represent a song or media item and the “next”
pointer can point to the next song in the playlist. When the end of the playlist is reached, the pointer can
be set to the beginning of the list, creating a circular structure that allows for continuous playback.
Memory Allocation: In computer memory management, circular linked lists can be used to keep track of
the allocated and free blocks of memory. Each node in the list represents a block of memory. When a
block of memory is freed, it can be added back to the circular linked list.
Task Scheduling: Circular linked lists can be used to implement task scheduling algorithms, where each
node in the list represents a task and its priority. The “next” pointer can point to the next task in the queue,
with the end of the queue pointing back to the beginning to create a circular structure. This allows for a
continuous loop of the task scheduling, where tasks are added and removed from the queue based on their
priority.
Cache Management: Circular linked lists can be used in the cache management algorithms to manage
the replacement of cache entries. Each node in the list can represent a cache entry, with the “next” pointer
pointing to the next entry in the list. When the end of the list is reached, the pointer can be set to the
beginning of the list, creating a circular structure that allows for the replacement of older entries with
ones.
File system Management: Circular linked lists can be used in file system management to track the
allocation of the disk space. Each node in the list can represent a block of disk space, with the “next”
pointer pointing to the next available block. When the end of the list is reached, the pointer can be set to
the beginning of the list, creating a circular structure that allows for the allocation and deallocation of disk
space.
We can traverse the list until we find the NEXT entry that contains
the address of the first node of the list. This denotes the end of the
linked list, that is, the node that contains the address of the first
node is actually the last node of the list. When we traverse the
DATA and NEXT in this manner, we will finally see the linked list
in Fig. stores characters that when put together form the word
HELLO.
Now, look at Figure. Two different linked lists are simultaneously
maintained in the memory. There is no ambiguity in traversing
through the list because each list maintains a separate START
pointer which gives the address of the first node of the respective
linked list. The remaining nodes are reached by looking at the
value stored in NEXT.

14
By looking at the figure, we can conclude that the roll numbers of the students who have opted for
Biology are S01, S03, S06, S08, S10, and S11. Similarly, the roll numbers of the students who chose
Computer Science are S02, S04, S05, S07, and S09.

Fig: Memory representation of two circular linked lists stored in the Memory

Inserting a New Node in a Circular Linked List

In this section, we will see how a new node is added into an already existing linked list. We will take two
cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning of the circular linked list.
Case 2: The new node is inserted at the end of the circular linked list.

Inserting a Node at the Beginning of a Circular Linked List

Suppose we want
to add a new
node with data 9
as the first node
of the list. Then
the following
changes will be
done in the
linked list.

15
This is the algorithm to insert a new node at the
beginning of a linked list. In Step 1, we first check
whether memory is available for the new node. If
the free memory has exhausted, then an
OVERFLOW message is printed. Otherwise, if a
free memory cell is available, then we allocate
space for the new node. Set its DATA part with the
given VAL and the NEXT part is initialized with
the address of the first node of the list, which is
stored in START. Now, since the new node is
added as the first node of the list, it will now be
known as the START node, that is, the START
pointer variable will now hold the address of the
NEW_NODE.
While inserting a node in a circular linked list, we have to use a while loop to traverse to the last node of
the list. Because the last node contains a pointer to START, its NEXT field is updated so that after
insertion it points to the new node which will be now known as START.

Inserting a Node at the End of a Circular Linked List

Suppose we want to add a new node with data 9 as the last node of the list. Then the following changes
will be done in the linked list.

Now let us see the algorithm to insert a new node at the end of a circular linked list. In Step 6, we take a
pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked
list. In the while loop, we traverse through the linked list to reach the last node. Once we reach the last
node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node.
Remember that the NEXT field of the new node contains the address of the first node which is denoted by
START.

16
Deleting a Node from a Circular Linked List
In this section, we will discuss how a node is deleted from an already existing circular linked list. We will
take two cases and then see how deletion is done in each case. Rest of the cases of deletion are same as
that given for singly linked lists.
Case 1: The first node is deleted.
Case 2: The last node is deleted.

Deleting the First Node from a Circular Linked List

When we want to delete a node from the beginning of the list, then the following changes will be done in
the linked list.

Fig: Deleting the first node from a circular linked list

Now let us check the algorithm to delete the first node from a circular linked list. In Step 1 of the
algorithm, we check if the linked list exists or not. If START = NULL, then it signifies that there are no
nodes in the list and the control is transferred to the last statement of the algorithm. However, if there are
nodes in the linked list, then we use a pointer variable PTR which will be used to traverse the list to

17
ultimately reach the last node. In Step 5, we change the next pointer of the last node to point to the second
node of the circular linked list. In Step 6, the memory occupied by the first node is freed. Finally, in Step
7, the second node now becomes the first node of the list and its address is stored in the pointer variable
START.

Deleting the Last Node from a Circular Linked List

Suppose we want to delete the last node from the linked list, then the following changes will be done in
the linked list.

Now let us see the algorithm to delete the last node from a circular linked list. In Step 2, we take a pointer
variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In
the while loop, we take another pointer variable PREPTR such that PREPTR always points to one node
before PTR. Once we reach the last node and the second last node, we set the next pointer of the second
last node to START, so that it now becomes the (new) last node of the linked list. The memory of the
previous last node is freed and returned to the free pool.

18
Doubly Linked Lists
A doubly linked list or a two-way linked list is a more complex type of linked list which contains a
pointer to the next as well as the previous node in the sequence.
Therefore, it consists of three parts—data, a pointer to the next node, and a pointer to the previous node.

In C, the structure of a doubly linked list can be given as

struct node
{
struct node *prev;
int data;
struct node *next;
};
The PREV field of the first node and the NEXT field of the last node will contain NULL.
The PREV field is used to store the address of the preceding node, which enables us to traverse the list in
the backward direction.
Thus, we see that a doubly linked list calls for more space per node and more expensive basic operations.
However, a doubly linked list provides the ease to manipulate the elements of the list as it maintains
pointers to nodes in both the directions (forward and backward).
The main advantage of using a doubly linked list is that it makes searching twice as efficient.

In the figure, we see that a variable START is used to store

the address of the first node. In this example, START = 1, so
the first data is stored at address 1, which is H.
Since this is the first node, it has no previous node and hence
stores NULL or –1 in the PREV field.
We will traverse the list until we reach a position where the
NEXT entry contains –1 or NULL. This denotes the end of
the linked list.

19
When we traverse the DATA and NEXT in this manner, we will finally see that the linked list in the above
example stores characters that when put together form the word HELLO.

Inserting a New Node in a Doubly Linked List

In this section, we will discuss how a new node is added into an already existing doubly linked list. We
will take four cases and then see how insertion is done in each case.
Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.

Inserting a Node at the Beginning of a Doubly Linked List

Suppose we want to add a new node with data 9 as the first node of the list. Then the following changes
will be done in the linked list.

Now, let us check the algorithm to insert a new node at the beginning of a doubly linked list.
In Step 1, we first check whether memory is available for the new node. If the free memory has
exhausted, then an OVERFLOW message is printed. Otherwise, if free memory cell is available, then we
allocate space for the new node.
Set its DATA part with the given VAL and the NEXT
part is initialized with the address of the first node of the
list, which is stored in START. Now, since the new node
is added as the first node of the list, it will now be
known as the START node, that is, the START pointer
variable will now hold the address of NEW_NODE.

Inserting a Node at the End of a Doubly Linked

List
Suppose we want to add a new node with data 9 as the
last node of the list. Then the following changes will be
done in the linked list.

20
Now let us check the algorithm to insert a new
node at the end of a doubly linked list.
In Step 6, we take a pointer variable PTR and
initialize it with START. In the while loop, we
traverse through the linked list to reach the
last node.
Once we reach the last node, in Step 9, we
change the NEXT pointer of the last node to
store the address of the new node.
Remember that the NEXT field of the new
node contains NULL which signifies the end
of the linked list. The PREV field of the
NEW_NODE will be set so that it points to
the node pointed by PTR (now the second last
node of the list).

Inserting a Node after a given node in a Doubly Linked List

Suppose we want to add a new node with value 9 after the node containing 3.

21
In Step 5, we take a pointer PTR and initialize it with START. That is, PTR now points to the first node of
the linked list.
In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM.
We need to reach this node because the new node will be inserted after this node. Once we reach this
node, we change the NEXT and PREV fields in such a way that the new node is inserted after the desired
node.

Inserting a Node before a given node in a Doubly Linked List

Suppose we want to add a new node with value 9 before the node containing 3.

22
In Step 1, we first check whether memory is available for the new node. In Step 5, we take a pointer
variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list.
In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM.
We need to reach this node because the new node will be inserted before this node. Once we reach this
node, we change the NEXT and PREV fields in such a way that the new node is inserted before the
desired node.

Deleting the first node from a Doubly Linked List

In this section, we will see how a node is deleted from an already existing doubly linked list. We will take
four cases and then see how deletion is done in each case.
Case 1: The first node is deleted.
Case 2: The last node is deleted.

23
 Case 3: The node after a given node is deleted.
Case 4: The node before a given node is deleted

Deleting the first node from a Doubly Linked List

When we want to delete a node from the beginning of the list, then the following changes will be done in
the linked list.

Let us check the algorithm to delete the first node of a doubly linked list.
In Step 1 of the algorithm, we check if the linked list exists
or not. If START = NULL, then it signifies that there are no
nodes in the list and the control is transferred to the last
statement of the algorithm.
However, if there are nodes in the linked list, then we use a
temporary pointer variable PTR that is set to point to the first
node of the list. For this, we initialize PTR with START that
stores the address of the first node of the list.
In Step 3, START is made to point to the next node in
sequence and finally the memory occupied by PTR (initially
the first node of the list) is freed and returned to the free
pool.

Deleting a Last Node from a Doubly Linked List

Suppose we want to delete the last node from the linked list, then the following changes will be done in
the linked list.

Now let us check the algorithm to delete the last node of a doubly linked list.

24
In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the
first node of the linked list.
The while loop traverses through the list to reach the last node. Once we reach the last node, we can also
access the second last node by taking its address from the PREV field of the last node.
To delete the last node, we simply have to set the next field of second last node to NULL, so that it now
becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned
to the free pool.

Deleting the Node after a given node in a Doubly Linked List

Suppose we want to delete the node that succeeds the node which contains data value 4. Then the
following changes will be done in the linked list.

Let's check the algorithm to delete a node after a given node of a doubly linked list.
In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the
first node of the doubly linked list.
The while loop traverses through the linked list to reach the given node.
Once we reach the node containing VAL, the node succeeding it can be easily accessed by using the
address stored in its NEXT field.
The NEXT field of the given node is set to contain the contents in the NEXT field of the succeeding node.
Finally, the memory of the node succeeding the given node is freed and returned to the free pool.

25
Deleting the Node before a given node in a Doubly Linked List
Suppose we want to delete the node preceding the node with value 4. Before discussing the changes that
will be done in the linked list, let us first look at the algorithm.

Let us check the algorithm m to delete a node before a given node of a doubly linked list.

26
In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the
first node of the linked list.
The while loop traverses through the linked list to reach the desired node. Once we reach the node
containing VAL, the PREV field of PTR is set to contain the address of the node preceding the node
which comes before PTR.
The memory of the node preceding PTR is freed and returned to the free pool.

27