DATA STRUCTURES

2-1 CSE (R19)

UNIT-2
UNIT-2 SYLLABUS
 2.1 Linked List:
 Introduction
 Basic Concepts
 Representation of Linked list in memory—Examples
 Memory Allocation and De-allocation for Linked Lists
 Linked Lists vs Arrays
 2.2 Single linked list
 Operations on Single Linked list-
 Insertion
 Deletion
 Search and Traversal
 Reversing Single Linked list
 Applications on Single Linked list-
 Polynomial Expression
 Representation
 Addition
 Multiplication
 Sparse Matrix Representation using Linked List
 Advantages and Disadvantages of Single Linked list
 2.3 Doubly Linked list-
 Insertion
 Deletion
 2.4 Circular Linked list- 2
 Insertion
 Deletion
2.1 LINKED LISTS – INTRODUCTION
 An array is a linear collection of data elements in which the
elements are stored in consecutive memory locations.
 To make efficient use of memory, the elements must be stored
randomly at any location rather than in consecutive 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.
 Linked list is a data structure that is free from the above said
restrictions. A linked list does not store its elements in
consecutive memory locations and the user can add any number
of elements to it.
 A linked list does not allow random access of data.
 Elements in a linked list can be accessed only in a sequential
manner.
 Insertions and deletions can be done at any point in the list in a
constant time. 3
 LINKED LISTS– BASIC CONCEPTS
 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.
 It acts as a building block to implement data structures such as stacks, queues.
 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.

Simple Linked List

• In the above figure, we have a linked list in which every node contains two parts.
•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. In Fig, the NULL pointer is represented by X. A NULL pointer denotes
the end of the list.
• In a linked list, every node contains a pointer to another node which is of the same 4
type, it is also called a self-referential data type.
LINKED LIST REPRESENTATION IN
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 C, we can implement a linked list using the following
code: struct node
{
int data;
struct node
*next;
};
• 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.
• If START = NULL, then the linked list is empty and contains no
nodes. 5
MEMORY REPRESENTATION-EXAMPLE-1
 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,
which denotes the end of the linked list.
 The figure shows a chunk of memory locations START pointing to the first
which range from 1 to 10. The shaded portion element of the linked list in
contains data for other applications. the memory
 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, 6
4, 7, 8, and 10.
MEMORY REPRESENTATION-EXAMPLE-2
 The DATA part of a node
may contain just a single
data item, an array, or a
structure.
 Let us take an example to
see how a structure is
maintained in a linked
list that is stored in the
memory.
 Consider a scenario in
which the roll number,
name, aggregate, and
grade of students are
stored using linked lists.
 In the figure, we see how
the NEXT pointer is used
to store the data
Students Linked List
alphabetically. 7
MEMORY ALLOCATION AND DE-ALLOCATION FOR A
LINKED LIST
 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 in Figure
which contains the roll
number of students, marks
obtained by them in Biology,
and finally a NEXT field
which stores the address of
Students Linked
the next node in sequence. List

8
MEMORY ALLOCATION AND DE-ALLOCATION FOR A
LINKED LIST
 Now, if a new student joins the
class, 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 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.
 The computer maintains a list of
all free memory cells. This list of
available space is called the free
linked list after the
pool. insertion of new student’s
record 9
MEMORY ALLOCATION AND DE-ALLOCATION FOR A
LINKED LIST
 We have a pointer variable AVAIL
which stores the address of the first free
space.
 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.
 For example, in Figure, when the first
free memory space is utilized for
inserting the new node, AVAIL will be
set to contain address 6.
 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
Linked list with AVAIL
that the memory can be reused by some
and START pointers
other program that needs memory
space. 10

 The operating system does this task of

adding the freed memory to the free
LINKED LISTS VS ARRAYS
 Both arrays and linked lists are a linear collection of
data elements.
 An array stores elements in consecutive memory
locations. A linked list does not store its nodes in
consecutive memory locations.
 An array allows random access of elements where as
a linked list does not allow random access of data.
Nodes in a linked list can be accessed only in a
sequential manner.
 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.
11
2.2 SINGLE LINKED LIST
 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.
 Every node stores the address of the next node in
sequence. The last node stores NULL pointer.
 A singly linked list allows traversal of data only
in one way.

Single Linked
list
12
SINGLE LINKED LIST-- OPERATIONS
 Traversing
 Searching

 Inserting
 Inserting a Node at the Beginning
 Inserting a Node at the End
 Inserting a Node After a Given Node
 Inserting a Node Before a Given Node
 Deleting
 Deleting the First Node
 Deleting the Last Node
 Deleting the Node After a Given Node
13
 TRAVERSING A SINGLE 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
that PTR points to the first node of
the linked list.
• 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 Algorithm for Traversing a Single Linked
node pointed by PTR. list
• In Step 4, we move to the next node
by making the PTR variable point to 14
the node whose address is stored in
the NEXT field.
 SEARCHING A SINGLE LINKED LIST
 Searching a linked list means to find a particular element in the
linked list.
 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, we compare every node’s
DATA with VAL for which the search
is being made.
• If the search is successful then the
address of that node is stored in POS
and the control jumps to the last
statement of the algorithm.
• If the search is unsuccessful, POS is
set to NULL which indicates that Algorithm for Searching a
VAL is not present in the linked list. Single Linked list 15
SEARCHING A SINGLE LINKED LIST--
EXAMPLE
 If we have search element i.e., VAL = 4, then the flow of the
algorithm can be explained as shown in the below figure.

16
INSERTING A NEW NODE IN A SINGLE 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.
 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.

17
CASE-1: INSERTING A NODE AT THE BEGINNING OF A
LINKED LIST
 Consider the linked list shown in below Figure.
 Suppose we want to add a new node with data 9 and add it
as the first node of the list.
 The following changes will be done in the linked list.

18
CASE-1: INSERTING A 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. Algorithm to insert a new
node at
 Now the new node will be known as the the beginning
START node, that is, the START pointer
variable will now hold the address of the
NEW_NODE.
 Steps 2, 3 allocate memory for the new
node.

19
CASE-2: INSERTING A NODE AT THE END OF A LINKED LIST
 Consider the linked list shown in the Figure.
 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
CASE-2: INSERTING A NODE AT THE END OF A LINKED LIST
 In Step 6, we take a pointer
variable PTR and initialize it with
START.
 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.
 The NEXT field of the new node Algorithm to insert a new
contains NULL, which signifies the node at
end of the linked list. the end

21
CASE-3: INSERTING A NODE AFTER A GIVEN NODE IN A
LINKED LIST
 Consider the linked list shown in the Figure.
 Suppose we want to add a new node with data 9 after the node containing data
3.
 Then the following changes will be done in the linked list.

22
CASE-3: INSERTING A NODE AFTER A GIVEN NODE IN A
LINKED LIST
 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.
 We take another pointer variable
PREPTR which will be used to store
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.
Algorithm to insert a new
 Once we reach this node, in Steps 10 node after a given node
and 11, we change the NEXT
pointers in such a way that new node
is inserted after the desired node.
23
CASE-4: INSERTING A NODE BEFORE A GIVEN NODE IN A
LINKED LIST
 Consider the linked list shown in the Figure.
 Suppose we want to add a new node with data 9 before the node containing data
3.
 Then the following changes will be done in the linked list.

24
CASE-4: INSERTING A NODE BEFORE A GIVEN NODE IN A
LINKED LIST
 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.
 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.
 Once we reach this node, in Steps Algorithm to insert a new
10 and 11, we change the NEXT node before a given node
pointers in such a way that the
new node is inserted before the
desired node. 25
DELETING A NODE IN A SINGLE LINKED LIST

 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.
 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.
 When we delete a node from a linked list, we 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 26
vacated.
CASE-1: DELETING THE FIRST NODE FROM A LINKED
LIST
 Consider the linked list shown in below Figure.
 When we want to delete a node from the beginning of the list, then the
following changes will be done in the 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.
• 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 Algorithm to delete the first node 27
PTR is freed and returned to the free pool.
CASE-2: DELETING THE LAST NODE FROM A LINKED
LIST
 Consider the linked list shown in below Figure.
 When we want to delete the last node from the list, then the following
changes will be done in the linked list..

28
CASE-2: DELETING THE LAST NODE FROM A LINKED
LIST

Algorithm to delete the last node

 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.
 We take another pointer variable PREPTR such that it always points to one
node before the 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 29
pool.
CASE-3: DELETING THE NODE AFTER A GIVEN NODE IN A
LINKED LIST
 Consider the linked list shown in below Figure.
 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.

30
CASE-3: DELETING THE NODE AFTER A GIVEN NODE IN A
LINKED LIST

Algorithm to delete the node after a given

node
 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.
 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 next field of the node succeeding it.
 The memory of the node succeeding the given node is freed and returned 31
back to the free pool.
 REVERSING A SINGLE LINKED LIST
1. Create two more pointers other than head namely prevNode and curNode that will
hold the reference of previous node and current node respectively.
Make sure that prevNode points to first node i.e. prevNode = head.
head should now point to its next node i.e. the second node head = head->next.
curNode should also points to the second node i.e. curNode = head.

2. Now, disconnect the previous node i.e. the first node from others. We will make
sure that it points to none. As this node is going to be our last node. Perform
operation prevNode->next = NULL.

32
 REVERSING A SINGLE LINKED LIST
3. Move head node to its next node i.e. head = head->next

4. Now, re-connect the current node to its previous node i.e. curNode->next =
prevNode;.

5. Point the previous node to current node and current node to head node. Means
they should now point to prevNode = curNode; and curNode = head.

33
 REVERSING A SINGLE LINKED LIST
6. Repeat steps 3-5 till head pointer becomes NULL.

34
REVERSING A SINGLE LINKED LIST
7. Now, after all nodes has been re-connected in the reverse order. Make the last
node as the first node. Means the head pointer should point to prevNode pointer.
Perform head = prevNode;. Finally you end up with a reversed linked list of its
original.

Algorithm to reverse a
Singly Linked List

35
APPLICATIONS OF A SINGLE LINKED
LIST
Polynomial Representation
 Consider a polynomial 6x3 + 9x2 + 7x + 1. Every individual term in a
polynomial consists of two parts, a coefficient and a power. Here, 6, 9, 7,
and 1 are the coefficients of the terms that have 3, 2, 1, and 0 as their
powers respectively.
 Every term of a polynomial can be represented as a node of the linked list.
The following Figure shows the linked representation of the terms of the
above polynomial.

Linked representation of a polynomial

Polynomials Addition
Let us consider P and Q be two polynomials having three terms each.
P= 30x2 + 20x + 100 —————(1)
Q= 60x3 + 50x2 + 60x——————(2)
we can represent these two polynomials as:-

36
POLYNOMIAL
ADDITION

 Step 1: Compare the exponent of P and the

corresponding exponent of Q.
here expo(p) < expo(q)
so, add the terms pointer to by q to the resultant
list and now advanced the q pointer.

37
POLYNOMIAL
ADDITION

 Step 2: Here we compare the exponents of the

current items between given P and Q.
expo(p) = expo(q)
therefore, add the coefficients of these two terms and
link this to the resultant list and advance the pointers
p and q to their next nodes.

38
POLYNOMIAL
ADDITION
 Step 3: We compare the exponents of the current terms
again
expo(p)=expo(q)
therefore, we add the coefficients of these two terms and link
this to the resultant linked list and advance the pointers to
their next.
We notice that nodes Q reaches the NULL and P points the
last node.

39
POLYNOMIAL
ADDITION

 Step 4:In the above step, we notice that there is

no node in the second polynomial to compare with.
So the last node in the first polynomial is added to
the end of the resultant linked list. The resultant
linked list is the final output.

R= 60x3 + 80x2 + 80x + 100

40
APPLICATIONS OF A SINGLE LINKED
LIST
Polynomial Multiplication
 Given two polynomials in the form of linked list. The task is to find the
multiplication of both polynomials.
Approach:
 In this approach we will multiply the 2nd polynomial with each term of 1st
polynomial.
 Store the multiplied value in a new linked list.
 Then we will add the coefficients of elements having the same power in resultant
polynomial.
Example-1:
Input: Poly1: 3x2 + 5x + 6 Poly2: 6x + 8
On multiplying each element of 1st polynomial with elements of 2nd polynomial, we
get 18x3 + 24x2 + 30x2 + 40x + 36x + 48 On adding values with same power of x, we
get resultant polynomial.
Output: 18x3 + 54x2 + 76x + 48

41
APPLICATIONS OF A SINGLE LINKED
LIST
Sparse Matrix Representation
 A matrix is a two-dimensional data object made of
m rows and n columns, therefore having total m x n
values.
 If most of the elements of the matrix have 0 value,
then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple
matrix ?
 Storage: There are lesser non-zero elements than
zeros and thus lesser memory can be used to store
only those elements.
 Computing time: Computing time can be saved by
logically designing a data structure traversing only
42
non-zero elements.
SPARSE MATRIX REPRESENTATION USING
LINKED LIST

 In linked list, each node has four fields. These four

fields are defined as:
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is
located
 Value: Value of the non zero element located at index –
(row,column)
 Next node: Address of the next node

43
ADVANTAGES AND DISADVANTAGES OF SINGLE
LINKED LIST
ADVANTAGES :-

1. Insertions and Deletions can be done easily.

2. It does not need movement of elements for insertion and deletion.
3. It’s space is not wasted as we can get space according to our
requirements.
4. It’s size is not fixed.
5. It can be extended or reduced according to requirements.
6. Elements may or may not be stored in consecutive memory
It is less expensive.

DISADVANTAGES :-
1. It requires more space as pointers are also stored with information.
2. Different amount of time is required to access each element.
3. If we have to go to a particular element then we have to go through all
those elements that come before that element.
4. We can not traverse it from last & only from the beginning.
5. It is not easy to sort the elements stored in the linear linked list.. 44
2.3 DOUBLY LINKED LIST
 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 as shown in Fig

Doubly Linked
list
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 is used to store the address of the preceding node, which enables us
to traverse the list in the backward direction. 45
• The PREV field of the first node and the NEXT field of the last node will contain
NULL.
 MEMORY REPRESENTATION OF DOUBLY
LINKED LIST
 A doubly linked list calls for more space per node and more expensive
basic operations.
 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.
• When we traverse the DATA and NEXT in
this manner, we will finally see that the Memory 46
linked list in the above example stores Representation of
characters that when put together form the Doubly Linked list
word HELLO.
 INSERTING A NEW NODE IN A 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.
CASE-1: INSERTING A NODE AT THE BEGINNING OF A DOUBLY
LINKED LIST
• Consider the doubly linked list shown in Fig.
• 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.

47
CASE-1: INSERTING A 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 Algorithm to insert a new node at
list, it will now be known as the
START node, that is, the START the beginning
pointer variable will now hold
the address of NEW_NODE. 48
CASE-2: INSERTING A NODE AT THE END OF A DOUBLY LINKED LIST

• Consider the doubly linked list shown in Fig.

• 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.

49
CASE-2: INSERTING A 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.
 The NEXT field of the new
node contains NULL which
signifies the end of the linked
list.
 The PREV field of the
Algorithm to insert a new node at
NEW_NODE will be set so that
it points to the node pointed by the end
PTR (now the second last node
of the list). 50
CASE-3: INSERTING A NODE AFTER A GIVEN NODE IN A DOUBLY
LINKED LIST
• Consider the doubly linked list shown in Fig.
• Suppose we want to add a new node with data 9 after the node containing 3.
• Then the following changes will be done in the linked list.

51
CASE-3: INSERTING A NODE AFTER A GIVEN NODE IN A DOUBLY
LINKED LIST

 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 Algorithm to insert a new node
new node is inserted after the after a given node
desired node.
52
CASE-4: INSERTING A NODE BEFORE A GIVEN NODE IN A DOUBLY
LINKED LIST
• Consider the doubly linked list shown in Fig.
• Suppose we want to add a new node with data 9 before the node containing 3.
• Then the following changes will be done in the linked list.

53
CASE-4: INSERTING A NODE BEFORE A GIVEN NODE IN A DOUBLY
LINKED LIST

 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 Algorithm to insert a new node
fields in such a way that the new before a given node
node is inserted before the
desired node. 54
 DELETING A NODE IN A DOUBLY LINKED LIST
 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.
 Case 3: The node after a given node is deleted.
 Case 4: The node before a given node is deleted.
CASE-1: DELETING THE FIRST NODE FROM A DOUBLY LINKED LIST
• Consider the doubly linked list shown in Fig.
• When we want to delete a node from the beginning of the list, then the following
changes will be done in the linked list.

55
CASE-1: DELETING THE FIRST NODE FROM 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.
 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 Algorithm to delete 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 56
free pool..
CASE-2: DELETING THE LAST NODE FROM A DOUBLY LINKED LIST

• Consider the doubly linked list shown in Fig.

• Suppose we want to delete the last node of the list.
• Then the following changes will be done in the linked list.

57
CASE-2: DELETING THE LAST NODE FROM 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
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 Algorithm to delete the last node
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. 58
CASE-3: DELETING THE NODE AFTER A GIVEN NODE IN A DOUBLY
LINKED LIST
• Consider the doubly linked list shown in Fig.
 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.

59
CASE-3: DELETING THE NODE AFTER A GIVEN NODE IN 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 Algorithm to delete a node after a
is set to contain the contents in the given node
NEXT field of the succeeding node.
 Finally, the memory of the node
succeeding the given node is freed
and returned to the free pool. 60
CASE-4: DELETING THE NODE BEFORE A GIVEN NODE IN A DOUBLY
LINKED LIST
 Consider the doubly linked list shown in Fig.
 Suppose we want to delete the node preceding the node with value
4..
 Then the following changes will be done in the linked list.

61
CASE-4: DELETING THE NODE BEFORE A GIVEN NODE IN 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
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. Algorithm to delete a node before
a given node
 The memory of the node
preceding PTR is freed and
returned to the free pool.
62
ADVANTAGES AND DISADVANTAGES OF DOUBLY
LINKED LIST
ADVANTAGES :-

1. We can traverse in both direction i.e from starting to end & as well
as from end to starting.
2. It is easy to reverse the linked list.
3. If we are at a node, then we can go to any node.

DISADVANTAGES :-

1. It requires more space per space per node because extra field is
required for pointer to previous node.
2. Insertion and Deletion take more time than single linked list
because more pointer operations are required than single linked
63
list.
2.4 CIRCULAR LINKED LIST
 In a circular linked list, the last node contains a pointer to the first node
of the 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.
 There are no NULL values in the NEXT part of any of the nodes of list.

Circular Linked
list
Applications:
• Circular linked lists are widely used in operating systems for task
maintenance.
• When we are surfing the Internet, we can use the Back button and the
Forward button to move to the previous pages that we have already visited. A
circular linked list is used to maintain the sequence of the Web pages visited 64
MEMORY REPRESENTATION OF CIRCULAR
LINKED LIST
 Consider the Figure, where we
store the string HELLO in a
Circular Linked List.
 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.
 When we traverse the DATA and
NEXT in this manner, we will
finally see that the linked list in
the Figure stores characters that
Memory
when put together form the word Representation of
HELLO. Circular Linked list

65
INSERTING A NEW NODE IN A CIRCULAR
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.
 Case
CASE -1: 2: The new node
INSERTING A is
Ninserted
ODE ATatTHE
the end.
BEGINNING OF A CIRCULAR
LINKED LIST
• Consider the circular linked list shown in Fig.
• 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.

66
CASE-1: INSERTING A NODE AT THE BEGINNING OF A CIRCULAR
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.
 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, 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 Algorithm to insert a new node at
pointer to START, its NEXT field is the beginning
updated so that after insertion it
points to the new node which will be
now known as START. 67
CASE-2: INSERTING A NODE AT THE END OF A CIRCULAR LINKED
LIST

• Consider the circular linked list shown in Fig.

• 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.

68
CASE-2: INSERTING A 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 Algorithm to insert a new node at
which is denoted by START. the end

69
DELETING A NODE IN A CIRCULAR LINKED LIST
 We will see 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.
 Case 1: The first node is deleted.
CASE-1: DELETING THE FIRST NODE FROM A CIRCULAR LINKED
 Case 2: The last node is deleted.
LIST
• Consider the circular linked list shown in Fig.
• When we want to delete a node from the beginning of the list, then the following
changes will be done in the linked list.

70
CASE-1: DELETING 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.
 If there are nodes in the linked list,
then we use a pointer variable PTR
which will be used to traverse the
list to 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 Algorithm to delete the first node
linked list.
 In Step 6, the memory occupied by
the first node is freed.
 Finally, in Step 7, the second node 71
now becomes the first node of the
list and its address is stored in the
pointer variable START.
CASE-2: DELETING THE LAST NODE FROM A CIRCULAR LINKED
LIST

• Consider the circular linked list shown in Fig.

• Suppose we want to delete the last node of the list.
• Then the following changes will be done in the linked list.

72
CASE-2: DELETING THE LAST NODE FROM A CIRCULAR LINKED
LIST
 In Step 2, we take a pointer
variable PTR and initialize it
with START.
 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
Algorithm to delete the last node
the linked list.
 The memory of the previous last
node is freed and returned to the
free pool. 73
ADVANTAGES AND DISADVANTAGES OF CIRCULAR
LINKED LIST

ADVANTAGES :-

1. If we are at a node, then we can go to any node. But in linear linked

list it is not possible to go to previous node.
2. It saves time when we have to go to the first node from the last
node. It can be done in single step because there is no need to
traverse the in between nodes. But in double linked list, we will
have to go through in between nodes.

DISADVANTAGES :-
1. It is not easy to reverse the linked list.
2. If proper care is not taken, then the problem of infinite loop can
occur.
3. If we at a node and go back to the previous node, then we can not do
it in single step. Instead we have to complete the entire circle by
going through the in between nodes and then we will reach the 74
required node.
QUESTION BANK
1. What is a linked list? Explain the memory representation of a simple
linked list with an example.
2. Explain the allocation and de-allocation of memory for a linked list
with an example.
3. Differentiate arrays and linked lists.
4. Write the algorithm for Traversing a Single Linked List.
5. Explain the algorithm for Searching a Single Linked List with an
example.
6. Explain the algorithm for Reversing a Single Linked List with an
example.
7. Explain the different cases of Inserting a new Node in a Single
Linked List with relevant examples.
8. Explain the different cases of Deleting a Node in a Single Linked List
with relevant examples.
9. Explain with examples how polynomial addition and multiplication is
performed using linked list.
75
10. Explain sparse matrix representation using linked list with an
example
QUESTION BANK
12. What is a Doubly linked list? Explain the memory representation of a
Doubly linked list with an example.
13. Explain the different cases of Inserting a new Node in a Doubly
Linked List with relevant examples.
14. Explain the different cases of Deleting a Node in a Doubly Linked
List with relevant examples.
15. List the advantages and disadvantages of Doubly Linked List.
16. What is a Circular linked list? Explain the memory representation of
a Circular linked list with an example.
17. Explain the different cases of Inserting a new Node in a Circular
Linked List with relevant examples.
18. Explain the different cases of Deleting a Node in a Circular Linked
List with relevant examples.
19. List the advantages and disadvantages of Circular Linked List.

76