CHAPTER 1: INTRODUCTION TO STACKS, QUEUES AND

LINKED LISTS

DETAILED CONTENT :
➢ Introduction to Data Structures: Linear and Non-Linear Data Structures, Static and
Dynamic Data Structures.
➢ Concept of Stack and Queue. Array Implementation of Stack and Queue, Circular
Queue, Double Ended Queue, Priority Queue.
➢ Concept of Linked Lists. Singly linked lists, doubly linked lists and circular linked lists.
➢ Insertion, deletion, update and copying operations with Singly linked lists, doubly
linked lists and circular linked lists. Reversing a singly linked list.

TT 1
 ➢ INTRODUCTION TO DATA STRUCTURES
A data structure is basically a group of data elements that are put together under one name, and
which defines a particular way of storing and organizing data in a computer so that it can be
used efficiently.
Data structures are used in almost every program or software system. Some common examples
of data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables. Data
structures are widely applied in the following areas:
• Compiler design • Numerical analysis
• Operating system • Simulation
• Statistical analysis package • Artificial intelligence
• DBMS • Graphics

➢ Elementary Data structure organization

Data structures are building blocks of a program. A program built using improper data
structures may not work as expected. So as a programmer it is mandatory to choose most
appropriate data structures for a program.
• Data: The term data means a value or set of values. It specifies either the value of
a variable or a constant.
• Record: A record is a collection of data items. For example, the name, address,
course, and marks obtained are individual data items.
• File: A file is a collection of related records. For example, if there are 60 students
in a class, then there are 60 records of the students. All these related records are
stored in a file.

➢ LINEAR AND NON-LINEAR DATA STRUCTURES

Data structures are generally categorized into two classes: primitive and non-primitive data
structures.
• Primitive data structures are the fundamental data types which are supported by a
programming language. Some basic data types are integer, real, character, and Boolean.
• Non-primitive data structures are those data structures which are created using primitive
data structures. Examples of such data structures include linked lists, stacks, trees, and

TT 2
 graphs. Non-primitive data structures can further be classified into two categories: linear
and non-linear data structures.

• Linear Data Structure: If the elements of a data structure are stored in a linear or
sequential order, then it is a linear data structure. Examples include arrays, linked lists,
stacks, and queues. Linear data structures can be represented in memory in two different
ways. One way is to have to a linear relationship between elements by means of sequential
memory locations. The other way is to have a linear relationship between elements by
means of links.
• Non – Linear Data Structure: If the elements of a data structure are not stored in a
sequential order, then it is a non-linear data structure. The relationship of adjacency is not
maintained between elements of a non-linear data structure. Examples include trees and
graphs.

➢ STATIC AND DYNAMIC DATA STRUCTURES

• Static Data Structure: In Static data structure the size of the structure is fixed. The content
of the data structure can be modified but without changing the memory space allocated to
it. Some advantages of static data structure are data type size is fixed, Memory allocation
before program execution., Stack is used, less efficient than dynamic data structure,
Overflow is not possible.

TT 3
 • Dynamic Data Structure: The size of the structure in not fixed and can be modified
during the operations performed on it. Dynamic data structures are designed to facilitate
change of data structures in the run time. Some advantages of dynamic data structure are
memory allocation is done during program execution, Heap is used, more efficient,
memory reuse.

➢ OPERATIONS ON DATA STRUCTURES

1. Traversing: It means to access each data item exactly once so that it can be processed.
2. Searching: It is used to find the location of one or more data items that satisfy the given
constraint. Such a data item may or may not be present in the given collection of data items.
3. Inserting: It is used to add new data items to the given list of data items.
4. Deleting: It means to remove (delete) a particular data item from the given collection of
data items.
5. Sorting: Data items can be arranged in some order like ascending order or descending
order depending on the type of application.
6. Merging: Lists of two sorted data items can be combined to form a single list of sorted
data items.

➢ ABSTRACT DATA TYPE

Data type of a variable is the set of values that the variable can take. The basic data types in C
include int, char, float, and double. The word ‘abstract’ in the context of data structures means
considered apart from the detailed specifications or implementation.

An abstract data type (ADT) is the way we look at a data structure, focusing on what it does
and ignoring how it does its job. The end-user is not concerned about the details of how the
methods carry out their tasks. They are only aware of the methods that are available to them
and are only concerned about calling those methods and getting the results. They are not
concerned about how they work.

TT 4
 ➢ ALGORITHM
The typical definition of algorithm is ‘a formally defined procedure for performing some
calculation’. Algorithms are mainly used to achieve software reuse. Once we have an idea or
a blueprint of a solution, we can implement it in any high-level language like C, C++, or Java.
An algorithm is basically a set of instructions that solve a problem. It is not uncommon to have
multiple algorithms to tackle the same problem, but the choice of a particular algorithm must
depend on the time and space complexity of the algorithm.
There are two main approaches to design an algorithm—top-down approach and bottom-up
approach.
• Top Down Approach: A top-down design approach starts by dividing the complex
algorithm into one or more modules. These modules can further be decomposed into one
or more sub-modules, and this process of decomposition is iterated until the desired level
of module complexity is achieved. Top-down design method is a form of stepwise
refinement where we begin with the topmost module and incrementally add modules that
it calls.
• Bottom Up Approach: A bottom-up approach is just the reverse of top-down approach.
In the bottom-up design, we start with designing the most basic or concrete modules and
then proceed towards designing higher level modules. The higher-level modules are
implemented by using the operations performed by lower level modules. Thus, in this
approach sub-modules are grouped together to form a higher-level module. All the higher-
level modules are clubbed together to form even higher-level modules. This process is
repeated until the design of the complete algorithm is obtained

➢ TIME AND SPACE COMPLEXITY

The time complexity of an algorithm is basically the running time of a program as a function
of the input size. Similarly, the space complexity of an algorithm is the amount of computer
memory that is required during the program execution as a function of the input size.
Asymptotic analysis of an algorithm refers to defining the mathematical boundation/framing
of its run-time performance. Using asymptotic analysis, we can very well conclude the best
case, average case, and worst-case scenario of an algorithm.

TT 5
 1. Big Oh Notation O: The notation Ο(n) is the formal way to express the upper bound of an
algorithm's running time. It measures the worst-case time complexity or the longest amount
of time an algorithm can possibly take to complete.

O(f(n)) = g(n)

2. Omega Notation Ω : The notation Ω(n) is the formal way to express the lower bound of
an algorithm's running time. It measures the best-case time complexity or the best amount
of time an algorithm can possibly take to complete.

Ω (f (n)) >= g(n)

3. θ Notation: The notation θ(n) is the formal way to express both the lower bound and the
upper bound of an algorithm's running time. It is represented as follows:

θ (f (n)) = g(n)

TT 6
 ➢ CONCEPT OF STACKS
Stack is an important data structure which stores its elements in an ordered manner. A stack is
a linear data structure which uses the same principle, i.e., the elements in a stack are added and
removed only from one end, which is called the TOP. Hence, a stack is called a LIFO (Last-
In-First-Out) data structure, as the element that was inserted last is the first one to be taken out.

Fig.: Overview of stack

➢ Array Representation of Stack: In the computer’s memory, stacks can be represented as a

linear array. Every stack has a variable called TOP associated with it, which is used to store
the address of the topmost element of the stack. It is this position where the element will be
added to or deleted from. There is another variable called MAX, which is used to store the
maximum number of elements that the stack can hold. If TOP = NULL, then it indicates that
the stack is empty and if TOP = MAX–1, then the stack is full.

TT 7
 ➢ Application of stacks:
➢ Reversing a list
➢ Parentheses checker
➢ Conversion of an infix expression into a postfix expression
➢ Evaluation of a postfix expression
➢ Conversion of an infix expression into a prefix expression
➢ Evaluation of a prefix expression
➢ Recursion
➢ Tower of Hanoi

➢ OPERATIONS ON STACKS
A stack supports three basic operations: push, pop, and peek. The push operation adds an
element to the top of the stack and the pop operation removes the element from the top of the
stack. The peek operation returns the value of the topmost element of the stack.

1. Push Operation: The push operation is used to insert an element into the stack. The new
element is added at the topmost position of the stack. However, before inserting the value, we
must first check if TOP=MAX–1, because if that is the case, then the stack is full and no more
insertions can be done.
To insert an element with value E, we first check if TOP=MAX–1. If the condition is false,
then we increment the value of TOP and store the new element at the position given by stack
[TOP]. Thus, the updated stack becomes as shown below:

Fig: Top of the stack is Index 3 Fig: New element added E

TT 8
 ➢ Algorithm for Push Operation:
Step 1: IF TOP = MAX-1
PRINT “OVERFLOW”
Go to Step 4
[END OF IF]
Step 2: SET TOP = TOP+1
Step 3: SET STACK[TOP] = VALUE
Step 4: END

2. Pop Operation: The pop operation is used to delete the topmost element from the stack.
However, before deleting the value, we must first check if TOP=NULL because if that is the
case, then it means the stack is empty and no more deletions can be done. If an attempt is made
to delete a value from a stack that is already empty, an UNDERFLOW message is printed.

Fig: Top of the stack is Index 4 Fig: Element E is deleted

➢ Algorithm for Pop Operation:

Step 1: IF TOP = NULL
PRINT UNDERFLOW
Go to Step 4
[END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP-1
Step 4: END
3. Peek Operation: Peek is an operation that returns the value of the topmost element of the
stack without deleting it from the stack. The Peek operation first checks if the stack is empty,
i.e., if TOP = NULL, then an appropriate message is printed, else the value is returned.

Fig.: Top of the element is E

TT 9
 ➢ Algorithm for Peek Operation:
Step 1: IF TOP = NULL
PRINT STACK IS EMPTY
Go to Step 3
Step 2: RETURN STACK[TOP]
Step 3: END

➢ CONCEPT OF QUEUE
A Queue is a FIFO (First-In, First-Out) data structure in which the element that is inserted first
is the first one to be taken out. The elements in a queue are added at one end called the REAR
and removed from the other end called the FRONT.

➢ Array Representation of Queue: Queues can be easily represented using linear arrays. As
stated earlier, every queue has front and rear variables that point to the position from where
deletions and insertions can be done, respectively.

Fig.: Array Representation of Queue

➢ OPERATIONS ON QUEUE :
The Queues mainly perform two operations such as Insertion of new element at the Queue and
Deletion of element from the Queue.

1. Insertion of new element at the Queue: Suppose we want to add another element with new
value, then REAR would be incremented by 1 and the value would be stored at the position
pointed by REAR. The queue after addition would be as shown in Fig. Here, FRONT = 0 and
REAR = 6. Every time a new element has to be added, we repeat the same procedure.
However, before inserting an element in a queue, we must check for overflow conditions. An
overflow will occur when we try to insert an element into a queue that is already full. When

TT 10
 REAR = MAX – 1, where MAX is the size of the queue, we have an overflow condition. Note
that we have written MAX – 1 because the index starts from 0.

Fig.: The Front = 0 and Rear =4 Fig.: Add new element, The Front = 0 and Rear =5

➢ Algorithm to insert new element at the Queue

Step 1: IF REAR = MAX-1
Write OVERFLOW
Go to step 4
[END OF IF]
Step 2: IF FRONT=-1 and REAR=-1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR+1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT

2. Deletion of new element from the Queue: If we want to delete an element from the queue,
then the value of FRONT will be incremented. Deletions are done from only this end of the
queue. Before deleting an element from a queue, we must check for underflow conditions. An
underflow condition occurs when we try to delete an element from a queue that is already
empty. If FRONT = –1 and REAR = –1, it means there is no element in the queue.

Fig.: The Front = 0 and Rear =5 Fig.: The element is deleted, Front = 1 and Rear =5

TT 11
 ➢ Algorithm to delete element from the Queue
Step 1: IF FRONT = -1 OR FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT+1
[END OF IF]

Step 2: EXIT

➢ TYPES OF QUEUE:
1. Circular Queue: In Circular Queue, all the nodes are represented as circular. It is similar to
the linear Queue except that the last element of the queue is connected to the first element. It
is also known as Ring Buffer, as all the ends are connected to another end. The drawback that
occurs in a linear queue is overcome by using the circular queue. If the empty space is available
in a circular queue, the new element can be added in an empty space by simply incrementing
the value of rear.

Fig.: Circular Queue

2. Dequeue: In Deque or Double Ended Queue, insertion and deletion can be done from both
ends of the queue either from the front or rear. It means that we can insert and delete elements
from both front and rear ends of the queue. Deque can be used as a palindrome checker means
that if we read the string from both ends, then the string would be the same.

Fig.: Overview of Dequeue

TT 12
 There are two types of deque that are discussed as follows –

➢ Input restricted deque - As the name implies, in input restricted queue, insertion operation
can be performed at only one end, while deletion can be performed from both ends.

Fig.: Input restricted queue

➢ Output restricted deque - As the name implies, in output restricted queue, deletion operation
can be performed at only one end, while insertion can be performed from both ends.

Fig.: Output restricted queue

3. Priority Queue: It is a special type of queue in which the elements are arranged based on the
priority. It is a special type of queue data structure in which every element has a priority
associated with it. Suppose some elements occur with the same priority, they will be arranged
according to the FIFO principle. The representation of priority queue is shown in the below
image –

Fig.: Overview of priority queue

There are two types of priority queue that are discussed as follows –

➢ Ascending priority queue - In ascending priority queue, elements can be inserted in

arbitrary order, but only smallest can be deleted first
➢ Descending priority queue - In descending priority queue, elements can be inserted
in arbitrary order, but only the largest element can be deleted first.

TT 13
 4. Multiple Queue: When we implement a queue using an array, the size of the array must be
known in advance. If the queue is allocated less space, then frequent overflow conditions will
be encountered. To deal with this problem, the code will have to be modified to reallocate more
space for the array. In case we allocate a large amount of space for the queue, it will result in
sheer wastage of the memory. Thus, there lies a tradeoff between the frequency of overflows
and the space allocated. So, a better solution to deal with this problem is to have multiple
queues or to have more than one queue in the same array of sufficient size.

Fig.: Overview of Multiple Queue

➢ Applications of Queue:
• Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
• Queues are used to transfer data asynchronously (data not necessarily received at same rate
as sent) between two processes (IO buffers), e.g., pipes, file IO, sockets.
• Queues are used as buffers on MP3 players and portable CD players, iPod playlist.
• Queues are used in Playlist for jukebox to add songs to the end, play from the front of the
list.
• Queues are used in operating system for handling interrupts. When programming a real-
time system that can be interrupted, for example, by a mouse click, it is necessary to process
the interrupts immediately, before proceeding with the current job. If the interrupts have to
be handled in the order of arrival, then a FIFO queue is the appropriate data structure.

TT 14
 ➢ CONCEPT OF LINKED LISTS
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.

Fig.: Overview of linked list

1. In linked list each node contains two part first one is DATA which contains the integer
value and another node NEXT which contains the address of next node.
2. The START pointer contains the address of First node.
3. The last node of linked list contains the NULL value which defines the end of the linked
lists. In programming, the NULL value defines as -1.
4. If START = NULL that means the linked lists is empty.
5. 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.

Fig.: Linked List with memory allocation

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.

TT 15
 ➢ Difference Between Array and Linked Lists
Array Linked Lists
An array is a collection of elements of a A linked list is a collection of objects known
similar data type. as a node where node consists of two parts,
i.e., data and address.
Array elements store in a contiguous Linked list elements can be stored anywhere
memory location. in the memory or randomly stored.
Array works with a static memory. Here The Linked list works with dynamic
static memory means that the memory size is memory. Here, dynamic memory means that
fixed and cannot be changed at the run time. the memory size can be changed at the run
time according to our requirements.
Array elements are independent of each Linked list elements are dependent on each
other. other. As each node contains the address of
the next node so to access the next node, we
need to access its previous node.
Array takes more time while performing any Linked list takes less time while performing
operation like insertion, deletion, etc. any operation like insertion, deletion, etc.
In the case of an array, memory is allocated In the case of a linked list, memory is
at compile-time. allocated at run time.
Memory utilization is inefficient in the array. Memory utilization is efficient in the case of
For example, if the size of the array is 6, and a linked list as the memory can be allocated
array consists of 3 elements only then the rest or deallocated at the run time according to
of the space will be unused. our requirement.
Accessing any element in an array is faster Accessing an element in a linked list is
as the element in an array can be directly slower as it starts traversing from the first
accessed through the index. element of the linked list.

➢ Memory Allocation and De-Allocation for a Linked Lists

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

TT 16
 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.

➢ OPERATIONS ON LINKED LISTS

Following operations can be performed on Linked Lists.
• Traversing of a linked list.
• Find number of nodes at the linked list.
• Searching of a value in a linked list.
• Insertion of node at beginning, end, before given node and after given node at the linked
list.
• Deletion of node at beginning, end, before given node and after given node at the linked
list.
• Reversing of a linked list.

➢ TYPES OF LINKED LISTS

➢ SINGLY 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. 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. Below Figure shows a singly linked
list.

Fig.: Singly Linked Lists

1. Traversing a linked list
Traversing a linked list means accessing the nodes of the list in order to perform some
processing on them. For traversing the linked list, we also make use of another pointer variable
PTR which points to the node that is currently being accessed.

TT 17
 ➢ Algorithm for Traversing a linked List:
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4
while PTR! = NULL
Step 3: Apply Process to PTR -> DATA
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: EXIT

2. Find number of nodes at the linked list.

To count the number of nodes in a linked list, 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.

➢ Algorithm to print the number of nodes in a linked List

Step 1: [INITIALIZE] SET COUNT = 0
Step 2: [INITIALIZE] SET PTR = START
Step 3: Repeat Steps 4 and 5
while PTR! =NULL
Step 4: SET COUNT = COUNT + 1
Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 6: Write COUNT
Step 7: EXIT

3. Searching for a value in a linked List

Searching a linked list means to find a particular element in the linked list. 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.

TT 18
 ➢ Algorithm to Searching for a value in a linked List
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Step 3
while PTR! =NULL
Step 3: IF VAL = PTR -> DATA
SET POS = PTR
Go To Step 5
ELSE
SET PTR = PTR -> NEXT
[END OF IF]

[END OF LOOP]

Step 4: SET POS = NULL

Step 5: EXIT

➢ Insert a new node at the Singly linked list

A. Insert a new node at the beginning of a Singly linked list

To insert a new node at the beginning of a linked list, 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. The step 2 & 3 of an algorithm, 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.

TT 19
 ➢ Algorithm to Insert a new node at the beginning of the Singly linked list
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT

B. Insert a new node at the end of a Singly linked list

To insert a new node at the end of a linked list. In Algorithm 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.

TT 20
 ➢ Algorithm to Insert a new node at the beginning of the Singly linked list
Step 1: IF AVAIL = NULL end
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR -> NEXT! =NULL
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODW
Step 10: EXIT

C. Insert a new node before given node at the Singly 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. 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.

TT 21
 ➢ Algorithm to Insert a new node before given node at the Singly linked list
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR -> DATA! =NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 10: PREPTR -> NEXT = NEW_NODE
Step 11: SET NEW_NODE -> NEXT = PTR
Step 12: EXIT

D. Insert a new node before given node at the Singly 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. Then 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. 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
new node is inserted after the desired node.

TT 22
 ➢ Algorithm to Insert a new node after given node at the Singly linked list
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PREPTR -> DATA! =NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 10: PREPTR -> NEXT = NEW_NODE
Step 11: SET NEW_NODE -> NEXT = PTR
Step 12: EXIT

➢ Deleting a node from the Singly linked list

A. Deletion of first node from the Singly Linked List
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.
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.

TT 23
 ➢ Algorithm to Delete a First node from the Singly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START -> NEXT
Step 4: FREE PTR
Step 5: EXIT

B. Deletion of last node from the Singly 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 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.

TT 24
 ➢ Algorithm to Delete a Last node from the Singly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 and 5
While PTR -> NEXT! = NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 6: SET PREPTR -> NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT

C. Deletion of node After given node in the Singly 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 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 back to the free pool.

➢ Algorithm to Delete a node after a given node from the Singly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 10
[END OF IF]
Step 2: SET PTR = START

TT 25
 Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6
while PREPTR -> DATA! =NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR -> NEXT = PTR -> NEXT
Step 9: FREE TEMP
Step 10: EXIT

➢ CIRCULAR LINKED LIST

Circular linked list is a linked list where all nodes are connected to form a circle. There is no
NULL at the end. A circular linked list can be a singly circular linked list or doubly circular
linked list. Any node can be a starting point. We can traverse the whole list by starting from
any point. We just need to stop when the first visited node is visited again.

Fig.: Overview of Circular Linked List

➢ Operations on Circular Linked List

1. Insertion of new node at the Circular Linked List
A. Insertion of new node at the beginning of the Circular Linked List
B. Insertion of new node at the end of the Circular Linked List
2. Deletion of node from the Circular Linked List
A. Deletion of node from the beginning of the Circular Linked List
B. Deletion of node from the end of the Circular Linked List

➢ Insertion of new node at the Circular Linked List

A. Insertion of new node at the beginning of the 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. Otherwise, if free memory cell is

TT 26
 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.

➢ Algorithm to Insert new node at the beginning of the Circular Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 11
[END OF IF]
Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR -> NEXT! =START
Step 7: PTR = PTR -> NEXT
[END OF LOOP]
Step 8: SET NEW_NODE -> NEXT = START
Step 9: SET PTR -> NEXT= NEW_NODE
Step 10: SET START = NEW_NODE
Step 11: EXIT

B. Insertion of new node at the end of the 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

TT 27
 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.

➢ Algorithm to Insert new node at the end of the Circular Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 10
[END OF IF]
Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT = START
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR -> NEXT! = START
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: EXIT
➢ Deletion of node from the Circular Linked List
A. Deletion of node from the beginning of the Circular Linked List
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.

TT 28
 ➢ Algorithm to Delete node from beginning of the Circular Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR NEXT! =START
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: SET PTR -> NEXT = START -> NEXT
Step 6: FREE START
Step 7: SET START = PTR -> NEXT
Step 8: EXIT

B. Deletion of node from the end of the 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.

➢ Algorithm to Delete node from end of the Circular Linked List

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!=START
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR -> NEXT

TT 29
 [END OF LOOP]
Step 6: SET PREPTR -> NEXT = START
Step 7: FREE PTR
Step 8: EXIT

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

Fig.: Overview of Doubly Linked List

➢ Operations on Circular Linked List

1. Insertion of new node at the Doubly Linked List
A. Insertion of new node at the beginning of the Doubly Linked List
B. Insertion of new node at the end of the Doubly Linked List
C. Insertion of new node before the given value of the Doubly Linked List
D. Insertion of new node after the given value of the Doubly Linked List
2. Deletion of node from the Doubly Linked List
A. Deletion of node from the beginning of the Doubly Linked List
B. Deletion of node from the end of the Doubly Linked List
C. Deletion of node from before given value of the Doubly Linked List
D. Deletion of node from after given value of the Doubly Linked List

➢ Insertion of new node at the beginning of the 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

TT 30
 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.

➢ Algorithm to insertion of new node at the beginning of the Doubly Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 9
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> PREV = NULL
Step 6: SET NEW_NODE -> NEXT = START
Step 7: SET START -> PREV = NEW_NODE
Step 8: SET START = NEW_NODE
Step 9: EXIT

➢ Insertion of new node at the end of the 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.

TT 31
 ➢ Algorithm to insertion of new node at the end of the Doubly Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 11
[END OF IF]
Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET NEW_NODE -> NEXT= NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR -> NEXT!=NULL
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET PTR -> NEXT = NEW_NODE
Step 10: SET NEW_NODE -> PREV = PTR
Step 11: EXIT

➢ Insertion of new node before the given value of the Doubly 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. 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.

➢ Algorithm to insert new node before the given value at Doubly Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 13
[END OF IF]
Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL

TT 32
 Step 5: SET PTR = START
Step 6: Repeat Step 7 and 8 while PTR -> DATA != NUM
Step 7: SET PREPTR = PTR
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 9: SET NEW_NODE -> NEXT = PREPTR - > NEXT
Step 10: SET NEW_NODE -> PREV = PTR -> PREV
Step 11: SET PREPTR -> NEXT = NEW_NODE
Step 12: SET PTR -> PREV = NEW_NODE
Step 13: EXIT

➢ Insertion of new node after the given value of the 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 new node is inserted after the desired node.

➢ Algorithm for Insertion of new node after the given value of the Doubly Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 13
[END OF IF]
Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL -> NEXT
Step 4: SET NEW_NODE -> DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 and 8 while PREPTR -> DATA != NUM
Step 7: SET PREPTR = PTR
Step 8: SET PTR = PTR -> NEXT
[END OF LOOP]

TT 33
 Step 9: SET NEW_NODE -> NEXT = PREPTR - > NEXT
Step 10: SET NEW_NODE -> PREV = PTR -> PREV
Step 11: SET PREPTR -> NEXT = NEW_NODE
Step 12: SET PTR -> PREV = NEW_NODE
Step 13: EXIT

➢ Deletion of node from the beginning of the Doubly Linked 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.

➢ Algorithm for Deletion of node from the beginning of the Doubly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 6 [END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START -> NEXT
Step 4: SET START -> PREV = NULL
Step 5: FREE PTR
Step 6: EXIT

➢ Deletion of node from the end of the 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 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.

TT 34
 ➢ Algorithm for Deletion of node from the end of the Doubly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 7
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 and 5 while PTR -> NEXT !=NULL
Step 4: PREPTR = PTR
Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 6: SET PREPTR -> NEXT = NULL
Step 7: Free PTR
Step 8: Exit

➢ Deletion of node from before given value of the 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.

TT 35
 ➢ Algorithm for Deletion of node from before given value of the Doubly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 and 5 while PTR -> DATA != VAL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 6: SET PTR -> PREV = PREPTR -> PREV
Step 7: SET PREPTR -> PREV -> NEXT = PTR
Step 8: Free PREPTR
Step 9: EXIT

➢ Deletion of node from after given value of the 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. The memory
of the node preceding PTR is freed and returned to the free pool.

➢ Algorithm for Deletion of node from After given value of the Doubly Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 9
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 and 5 while PREPTR -> DATA != VAL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR -> NEXT

TT 36
 [END OF LOOP]
Step 6: SET PREPTR -> NEXT = PTR -> NEXT
Step 7: SET PTR -> NEXT -> PREV = PREPTR
Step 8: Free PTR
Step 9: EXIT

➢ Reversing of a Linked List

In the reversing of singly linked list the first node become the last node and last node become
the first node.

Fig.: Overview of Reversing of Linked List

➢ Algorithm for Reversing of a Linked List
Step 1: INIT TEMP = NULL, PREV= NULL
Step 2: IF START = NULL
WRITE UNDERFLOW
GO TO STEP 10
END OF IF
Step 3: SET PTR = START
Step 4: Repeat 5 to 8 While PTR ! = NULL
Step 5: TEMP = PTR -> NEXT
Step 6: PTR -> NEXT = PREV
Step 7: PREV = PTR
Step 8: PTR = TEMP
END OF LOOP
Step 9: SET START = PREV
Step 9: EXIT

➢ Updating Value of a Linked List

Updating a data element of any node at singly linked list. User need to enter existing value
and new value to update.

TT 37
 ➢ Algorithm to Update Value at a Linked List

Step 1: IF START = NULL

WRITE UNDERFLOW
GO TO STEP 9
END OF IF
Step 2: SET PTR = START
Step 3: Repeat 4 While PTR -> DATA! = OLD_VALUE
Step 4: PTR = PTR -> NEXT
End of Loop
Step 5: PTR -> DATA = NEW_VALUE
Step 9: EXIT

TT 38