Syllabus

Unit 1: Introduction: Basic Terminology, Elementary Data Organization, Built in

Data Types in C. Algorithm, Efficiency of an Algorithm, Time and Space
Complexity, Asymptotic notations: Big Oh, Big Theta and Big Omega, Time-Space
trade-off. Abstract Data Types (ADT)
Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays:
Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-
D,2-D,3-D and n-D Array Application of arrays, Sparse Matrices and their
representations.
Linked lists: Array Implementation and Pointer Implementation of Singly Linked
Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List.
Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction &
Multiplications of Single variable & Two variables Polynomial.

Unit 2: Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array
and Linked Implementation of Stack in C, Application of stack: Prefix and Postfix
Expressions, Evaluation of postfix expression, Iteration and Recursion- Principles of
recursion, Tail recursion, Removal of recursion Problem solving using iteration and
recursion with examples such as binary search, Fibonacci numbers, and Hanoi towers.
Tradeoffs between iteration and recursion.
Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues,
Array and linked implementation of queues in C, Dequeue and Priority Queue.

Unit 3: Searching: Concept of Searching, Sequential search, Index Sequential Search,

Binary Search. Concept of Hashing & Collision resolution Techniques used in
Hashing. Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort,
Heap Sort and Radix Sort.

Unit 4: Trees: Basic terminology used with Tree, Binary Trees, Binary Tree
Representation: Array Representation and Pointer(Linked List) Representation,
Binary Search Tree, Strictly Binary Tree ,Complete Binary Tree . A Extended Binary
Trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Constructing
Binary Tree from given Tree Traversal, Operation of Insertion , Deletion, Searching
& Modification of data in Binary Search. Threaded Binary trees, Traversing
Threaded Binary trees. Huffman coding using Binary Tree. Concept & Basic
Operations for AVL Tree , B Tree & Binary Heaps

Unit 5: Graphs: Terminology used with Graph, Data Structure for Graph
Representations: Adjacency Matrices, Adjacency List, Adjacency. Graph Traversal:
Depth First Search and Breadth First Search, Connected Component, Spanning Trees,
Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transitive Closure and
Shortest Path algorithm:Warshal Algorithm and Dijikstra Algorithm.

Dr. Nisha Pal

 Unit-1
Introduction to Data Structures
Since the inception of computers, people have been using the term "data" to describe
computer information that is communicated or stored. However, it's important to note that
order types also encompass data. Data can manifest in various forms such as printed numbers
or sentences on paper, bits and bytes stored in electronic devices' memory, or knowledge
retained mentally. As the world progressed into modernity, this data became integral to daily
life, with different methods emerging for its storage. Data refers to a collection of numbers,
facts, or values, organized in a particular format corresponding to a specific set of item
values. Sub-items, derived from data items, represent a group of items beyond the primary
form of the item. For instance, an employee's name can be broken down into its first, middle,
and last letters, constituting separate data elements, while their assigned ID typically remains
a single item.

Figure 1.1 Representations of Data Items

Items like ID, Age, Gender, First, Middle; Last, Street, Locality, etc. are basic data items in
the aforementioned sample. The Name and the Address, on the other hand, are group data
items.

What is Data Structure?

Within computer science, there exists a specialized domain known as data structures. Delving
into the realm of data structures equips us with the comprehension of how data is organized
and managed, facilitating the optimization of efficiency in any process or program.
Essentially, a data structure is a tailored approach to storing and arranging data within a
computer's memory, ensuring swift retrieval and efficient utilization when required. It serves
as a logical or mathematical model representing a specific form of data organization, offering
diverse methods for managing data.
OR

The data structure indicates how data is organized in memory. Data structures are ways to
organize, store, retrieve, and manage data efficiently. It helps in structuring data so that it can
be accessed and modified effectively. In programming, choosing the right data structure can
make a huge difference in the performance and scalability of an application.

A specific data model's scope is determined by two things:

1. Adequate loading of data into the structure is essential to establish a distinct correlation
between the data and its corresponding physical entity.
2. The structure's design should be straightforward, allowing for easy adaptation to facilitate
effective data analysis when required.
3. Data structures encompass various components such as arrays, linked lists, stacks, queues,
trees, and more. Virtually every realm within computer science, including compiler design,
operating systems, graphics, artificial intelligence, and numerous others, extensively utilizes
data structures.
A fundamental element in numerous computer science algorithms is the data structure,
empowering programmers to proficiently handle data. Given that software's core objective
revolves around swiftly storing and retrieving user data, enhancing program or software
performance becomes paramount.

Need for Data Structures

As applications become increasingly complex and data volume grows daily, challenges such
as data searching, processing speed, and managing multiple requests may arise. Data
structures offer various strategies for effectively managing, organizing, and storing data.
They enable swift navigation through data objects while providing benefits such as
abstraction, reuse, and efficiency.
Why should we learn Data Structures?
1. Data structures and algorithms stand as fundamental pillars within computer science.
2. Algorithms facilitate the meaningful analysis of data, whereas data structures facilitate its
organization and storage.
3. Acquiring proficiency in algorithms and data structures enhances our programming
capabilities.
4. This proficiency enables the creation of code that is both reliable and efficient.
5. Moreover, it equips us to address challenges more swiftly and effectively.
Understanding the Objectives of Data Structures:

Data structures accomplish two related goals:

1. Correctness: Data structures are engineered to operate flawlessly across various input
scenarios, tailored to the specific challenges they aim to resolve. Essentially, the primary
objective of a data structure is to ensure correctness, which is contingent upon the issues it's
intended to tackle.
2. Efficiency: In addition to correctness, data structures must demonstrate efficiency by
swiftly managing data while minimizing resource consumption, such as memory usage. The
real-time efficiency of a data structure significantly influences the outcome of a process,
determining its success or failure.
Some Key Features of Data Structures:
Some of the Key Features of Data Structures Include:
o Efficient Data Storage: It enables efficient management and retrieval of data,
making operations such as searching, inserting, and deleting faster.

o Memory Utilization: It optimizes memory usage by structuring data to minimize

space complexity.

o Data Manipulation: Structures such as stacks, queues, and trees facilitate specific
operations like push/pop, enqueue/dequeue, and hierarchical traversal.

o Data Organization: Organizing data logically enables better data processing and
operations.

o Ease of Access: Data structures such as arrays and linked lists offer quick access to
elements, depending on their design.
 o Flexibility: Various structures are appropriate for different scenarios, providing
flexibility in programming.

o Optimization: Selecting the appropriate data structure can greatly enhance the speed
and efficiency of an algorithm.

o Dynamic Size: Some data structures, such as linked lists and dynamic arrays, can
dynamically adjust their size to accommodate varying amounts of data.

Some Applications of Data Structures:

The following are some applications of Data Structures:

1. Data structures aid in sorting out the information stored in a computer's memory.
2. Data structures aid in the representation of information in databases.
3. Data structures enable the use of algorithms to data search (For example, search
engine).
4. We can use data structures to create data manipulation techniques (For example, word
processors).
5. Data structures can be used to create algorithms for data analysis (For example, data
miners).
6. Data structures support the generation of data by algorithms (For example, a random
number generator).
7. Data structures can also support data compression and decompression methods (For
example, a zip utility).
8. Data structures can also be used to develop algorithms for encrypting and decrypting
data (For example, a security system).
9. We can create software that manages files and directories with the aid of data
structures (For example, a file manager).
10. Data structures can also be used to create software that renders graphics. (A web
browser or 3D rendering programme, for instance.)

Basic Terminologies related to Data Structures

Any software or programme is constructed from data structures. It can be very difficult for a
programmer to choose the right data structure for a programme.

When discussing data structures, the following basic terms are frequently used:
 1. Data: Data can be viewed as a set of values or as a basic value. Examples of
employee-related data include the name and ID of the employee.
2. Data Items: Data Items are single units of value.
3. Group Items: Group Items are data items that have lower-level data items. An
employee's name, for instance, could include their first, middle, and last names.
4. Elementary Items: Elementary Items are data items that cannot be subdivided into
other data items. Using an employee's ID as an illustration.
5. Entity and Attribute: An entity represents a class of specific items. It is made up of
several Qualities. Each attribute represents a particular attribute of that entity. For
instance.
6. Field: Field refers to a single fundamental piece of data that represents an entity's
attribute.
7. Record: A Record is a grouping of various data pieces. The name, ID, address, and
job title of the employee entity, for instance, can be grouped to create the record for
the employee.
8. File: A File is a grouping of distinct Records of the same entity type. For instance, if
there are 100 employees, the corresponding file will have 25 records with information
about each person.

Example:

Attributes ID Name Gender Job Title

Software
Values 1234 Ram Male
Developer

An Entity Set is made up of entities with related qualities. A range of values, or the set of all
potential values that could be assigned to a given property, exists for each attribute of an
entity set.

When referring to data that has certain characteristics of meaningful or processed data, the
term "information" is occasionally used.

Classification of Data Structures:

A data structure offers an organized assembly of variables interconnected in different ways,

forming the cornerstone of a programming tool that delineates relationships between data
items, facilitating efficient data processing by programmers.

Data structures can be categorized into two groups:

1. Primitive Data Structures
2. Non-Primitive Data Structures
The diagram below illustrates the different categories of data structures.

Figure 1.2 Classifications of Data Structures

1. Primitive Data Structures

 Primitive Data Structures encompass the fundamental elements incorporated into

programs, consisting of characters and numbers.
 These data structures can be directly manipulated or accessed by machine-level
instructions.
 Simple data types like Integer, Float, Character, and Boolean are examples of Primitive
Data Structures.
 As they contain characters that cannot be further broken down, these data types are often
referred to as simple data types.
1. Non-Primitive Data Structures
 Data structures stemming from primitive data structures are termed non-primitive data
structures.
 Unlike primitive data structures, machine-level instructions cannot directly manipulate or
access these data structures.
 The primary objective of these data structures is to establish a collection of data
components that can be either homogeneous (of the same kind) or heterogeneous (of
different data types).
 These data structures can be classified into two sub-categories based on the arrangement
and organization of the data:
  Linear Data Structures
 Non-Linear Data Structures
Linear Data Structures
A linear data structure is characterized by direct relationships between its data objects.
Typically, the data is sorted except for the first and last items, where each item has a
predecessor and a successor. However, due to different configurations in memory, this
sequential order does not always work.

The Linear Data Structures are further divided into two categories based on memory
allocation:

1. Static Data Structures: Static Data Structures are highly defined data
structures. The sizes of these data structures cannot be changed by the
user after they are created because memory is allocated to them at
compile time; however, the content can be updated. An array is a good
example of a static data structure because it has a fixed size and allows
later data modifications.
2. Dynamic Data Structures: Dynamic Data Structures are variable sized data
structures. The memory of these data structures is allocated at runtime,
and their size changes as the code is executed. In addition, during code
execution, the user has the ability to change the size and data blocks
stored in these data structures. Some examples of dynamic data
structures include Linked Lists, Stacks, and Queues.

Types of Linear Data Structures:

The list of linear data structures that we typically utilise is as follows:

1. Arrays

An array, the basic data structure, combines multiple pieces of data of the same type into a
unified variable. Instead of dispersing these values across variables, we aggregate them into
one. It is important to note that this does not mean combining all the same values in every
context into a single framework. However, there are generally situations where related
variables sharing the same data are inherently apt to be sorted into a hierarchy.

An array is a collection of objects where each element occupies a specific position. All
elements of an array have the same variable name but different index numbers, also known as
subscripts. With these indices, we can retrieve any data element from the array. A key
characteristic of arrays is that the data is stored in adjacent memory, allowing users to use
their indices through the elements of the array.
 Figure 1.3 An Array

Arrays can be classified into different types:

a. One-Dimensional Array: A one-dimensional array consists of only one sequence of data

elements. Archives are mostly kept locally.
b. Two-Dimensional Array: Two-dimensional array of data elements with multiple rows and
columns. This is also known as accounting.
c. Multidimensional Array: A multidimensional array can be defined as an array
of array. Multidimensional arrays can have as many indices as necessary
and not just two indices or two dimensions.

Some Applications of Array:

a. Data segments of the same data set can be stored.

b. For other data structures, the array acts as an attached storage device.
c. The array is also useful for storing the informational components of a
binary tree with a predetermined number of elements.
d. Arrays can also be used to store matrices.

2. Linked Lists

Another example of a dynamic linear data structure for holding a collection of data elements
is a linked list. The nodes in this structure represent data objects, which are connected to each
other through links or pointers. Each node has two locations: a text location, the building of
the data, and a pointer location, which contains the addresses of the next nodes in the list. The
last node in a linked list contains a null pointer, indicating its end. Unlike arrays, linked lists
can be resized dynamically, to suit the needs of the user.
 Figure1.4. A Linked List

Linked Lists can be classified into different types:

a. Singly Linked List: The most common type of linked list is the singly linked list,
where each node contains data along with a pointer field pointing to the next node.
b. Doubly Linked List: A doubly linked list comprises an information field and two
pointer fields. The data resides in the information field, while one pointer field holds a
reference to the next node, and the other pointer field contains the location of the
previous node. This bidirectional linkage allows traversal in both forward and
backward directions.
c. Circular Linked List: The Singly Linked List and the Circular Linked List share
similarities. However, the distinguishing feature of the Circular Linked List is that its
last node points back to the first node, forming a circular loop.

Some Applications of Linked Lists

a. Linked Lists facilitate the implementation of fixed-size stacks, queues, binary trees, and
graphs.
b. Dynamic memory management feature of the operating system can also be utilized.
c. Linked Lists offer a method to implement polynomials for mathematical operations.
d. Circular linked lists are suitable for constructing round-robin task execution in operating
systems or application operations.
e. Circular Linked Lists find application in Slide Shows, especially when users need to return
to the first slide after viewing the last one.
f. Browser's forward and backward navigation buttons are implemented using doubly linked
lists, enabling users to move between opened pages of a website.
3. Stacks

Stacks, a form of linear data structure, adhere to the Last In, First Out (LIFO) principle,
allowing operations like insertion and deletion from the top of the stack. Both contiguous
memory, like an Array, and non-contiguous memory, such as a Linked List, can serve as
implementations for stacks. Stacks manifest in everyday scenarios such as piles of books, a
deck of cards, money, and various other contexts.

Figure 1.5 A Real-life Example of Stack

The insertion and removal of fresh books from the top of the stack are examples of activities
that are carried out from only one end of a stack, as seen in the above image. It suggests that
just the top of the stack can be used for insertion and deletion in the stack. At any given time,
we are only able to access the Stack's tops.

The primary operations in the Stack are as follows

Push: Push operation refers to the action of adding a new element to the stack.

Pop: Pop Operation refers to an operation that removes or deletes elements from the
stack.
 Figure 1.6 A Stack

Some Applications of Stacks:

a. Stack serves as temporary storage for recursive operations.

b. Function calls, nested actions, and postponed functions utilize the stack as auxiliary
storage.
c. Stacks are employed to manage function calls.
d. Some programming languages utilize stacks for evaluating arithmetic expressions.
e. Stacks are valuable for converting infix expressions to postfix expressions.
f. Stacks facilitate syntax validation of expressions in programming environments.
g. Stacks can be utilized for matching parentheses.
h. Reversing a string can be achieved using stacks.
i. Stacks are instrumental in solving backtracking-based puzzles.
j. Graph and tree traversal via depth-first search is facilitated by stacks.
k. Stacks are employed in various operations of operating systems.
l. Stacks are utilized for UNDO and REDO functions in editing tasks.

4. Queues

Like a stack, a queue is a linear data structure but with specific constraints on element
insertion and deletion. Elements are added to one end of the queue and removed from the
opposite end, adhering to the FIFO (First In, First Out) principle. Queues can be implemented
using arrays, linked lists, or even stacks. Examples of queues in daily life include lines at car
washes, escalators, and ticket counters.
 Figure 1.7 A Real-life Example of Queue

A real-life example, such as a movie ticket counter, illustrates the queue system where the
first person to arrive is the first to be served, ensuring fairness. Eventually, the last-arriving
customer will also receive service. The queue operates bidirectional, accommodating various
actions. Similarly, a food court line adds customers from the back and serves them from the
front once they've received their requested services.

The Queue's principal functions are as follows:

a. Enqueue: Enqueue refers to the process of adding certain data elements to a queue.
The rear pointer is always used to assist in inserting the element.
b. Dequeue: Dequeue is the phrase for deleting or removing data pieces from the Queue.
The front pointer is always used to assist in deleting the element.
 Figure 1.8 A Queue

Some Applications of Queues:

a. Queues are often used in a special way of searching through graphs called breadth-first
search.
b. In computer systems, queues are used in various tasks like managing jobs in the operating
system. For example, when you press keys on your keyboard or print documents, those
actions are managed using queues.
c. Queues are important in managing different tasks in a computer, such as deciding which
job the CPU should do next or managing data storage.
d. When you're downloading files using a web browser, priority queues help in deciding
which file gets downloaded first.
e. Queues are helpful in transferring data between devices like printers, keyboards, and the
main part of the computer.
f. Dealing with sudden tasks from user applications, like interruptions, is also something
queues help with in a computer system.
Non-Linear Data Structures
In non-linear data structures, the data pieces aren't arranged in a straight line. So, you can't
add or remove data in a straightforward order like you do with linear structures. Instead,
the data are organized in a hierarchical way, where many pieces of data are connected to
each other in a sort of tree-like structure.
Types of Non-Linear Data Structures

The list of non-linear data structures that we typically employ is as follows:

1. Trees

Each node in a tree holds a value as well as a list of pointers to other nodes, making trees
non-linear data structures and hierarchies (the "children").

A specialised approach to gathering and organising data in the computer for better use is the
Tree data structure. It has an edge-connected centre node, structural nodes, and sub-nodes.
We might also state that the connected roots, branches, and leaves make up the tree data
structure.

Figure 1.9 Tree

Trees can be classified into different types

a. Binary Tree: A binary tree is a tree data structure in which each parent node can have
a maximum of two children.
b. Binary Search Tree: We can easily maintain a sorted list of numbers in a Binary
Search Tree, a Tree data structure.
c. AVL Tree: A self-balancing Binary Search Tree called an AVL Tree keeps additional
data at each node known as a Balancing Factor, which can have a value of -1, 0, or
+1.
d. B-Tree: The self-balancing Binary Search Tree variant known as a B-Tree allows
each node to include multiple keys and more than two children.
Some Applications of Trees

a. Hierarchical structures in computer systems, such as directories and file systems, are
implemented using trees.
b. Trees are employed to establish the navigational structure of websites.
c. Trees can be utilized to develop code similar to Huffman's code.
d. Trees find utility in gaming applications for decision-making processes.
e. Trees are instrumental in implementing priority queues for priority-based OS scheduling
functions.
f. Compilers of many computer languages utilize trees to parse expressions and statements.
g. Trees serve as a means of storing data keys for indexing in database management systems
(DBMS).
h. Spanning trees enable decision-routing in computer and communications networks.
i. Path-finding algorithms in video games, robotics, and artificial intelligence (AI)
applications incorporate trees.

2. Graphs

Another illustration of a non-linear data structure is a graph, which consists of a finite number
of nodes or vertices and the edges bridging them. The use of graphs in solving real-world
issues denotes the issue as a network, such as social networks, circuit networks, or telephone
networks. One user in a telephone network may be represented by one of the nodes, or
vertices, of a graph, while the relationship between them could be represented by one of the
edges.
The mathematical structure known as the Graph data structure, G, is made up of a collection
of vertices, or V, and a set of edges, or E, as shown below:
G = (V,E)

Figure 1.10 Graph

The graph shown above is made up of seven vertices (A, B, C, D, E, F, and G) and ten edges
(A, B), (A, C), (B, C), (B, D), (B, E), (C, D), (D, E), (D, F), and (E, F).
Depending upon the position of the vertices and edges, the Graphs can be classified into
different types:

a. Trivial Graph: A graph with only one vertex is referred to as a trivial graph.
b. Null Graph: A graph devoid of any edges is termed a null graph.
c. Simple Graph: A simple graph is characterized by its absence of multiple edges or self-
loops.
d. Multi Graph: A graph featuring multiple edges without any self-loops is classified as a
multi graph.
e. Pseudo Graph: A pseudo graph is distinguished by its abundance of edges and inclusion
of self-loops.
f. Non-Directed Graph: A graph lacking directed edges is designated as a non-directed
graph.
g. Directed Graph: A directed graph consists solely of directed connections linking its
vertices.
h. Connected Graph: A connected graph possesses at least one path connecting every pair
of vertices.
i. Disconnected Graph: A disconnected graph is one in which there is no path connecting at
least one pair of vertices.
j. Regular Graph: A graph where every vertex has an identical degree is termed a regular
graph.
k. Complete Graph: In a complete graph, every vertex is connected to every other vertex by
an edge.
l. Cycle Graph: A graph containing at least three vertices and edges that form a cycle is
known as a cycle graph.
m. Cyclic Graph: A graph is deemed cyclic if it contains at least one cycle.
n. Acyclic Graph: An acyclic graph is one that lacks any cycles.
o. Finite Graph: A graph with a finite number of vertices and edges is referred to as a finite
graph.
p. Infinite Graph: An infinite graph possesses an infinite number of vertices and edges.
q. Bipartite Graph: In a bipartite graph, vertices can be divided into two independent sets, A
and B, with edges only connecting vertices from set A to those in set B.
r. Planar Graph: A graph that can be drawn in a single plane without any crossing edges is
termed a planar graph.
s. Euler Graph: A graph is Eulerian if all its vertices have even degrees.
t. Hamiltonian Graph: A Hamiltonian graph is a connected graph that contains a
Hamiltonian circuit, traversing each vertex exactly once.
 Some Applications of Graphs:

a. Graphs are instrumental in representing routes and networks in transportation, travel, and
communication applications.
b. GPS paths are depicted using graph structures.
c. Graphs aid in visualizing relationships within social networks and other network-based
software.
d. Mapping applications utilize graphs for various functionalities.
e. Graphs play a crucial role in representing user preferences in e-commerce applications.
f. Utility networks utilize graphs to identify issues faced by local or municipal businesses.
g. Graphs are employed in managing resource availability and usage within organizations.
h. Graphs are utilized to create document link maps of websites, showcasing the
interconnectedness between pages through hyperlinks.
i. Graphs find application in neural networks and robotic movements.

Difference Between Linear and Non-linear data Structure:

Basic Operations of Data Structures:

In the following section, we will discuss the different types of operations that we can perform
to manipulate data in every data structure:

1. Traversal: When you're going through a bunch of data, you need to make sure you
look at each piece just once to handle it properly. For example, if you want to print
out the names of everyone in a department, you have to go through each name one by
one, making sure not to miss anyone.
2. Search: Another thing you can do with data structures is called "search." This means
finding one or more pieces of data that meet certain criteria. The data you're looking
for might be there or might not be. For example, you might use the search function to
find the names of employees who have worked for more than five years.
3. Insertion: Adding new data to a group that's already there is called "insertion." For
example, if a company hires a new employee, you use the insertion operation to put
that new employee's information into the company's records.
4. Deletion: When you want to take out a particular piece of data from a list, you use
something called "deletion." For example, if someone leaves a job, you'd use the
deletion method to take their name off the list of employees.
5. Sorting: Depending on what you're doing, sorting means putting things in order from
smallest to biggest or biggest to smallest. For example, if you want to find the best
performers, you might sort everyone's performance from highest to lowest and pick
the top three. Or, if you're making a list of employees, you might use sorting to put
their names in alphabetical order.
6. Merge: When you have two lists of things that are already sorted, you can put them
together into one big sorted list using something called a "merge" operation.

7. Selection: Selection refers to choosing a specific piece of information from a pool of

data. By defining conditions inside the loop, we can choose any specific data.
8. Update: We can update or change the data in the data structure by using the Update
operation. By putting some criteria inside the loop, like the Selection operation, we
may also update any specific data.
9. Splitting: By splitting data into several subparts, we can shorten the time it takes for
the entire process to finish.

Elementary Data Types:

A class of elementary data objects with a set of procedures for producing and manipulating
them are expressed as elementary data types. An elementary data object consists of a single
 data value. a simple data type, such as an integer, a real number, a character, a Boolean, a
pointer, etc.
The basic components of elementary data types are as follows −
 Attributes − When referring to qualities or groups of traits that set one data object apart
from another, we use the term attributes. A data object's name, associated address, and data
type are its three primary characteristics. The declaration in C below.
int a;
It indicates that the type of a data object with the name "a" is integer. The characteristics of a
data object may be kept in a set of memory cells known as a descriptor (or dope vector). A
descriptor is a variable's collection of attributes. Descriptors are only required at build time if
all of the characteristics are fixed. They are created by the compiler and utilised during
compilation, typically as a component of the symbol table.
 Values − It describes a collection of all potential values that a data object might have.
A data object's type determines the values that it is capable of assuming. Any time
during its existence, an elementary data object has a single value from the set of
values. For instance, the C declaration int a; indicates that the data object a can select
one integer value out of a range of integer values. Since the value contained in a data
item may change over its lifespan, it is explicitly represented during programme
execution.
o Operations − A mathematical function used to manipulate data items is
referred to as an operation. An operation consists of
o Domain − A list of all potential input arguments on which the operation is
defined is what is meant by this.
o Range − It describes a collection of every outcome that an operation could be
able to generate as an output.
o Action − The result produced for each particular combination of arguments is
represented by the action of the operation.
o Algorithm − It outlines how to assess the outcomes for every particular
combination of arguments. It is employed to ascertain how an operation will
go.
o Signature − The number, order, and data types of the arguments in the domain
of an operation, as well as the order and data type of the producing order, are
defined by the operator's signature.

Data Types in C
In C, each variable has a corresponding data type. Each data type has a unique set of
operations that can be done on it and varied memory requirements. The type of data that the
variable can store, such as integer, character, floating point, double, etc., is specified. A
collection of data with fixed values, meaning, and features is referred to as a data type.

The data types in C can be classified as follows:

Types Description

Primitive Data
Types Integer and floating data types are subcategories of arithmetic types.
 Types Description

The data type doesn't have a value or operator, and it doesn't give its
Void Types caller a result. Yet, primitive data types include void.

User Defined It is mostly used to give integral constants names, which facilitates
DataTypes reading and maintaining programmes.

Derived Data Types are the data types that are created by deriving
Derived types from primitive or built-in data types.

Different data types also have different ranges up to which they can store numbers. These
ranges may vary from compiler to compiler. Below is a list of ranges along with the
memory requirement and format specifies on the 32-bit GCC compiler.

Memory Format
Data Type (bytes) Range Specifier

short int 2 -32,768 to 32,767 %hd

unsigned short 2 0 to 65,535 %hu

 Memory Format
Data Type (bytes) Range Specifier

int

unsigned int 4 0 to 4,294,967,295 %u

-2,147,483,648 to
int 4 2,147,483,647 %d

-2,147,483,648 to
long int 4 2,147,483,647 %ld

unsigned long int 4 0 to 4,294,967,295 %lu

long long int 8 -(2^63) to (2^63)-1 %lld

unsigned long 0 to
long int 8 18,446,744,073,709,551,615 %llu

signed char 1 -128 to 127 %c

unsigned char 1 0 to 255 %c

float 4 %f
1.2E-38 to 3.4E+38

double 8 %lf
1.7E-308 to 1.7E+308

long double 16
3.4E-4932 to 1.1E+4932 %Lf
Integer Types:

The integer data type in C is used to store the whole numbers without decimal values.
Octal values, hexadecimal values, and decimal values can be stored in int data type in C.
We can determine the size of the int data type by using the size of operator in C. Unsigned
int data type in C is used to store the data values from zero to positive numbers but it
can’t store negative values like signed int. Unsigned int is larger in size than signed int and
it uses “%u” as a format specifier in C programming language. Below is the programming
implementation of the int data type in C.

 Range: -2,147,483,648 to 2,147,483,647

 Size: 2 bytes or 4 bytes
 Format Specifier: %d
Note: The size of an integer data type depends on the compiler; on 16-bit processors, the
result of int is displayed as 2 bytes. Moreover, it displays both 2 and 4 bytes on processors
that are 32-bit.
// C program to print Integer data types.
#include <stdio.h>

intmain()
{
// Integer value with positive data.
inta = 9;

// integer value with negative data.

intb = -9;

// U or u is Used for Unsigned int in C.

intc = 89U;

// L or l is used for long int in C.

longintd = 99998L;

printf("Integer value with positive data: %d\n", a);

printf("Integer value with negative data: %d\n", b);
printf("Integer value with an unsigned int data: %u\n", c);
printf("Integer value with an long int data: %ld", d);

return0;
}
Output
With positive data, an integer value of 9
With negative data, an integer value -9
Unsigned int value for an integer: 89
Long int value for an integer: 99998

Character Types:

 Only one character may be stored in a character data type variable. The character has a
storage size of 1. It is C's most fundamental data type. In practically all compilers, it
stores a single character and uses a single byte of memory.
 Range: (-128 to 127) or (0 to 255)
 Size: 1 byte
 Format Specifier: %c

// C program to print Integer data types.

#include <stdio.h>

int main()
{

chara = 'a';
charc;

printf("Value of a: %c\n", a);

a++;
printf("Value of a after increment is: %c\n", a);

// c is assigned ASCII values

// which corresponds to the
// character 'c'
// a-->97 b-->98 c-->99
// here c will be printed
c = 99;

printf("Value of c: %c", c);

return0;
}

Output:
A's value is: a

After increment, the value of an is: b

C's value is c.

Floating-Point Types:

The float data type is used to hold floating-point values in C programming. Decimal and
exponential numbers are stored in C using the float keyword. It is used to hold decimal
integers with single precision (numbers with floating point values).
Range: 1.2E-38 to 3.4E+38
Size: 4 bytes
Format Specifier: %f

C Program to demonstrate use

// of Floating types
#include <stdio.h>

intmain()
{

floata = 9.0f;
floatb = 2.5f;
// 2x10^-4
floatc = 2E-4f;
printf("%f\n",a);
printf("%f\n",b);
printf("%f",c);

return0;

Output:

9.000000
2.500000
0.000200

Double Types:

In C, double precision decimal numbers (numbers having floating point values) are
stored using the Double data type. It is used to define numerical values that store C
decimal values for numbers. The double data type is essentially a precision data type
 that can store 64 bits of floating point or decimal numbers. As double has greater
precision as float, it is more clear that it uses up twice as much memory as the floating-
point type. It can easily handle 16 to 17 numbers either before or after the decimal
point.
 Range: 1.7E-308 to 1.7E+308
 Size: 8 bytes
 Format Specifier: %lf

// C Program to demonstrate
// use of double data type
#include <stdio.h>

intmain()
{

doublea = 123123123.00;
doubleb = 12.293123;
doublec = 2312312312.123123;

printf("%lf\n", a);

printf("%lf\n", b);

printf("%lf", c);

return0;
}

Output:

123123123.000000
12.293123
2312312312.123123
Void Data types:

In C, the void data type is used to indicate the absence of a value. It does not give its caller
a result value. Both values and operations are absent. It is employed to stand in for nothing.
Function return types, function arguments, and pointers to void are all examples of how
void is utilised.
Syntax:
// function return type void

void exit(int check);

// Function without any parameter can accept void.

int print(void);

// memory allocation function which

// returns a pointer to void.
void *malloc( size_t size);

// C program to demonstrate
// use of void pointers
#include <stdio.h>

intmain()
{
intval = 30;
void*ptr = &val;
printf("%d", *(int*)ptr);
return0;
}

Output:

30
Using dynamic memory allocation in C malloc(), calloc(), free() and
realloc():
C has a set of predetermined programming rules because it is a structured language. One of
them involves altering an array's size. A group of items kept in consecutive memory
regions is known as an array.

As can be observed, the above-made array has a length (size) of 9. However, what if this
duration needs to be changed? (size). As an illustration, suppose that only five elements
need to be entered into this array. In this instance, the remaining 4 indices in this array are
essentially a memory leak. So, it is necessary to reduce the array's length (size) from 9 to 5.
In C, this process is known as dynamic memory allocation.
As a result, C Dynamic Memory Allocation can be characterised as a process that enables
the runtime modification of a data structure's size, such as an array.
Several functions are available in C to carry out these tasks. To help with dynamic memory
allocation in C programming, C provides 4 library functions that are defined under the
stdlib.h> header file. As follows:

1. malloc()
2. calloc()
3. free()
4. realloc()

malloc () method

In C, a single big block of memory with the requested size is dynamically allocated using
the "malloc" or "memory allocation" method. It returns a void pointer that can be cast into
any other pointer type. As it doesn't initialise memory during execution, each block has
been originally initialised with the default garbage value.

Syntax:
malloc ptr = (cast-type*) (byte-size)

For instance:

(int*) malloc(100 * sizeof(int));

This statement will allocate 400 bytes of RAM because an int is 4 bytes in size. Moreover,
the address of the first byte in the allocated memory is contained in the pointer ptr.

If space is insufficient, allocation fails and returns a NULL pointer.

calloc() method :

1. To dynamically allocate the requested number of memory blocks of the specified

type in C, use the "calloc" or "contiguous allocation" method. Malloc() is fairly similar
to it, but it differs in two ways, which are as follows:
2. It gives each block a default value of "0."
3. Compared to malloc, it has two parameters or arguments ().
Syntax:
Ptr is equal to (cast-type*)calloc(n, element-size), where n is the number of elements
and element-size is their total size.
For instance:
ptr = (float*) calloc(25, sizeof(float)); This command allocates contiguous memory
space for 25 elements, each having the size of a float.

If space is insufficient, allocation fails and returns a NULL pointer .

realloc() method :

“realloc” or “re-allocation” method in C is used to dynamically change the memory

allocation of a previously allocated memory. In other words, if the memory previously
allocated with the help of malloc or calloc is insufficient, realloc can be used
to dynamically re-allocate memory. re-allocation of memory maintains the already present
value and new blocks will be initialized with the default garbage value .

Syntax:
ptr = realloc(ptr, newSize);
where ptr is reallocated with new size 'newSize'.

If space is insufficient, allocation fails and returns a NULL pointer.

Difference Between malloc() and calloc()

Memory is dynamically allocated by the library methods malloc() and calloc(). Dynamic
refers to memory that is allocated from the heap section while the programme is running.
Initialization malloc() returns a reference to the block's beginning after allocating a memory
block of the specified size (in bytes). The memory that is allocated but not initialised by
malloc(). Without initialising the allocated memory first, attempting to read from it will
cause unclear behaviour, which typically results in trash values being read.
The memory is allocated by calloc(), which also initialises each byte to 0. The allocated
memory has already been initialised to 0 by calloc, therefore if you attempt to read its
value without initialising it, you will receive 0. ().

Parameters

The amount of bytes to allocate is the only argument taken by malloc().

Calloc(), in contrast to malloc(), accepts two arguments:

1) The quantity of blocks to be distributed.

2) The number of bytes each block is.

Back Value

A pointer to the block of memory is returned after a successful allocation using the
malloc() and calloc() functions; otherwise, NULL is returned, signifying a failure.
 Algorithm
What is an Algorithm?
"A collection of finite rules or instructions to be followed in calculations or other problem-
solving procedures" is what the word algorithm signifies. Alternatively, "A finite-step
process for solving a mathematical problem that frequently uses recursive operations."

As a result, an algorithm is a set of limited procedures used to solve a certain problem.

Depending on what you want to do, algorithms might range from simple to sophisticate .

By using the process of making a novel recipe as an example, it can be understood. When
following a new recipe, one must read the directions and carry out each step in the correct
order. The new meal is cooked to perfection as a result of this process. You employ
algorithms every time you use a phone, computer, laptop, or calculator. Similar to this,
algorithms assist programmers in carrying out tasks to produce desired results.
The developed algorithm is language-independent, meaning that it consists only of simple
instructions that can be used to build it in any language and still produce the desired results.
Characteristics of an Algorithm

As opposed to using the normal recipe's printed directions, one would not follow them.
In a similar vein, not all computer instructions written down are algorithms. Certain
instructions must meet the following requirements in order to qualify as an algorithm:

 Clear and Unambiguous: The algorithm must be unambiguous and clear. Each of its
steps must have a distinct meaning and be transparent from beginning to end.
 Well-Defined Inputs: When an algorithm requests inputs, such inputs must be specific.
It might or might not accept input.
 Well-Defined Outputs: The output that will be produced by the algorithm must be
specified in detail and be well-defined. It must produce at least one output.
 Finite-ness: The algorithm must be finite, or end after a finite amount of time.
 Feasible: For use with the available resources, the algorithm needs to be simple,
generic, and implementable. Modern technology or anything else cannot be used in it.
 Language Independent: In order to be implemented with the available resources, the
algorithm needs to be simple, general, and practicable. It cannot use any advanced
technology or anything else.
 Properties of Algorithm

• It must come to an end after a set period of time.

• At least one output must be produced.
• It should require no input at all.
• It should be deterministic, which implies that the result should match the input scenario
exactly.
• Each step of the algorithm must be efficient, i.e., each step must provide results.

Types of Algorithms
There are numerous varieties of algorithms. Many significant algorithms include:

1. Brute Force Algorithm: It is the simplest solution to the issue. When we see an issue,
the first method that comes to mind is a brute force algorithm.
2. Recursive Algorithm: Recursion is the foundation of a recursive algorithm. In this
instance, a problem is divided into multiple smaller components and repeatedly called by
the same function.
3. Backtracking Algorithm: In essence, the backtracking algorithm constructs the solution
by scouring all potential solutions. Using this approach, we continue to develop the answer
in accordance with the criteria. Every time a solution fails, we go back to the original
problem, build on the new one, and repeat the process until the problem is solved or all
potential solutions have been considered.
4. Searching Algorithm: The algorithms used for searching individual components or
groups of elements from a specific data structure are called searching algorithms.
Depending on how they go about things or whatever data structure the element needs to be
in, they can be of several forms.
5. Sorting Algorithm: Sorting is the process of organising a group of facts in a specific
way in accordance with the needs. Sorting algorithms are the ones that assist in carrying out
this duty. Data groupings are often sorted using sorting algorithms in an increasing or
decreasing order.
6. Hashing Algorithm: Similar to how a search algorithm operates, hashing algorithms do
the same. Yet, they have an index with a key ID. In hashing, a key is given to a particular
piece of data.
7. Divide and Conquer Algorithm: This algorithm divides an issue into smaller problems,
resolves each smaller problem in turn, then combines the results to provide the overall
answer. The procedure entails the following three steps:
 Divide
 Solve
 Combine
8. Greedy Algorithm: This kind of algorithm builds the solution piece by piece. The
immediate benefit of the following section serves as the foundation for the solution of that
section. The answer for the following section will be the one offering the greatest benefit.
9. Dynamic Programming Algorithm: In order to avoid repeatedly computing the same
portion of the problem, this algorithm makes use of the idea of using the previously
discovered answer. It separates the issue into more manageable overlapping subproblems
and resolves each one.
10. Randomized Algorithm: We employ a random integer in the randomised process so
that it provides quick benefit. The expected result is determined in part by the random
number.

Advantages of Algorithms:
 It is simple to understand.
 An algorithm is a step-by-step depiction of a solution to a given problem.
 Because the problem is divided into smaller bits or steps in an algorithm
 It is simpler for the programmer to turn it into a real programme.
Disadvantages of Algorithms:
 Writing an algorithm can be a time-consuming process. Since writing an algorithm
takes a long time, it is indeed time-consuming.
 Understanding complex logic with the help of algorithms isn't easy.
 Displaying looping and branching statements in an algorithm is challenging.

How to Design an Algorithm?

As a prerequisite, the following things are required in order to build an algorithm:

1. The problem that this algorithm is supposed to answer, or a clearly stated problem.
2. Before solving the problem, the constraints of the problem must be taken into account.
3. The information needed to address the issue.
4. The results that can be anticipated after the issue is resolved.
5. This problem can be solved within the limitations that have been established.
The algorithm is then created using the aforementioned inputs in such a way that it resolves
the issue.

Example: Think about the example that prints the result of adding three numbers.

 Step 1: Fulfilling the pre-requisites

As was previously said, the requirements for an algorithm must be met before it can be
written.
1. The problem that is to be solved by this algorithm: Print the result of adding
three digits.
2. The constraints of the problem that must be considered while solving the
problem: The numbers cannot contain any other characters besides digits.
3. The input to be taken to solve the problem: the three figures that must be added.
4. The output to be expected when the problem is solved: the single integer value
that represents the sum of the three values entered as input.
 The solution to this problem, in the given constraints: The three digits must be added
to arrive at the answer. The "+" operator, bit-wise operations, and other techniques can
all be used to do this.

 Step 2: Designing the algorithm

Let's create the algorithm now using the prerequisites listed above: Algorithm to add 3
numbers and print their sum:
1. START
 2. Define three integer variables with the names num1, num2, and num3.
3. Enter each of the three integers to be added as an input into the num1, num2, and
num3 variables.
4. Define an integer variable sum to hold the three integers' combined sum.
5. Sum up the three figures and enter the total in the variable sum.
6. Display the sum of the variable's values.
7. END

 Step 3: Testing the algorithm by implementing it.

In order to test the algorithm, let’s implement it in C language.

// C program to add three numbers
// with the help of above designed algorithm

#include <stdio.h>
int main()
{

// Variables to take the input of the 3 numbers

intnum1, num2, num3;

// Variable to store the resultant sum

intsum;

// Take the 3 numbers as input

printf("Enter the 1st number: ");
scanf("%d", &num1);
printf("%d\n", num1);

printf("Enter the 2nd number: ");

scanf("%d", &num2);
printf("%d\n", num2);

printf("Enter the 3rd number: ");

scanf("%d", &num3);
printf("%d\n", num3);

// Calculate the sum using + operator

// and store it in variable sum
sum = num1 + num2 + num3;

// Print the sum

printf("\nSum of the 3 numbers is: %d", sum);

return0;
}
Output
Enter the 1st number: 0
Enter the 2nd number: 0
 Enter the 3rd number: -1577141152

Sum of the 3 numbers is: -1577141152

One problem, many solutions: There may or may not be more than one solution to an
algorithm. This implies that there may be more than one approach to implement the
algorithm. For instance, there are numerous ways to calculate the sum in the issue to add
three integers above. +operator
 Bit-wise operators
 . . etc

How to express an Algorithm?

1. Natural Language :- Here, we provide an English translation of the algorithm. It
would be too challenging to understand the algorithm from it.
2. Flow Chart : In this instance, we graphically or visually represent the algorithm. This
is simpler to understand than natural language.
3. Pseudo Code :- Here, we give the algorithm as annotations and instructional text
written in plain English that closely resembles real code but lacks any programming
language's syntax, making it difficult for a computer to compile or comprehend. It is the
best method for describing algorithms since it is simple enough for anyone with a
working knowledge of programming to grasp.

Issues of Algorithms:

The following are the issues that come up while designing an algorithm:
o How to design algorithms: As we know, an algorithm is a step-by-step procedure,
so we must follow some steps to design an algorithm.
o How to analyse algorithm efficiency: Analysing algorithm efficiency is essential
for understanding its performance, especially as the input size grows.

Why Analysis of Algorithms is important ?

Algorithm analysis is an important part of computational complexity theory, which

provides theoretical estimation for the required resources of an algorithm to solve a specific
computational problem. Analysis of algorithms is the determination of the amount of time
and space resources required to execute it.

 To predict the behaviour of an algorithm for large inputs (Scalable Software).

 It is much more convenient to have simple measures for the efficiency of an
algorithm than to implement the algorithm and test the efficiency every time a
certain parameter in the underlying computer system changes.
 More importantly, by analysing different algorithms, we can compare them to
determine the best one for our purpose.

How to analyse an Algorithm?

For a standard algorithm to work, it must be effective. As a result, it's important to keep an
eye on an algorithm's performance. There could be two stages:
1. Priori Analysis: Latin's priori means "before." As a result, Priori analysis describes the
process of validating an algorithm before applying it. This is checked when an
algorithm is written as a series of theoretical steps. The effectiveness of an algorithm is
assessed on the presumption that all other factors, such as processor speed, remain
constant and have no bearing on the implementation. This is often done by the
algorithm's creator. Our investigation is unaffected by the type of hardware or compiler
language. Due to the complexity of the programme, it offers rudimentary solutions.

2. Posterior Analysis: In Latin, "posterior" means "after." Therefore, posterior analysis is

the process of evaluating a method after it has been used. In this, the method is
examined through use and execution in any programming language. This analysis helps
in getting a true and accurate analysis report on correctness (for every possible input,
whether it shows or returns the right output or not), space required, time used, etc. In
other words, it is reliant on the hardware and compiler's language.

What is Algorithm complexity and how to find it?

Based on how much space and time it uses, an algorithm is classified as complicated. As a
result, an algorithm's complexity is determined by how much time and space it will require
to store all the data and execute the algorithm to produce the desired result (input,
temporary data and output). Thus, these two elements determine how effective an
algorithm.

The two factors of Algorithm Complexity are:

 Time Factor: The To calculate the amount of time that has passed, the number of
important actions is counted, such as comparisons in the sorting process.
 Space Factor: The total amount of memory required for the algorithm to run is counted
to determine the quantity of space.

Therefore, the complexity of an algorithm can be divided into two types:

1. Space Complexity: The space complexity of an algorithm is the quantity of memory

required to store the variables and generate the result. This could be relevant for transient
actions, inputs, or outputs.

How to calculate Space Complexity?

The space complexity of an algorithm is calculated from the following two factors:

Fixed Part: This is the area that the algorithm without a doubt requires. The size of the
programme, the output variables, and the input variables, for example.
Variable Part: Here is the area where the algorithm's results could differ. For instance,
recursion stack space, temporary variables, and dynamic memory allocation.
As a result, any algorithm's space complexity S(P) S(P) = C + SP(I), where C is the
algorithm's constant component and S(I) is its variable component that depends on the
instance characteristic I

Example: Consider the below algorithm for Linear Search

Step 1: Start
Get the n elements of the array from step 2 and the desired number from step 2's x.
Step 3: One by one, compare each element of arr[] with x, starting with the one that is
furthest to the left.
Show True in step 4 if x matches an element.
If x doesn't match any of the items, step 5: Print False.
Step 6: Complete the types of variables and constants.
In this scenario, there are two variables: x and arr, where x denotes the fixed portion of the
n items and arr denotes the variable portion. Thus, S(P) = 1 plus n. Hence, n establishes
how complex the space is (number of elements). Now, the provided variables and constant
types' data types will be multiplied in the available space.

Time Complexity: The time complexity of an algorithm is the amount of time required
for it to run and deliver a result. This might apply to normal operations, conditional if-else
statements, loop statements, etc.

How to calculate Time Complexity?

To determine an algorithm's temporal complexity, the next two factors are also determined:

Constant time part: Any instruction that is only ever performed once is included in
this section. A few examples are input, output, if-else, switches, arithmetic operations, etc.
Variable Time Part: This section contains all instructions that are executed n times or
more. using instances like loops, recursion, etc.
• As a result, the time complexity of any algorithm P can be calculated using the formula
T(P) = C + TP(I), where C denotes the method's constant time component and TP(I) is the
algorithm's variable time component that is dependent on the instance characteristic I.

Example: The linear search algorithm's temporal complexity is calculated using the
formula below:
Initially, Constant Time
Second Variable Time in Step 2 (Taking n inputs)
Third step: -Variable time (Till the element's index or the array's length (n) are found)
The final step is constant time.
Constant time is the fifth step.
Constant time is step six. This means that T(P) = 5 + n, or T (n)

Worst, Average and Best Case Analysis of Algorithms

1. Worst Case Analysis (Mostly used)

 In the worst-case analysis, we calculate the upper bound on the running time of an
algorithm. We must know the case that causes a maximum number of operations to
be executed.
 For Linear Search, the worst case happens when the element to be searched (x) is
not present in the array. When x is not present, the search() function compares it
with all the elements of arr[] one by one.
 This is the most commonly used analysis of algorithms (We will be discussing
below why). Most of the time we consider the case that causes maximum
operations.

2. Best Case Analysis (Very Rarely used)

  In the best-case analysis, we calculate the lower bound on the running time of an
algorithm. We must know the case that causes a minimum number of operations to
be executed.
 For linear search, the best case occurs when x is present at the first location. The
number of operations in the best case is constant (not dependent on n). So the order
of growth of time taken in terms of input size is constant.

3. Average Case Analysis (Rarely used)

 In average case analysis, we take all possible inputs and calculate the computing
time for all of the inputs. Sum all the calculated values and divide the sum by the
total number of inputs.
 We must know (or predict) the distribution of cases. For the linear search problem,
let us assume that all cases are uniformly distributed (including the case of x not
being present in the array). So we sum all the cases and divide the sum by (n+1). We
take (n+1) to consider the case when the element is not present.

Why is Worst Case Analysis Mostly Used?

Average Case: The average case analysis is not easy to do in most practical cases and it
is rarely done. In the average case analysis, we need to consider every input, its
frequency and time taken by it which may not be possible in many scenarios

Best Case: The Best Case analysis is considered bogus. Guaranteeing a lower bound on
an algorithm doesn't provide any information as in the worst case, an algorithm may
take years to run.

Worst Case: This is easier than average case and gives an upper bound which is useful
information to analyze software products.

Asymptotic Notation
The main idea of asymptotic analysis is to have a measure of the efficiency of algorithms that
don't depend on machine-specific constants and don't require algorithms to be implemented
and time taken by programs to be compared. Asymptotic notations are mathematical tools to
represent the time complexity of algorithms for asymptotic analysis.

Asymptotic Notations:

 Asymptotic Notations are mathematical tools used to analyze the performance of

algorithms by understanding how their efficiency changes as the input size grows.

 These notations provide a concise way to express the behavior of an algorithm's time
or space complexity as the input size approaches infinity.

 Rather than comparing algorithms directly, asymptotic analysis focuses on

understanding the relative growth rates of algorithms' complexities.

 It enables comparisons of algorithms' efficiency by abstracting away machine-specific

constants and implementation details, focusing instead on fundamental trends.
  Asymptotic analysis allows for the comparison of algorithms' space and time
complexities by examining their performance characteristics as the input size varies.

 By using asymptotic notations, such as Big O, Big Omega, and Big Theta, we can
categorize algorithms based on their worst-case, best-case, or average-case time or
space complexities, providing valuable insights into their efficiency.

There are mainly three asymptotic notations:

1. Big-O Notation (O-notation)

2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)

1. Theta Notation (Θ-Notation):

The function from above and below is enclosed in theta notation. It is used to examine the
average-case complexity of an algorithm because it represents the upper and lower bounds
of the running time of an algorithm.

Let the function from the set of natural numbers to itself be represented by g and f. If there
are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) f(n) c2* g(n) for all n
n0, then the function f is said to be (g).

Theta notation

Mathematical Representation of Theta notation:

The following expression can be translated as follows: for large values of n (n n0), f(n)
always has a value between c1 * g(n) and c2 * g(n), if f(n) is theta of g(n). For n values
bigger than n0, f(n) must also not be negative according to the definition of theta.
Eliminating low-order terms and ignoring leading constants is a straightforward method for
converting an expression to its Theta notation. For instance, Consider the phrase 3n3 + 6n2
+ 6000 = (n3); eliminating the lower order components is always acceptable because,
regardless of the constants used, there will always be a number(n) after which (n3) has
greater values than (n2). We write g(n) is the following collection of functions for a given
function.

2. Big-O Notation (O-notation):

Big-O notation is used to express an algorithm's maximum allowable running time. As a
result, it provides an algorithm's worst-case complexity .

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. It returns the highest possible
output value (big-O) for a given input.

Mathematical Representation of Big-O Notation:

For example, Consider the case of Insertion Sort. It takes linear time in the best case and
quadratic time in the worst case. We can safely say that the time complexity of the Insertion
sort is O(n2).
The Big-O notation is useful when we only have an upper bound on the time complexity of
an algorithm. Many times we easily find an upper bound by simply looking at the
algorithm.
3. Omega Notation (Ω-Notation):
The lowest bound of an algorithm's running time is shown in omega notation. As a
result, it offers an algorithm's best case complexity.

Let the function from the set of natural numbers to itself be represented by g and f. If
there is a constant c > 0 and a natural number n0 such that c*g(n) f(n) for all n n0, then
the function f is said to be (g).
Mathematical Representation of Omega notation:

Let's use the same example of an insertion sort again. Insertion Sort's time complexity can
be expressed as (n), although this is not very helpful information since we are typically
interested in the worst-case scenario and occasionally the average scenario.
Properties of Asymptotic Notations

1. General Properties

If P(n) is O(g(n)) then c*P(n) is also O(g(n)), where c is a constant.

Example:

P(n) = 3n²+4 is O(n²)

then, 6*P(n) = 6(3n²+4) = 18n²+24 is also O(n²).

Similarly, this property is satisfied by both the notation Ω and Θ.

Therefore, we can say,

If f(n) is Θ(g(n)), then c*f(n) is also Θ(g(n)), where c is a constant.

If f(n) is Ω (g(n)), then c*f(n) is also Ω (g(n)), where c is a constant.

2. Transitive Properties

If p(n) is O(g(n)) and g(n) is O(f(n)), then p(n) = O(f(n)).

Example:

If g(n) = n, f(n) = n² and p(n)=n³

⇒ n is O(n²) and n² is O(n³) then, n is O(n³)

Similarly, this property is satisfied by both the notation Ω and Θ.

We can say,

If p(n) is Θ(g(n)) and g(n) is Θ(f(n)), then p(n) = Θ(f(n)).

If p(n) is Ω (g(n)) and g(n) is Ω (f(n)), then p(n) = Ω (f(n))

3. Reflexive Properties

Reflexive properties are always easy to understand after transitive.

If p(n) is given, then p(n) is O(p(n)). Since the maximum value of p(n) will be p(n) itself!

Hence, x = p(n) and y = O(p(n)) tie themselves in reflexive relation always.

Example:

g(n) = n² ; O(n²) i.e O(g(n))

Similarly, this property is satisfied by both the notation Ω and Θ.

We can say that,

If p(n) is given, then p(n) is Θ(p(n)).

If p(n) is given, then p(n) is Ω (p(n)).

4. Symmetric Properties

If g(n) is Θ(f(n)), then f(n) is Θ(g(n)).

Example:

If p(n) = n² and f(n) = n²

then, p(n) = Θ(n²) and f(n) = Θ(n²)

Note that this property only satisfies for Θ notation.

5. Transpose Symmetric Properties

If g(n) is O(f(n)), then f(n) is Ω (g(n)).

Example:

If (n) = n, f(n) = n²

then n is O(n²) and n² is Ω (n)

This property only satisfies Ω and O notations.

Time-Space Trade-Off in Algorithms

Time-Space Trade-Off:
A tradeoff is a situation where one thing increases and another thing decreases. It is a way
to solve a problem in:
 Either in less time and with greater space,
 In a small amount of space with a lot of time.

The optimal algorithm is one that helps with problem solving while using less memory and
producing results more quickly. Yet, in general, it is not always possible to satisfy both of
these conditions at once. A lookup table-based method is the most common situation. This
suggests that it may be possible to save the answers to some queries for each potential
value. The entire lookup table can be written down to solve this problem, but doing so will
take up a lot of space and make it challenging to find the answers quickly. Another
approach is to calculate the findings without documenting anything; this method uses very
little paper but could take some time.So, the less space-efficient your algorithms are, the
more time-efficient they are.

Types of Space-Time Trade-off:

 Re-rendering or stored images

  Compressed or uncompressed data
 Smaller code or loop unrolling
 Lookup tables or recalculation

Compressed or Uncompressed data: The issue of data storage can be approached through
a space-time trade-off. Uncompressed data takes up more space but loads faster. Yet,
compressed data requires less storage space but more processing time to conduct the
decompression method. Working directly with compressed data is possible in a variety of
situations. It is quicker to work with compression than without compression in that scenario
of compressed bitmap indices.

Re-Rendering or Stored images: In this situation, saving just the source and rendering it
as an image would take up more memory but take less time; similarly, caching an image is
quicker than re-rendering but uses up more memory.

Smaller code or Loop Unrolling : Smaller code takes up less memory, but it takes more
time to compute because it has to go back to the beginning of the loop after each iteration.
Loop unrolling can increase binary size but improve execution performance. Although it
takes up more memory space, it takes less time to process.
Lookup tables or RecalculationA lookup table's implementation option allows for full table
inclusion, which shortens computation time but requires more memory. It can recalculate,
or compute table entries, as necessary, lengthening computation times while shortening
memory needs.
For instance: The recurrence relation, in mathematics, defines the Fibonacci Numbers'
sequence Fn:
F n = F n – 1 + F n – 2,
where, F0 = 0 and F1 = 1.
A simple solution to find the Nth Fibonacci term using recursion from the above recurrence
relation.
TimeComplexity: O(2N)
Auxiliary Space: O(1)

Abstract Data Types:

ADT will be covered, but first, let's have a look at the various built-in data types that are
available to us. Inbuilt data types include those like int, float, double, long, etc. with which
we may do operations like addition, subtraction, division, multiplication, etc. There may
now come a time when we need to define operations for our user-defined data type. Only
when we need them may we define these operations. So, we can design data structures
together with their operations to simplify the process of addressing problems, and such data
structures that are not built-in are known as Abstract Data Types (ADT).

An object's behaviour can be described by a set of values and a set of actions, and this
behaviour is known as an abstract data type (ADT). The definition of ADT merely specifies
the actions that must be taken, not how they must be carried out. It is unclear what
algorithms will be utilised to carry out the operations and how the data will be structured in
memory. Because it provides an implementation-independent view, it is dubbed "abstract."
An abstract data type is an abstraction of a data structure that provides only the interface
to which the data structure must adhere. The interface does not give any specific details
about something that should be implemented or in what programming language.

In other words, we can say that abstract data types are the entities that are definitions of
data and operations, but do not have implementation details. In this case, we know the data
that we are storing and the operations that can be performed on the data, but we don't know
about the implementation details. So, a user just needs to be aware of what a data type is
capable of, not how it will be used. Consider ADT as a "black box" that conceals the
internal organisation and design of the data type. The reason for not having implementation
details is that every programming language has a different implementation strategy. For
example, a C data structure is implemented using structures, while a C++ data structure is
implemented using objects and classes. Some examples of ADTs are List, Stack, and
Queue.

Abstract Data Type Model

The above figure shows the ADT model. There are two types of models in the ADT model,
i.e., the public function and the private function. The ADT model also contains the data
structures that we are using in a program. In this model, the first encapsulation is performed,
i.e., all the data is wrapped in a single unit, i.e., ADT. Then, the abstraction is performed
means showing the operations that can be performed on the data structure and the data
structures that we are using in a program.

Common ADTs:

Now, let's understand three common ADTs: List, Stack, and Queue ADTs.

1. List ADT
 The List ADT (Abstract Data Type) is a collection of elements in a sequential manner
that provides a set of operations without giving details of the internal
implementation. It provides an ordered way to store, access, and modify data.

Operations of List
The List ADT has to store the data sequentially and must have the following operations :
o insert(): For inserting an element at any position in the given list.
o get(): For returning an element at any given position in the list.
o remove(): For removing any element that occurs first from the non-empty list.
o removeAt():For removing the element from a non-empty list at the specified
location.
o replace():For replacing an element with another element at any position.
o size(): For returning the number of elements in the list.
o isEmpty():For returning a true value if the list is empty; otherwise, return a false
value.
o isFull(): For returning a true value if the list is full; otherwise, return a false value.
Only applied to the fixed-size implementations (for example, array-based lists).

2. Stack ADT
The stack ADT follows the LIFO (Last In, First Out) principle. It is a linear data structure.
In a stack ADT, the addition and removal of elements is done from only one end, which is
the top of the stack.

Operations of the Stack

The order of deletion and insertion should be as per the LIFO or FILO Principle in the stack
ADT. It must also support the following operations:
 o push(): For inserting an element at one end of the stack, called the top.
o pop(): For removing and returning the element at the top of the stack, provided the
stack is not empty.
o peek(): For returning the element at the top of the stack without removing it,
provided the stack is not empty.
o size(): For returning the total number of elements present in the stack.
o isEmpty(): For returning a true value if the stack is empty; otherwise, return a false
value.
o isFull(): For returning a true value if the stack is full; otherwise, return a false value.
It is only relevant for the fixed-capacity stacks (e.g., array-based).

3. Queue ADT

A linear data structure that follows the FIFO (First In, First Out) principle is the queue
ADT. It allows elements to be removed at the other end(front) and inserted at one end
(rear).

Operations of the Queue

The design of the queue ADT is similar to the stack ADT. It should give support to the
following operations:
o enqueue(): For inserting an element at the end of the queue.
o dequeue(): For removing and returning the first element of the queue, provided the
queue is not empty.
o peek(): For returning the element of the queue without removing it, provided the
queue is not empty.
o size(): For returning the total number of elements present in the queue.
o isEmpty(): For returning a true value if the queue is empty; otherwise, return a false
value.

Features of ADTs

The reasons for using ADTs in Java are mentioned below:

o Encapsulation: Hiding details of complex implementation behind a clean interface.
o Reusability: Allowing various internal implementations (e.g., linked list or array)
without changing external usage.
o Modularity: Simplifying updates and maintenance by the separation of logic.
o Security: Protecting data by stopping direct access and minimizing unintended
changes and bugs.

Advantages of ADTs
o Encapsulation: ADTs facilitate a way for encapsulating data and operations into a
single unit. Hence, making it easier to modify and manage the data structure.
 o Abstraction: ADTs allow users to use data structures without knowing the
implementation details, which can do simplification programming and reduction in
errors.
o Data Structure Independence: Implementation of ADTs can be done using
different data structures. Thus, making it easier to adapt to the changing
requirements and needs.
o Information Hiding: ADTs can protect the data integrity by taking control of
access and stopping unauthorized modifications.
o Modularity: One ADT can be combined with the other ADT to generate more
complex data structures, which can increase modularity and flexibility in
programming.

Disadvantages of ADTs
o Overhead: Implementation of ADTs can put some overhead in terms of processing
and memory, which can affect performance.
o Complexity: Implementation of ADTs can be complex, especially for complex and
large data structures.
o Learning Curve: To use ADTs, there is a requirement for knowledge of their
implementation and usage, which can take time and effort to learn.
o Limited Flexibility: There can be limitations in the functionality of some ADTs, or
they may not be apt for all types of data structures.
o Cost: Implementation of ADTs may require additional investment and resources,
which can increase the development cost.
Array Data Structure
A group of items kept in consecutive memory regions is known as an array. The goal is to
group objects of the same category for storage. As a result, it is simpler to determine each
element's position by simply adding an offset to a base value, or the address in memory where
the array's first element is stored (generally denoted by the name of the array).

A group of related data elements stored at adjacent memory locations is referred to as an array.
One of the most basic data structures, it allows for random access to each data element by its
index number.

Basic Terminologies

 Array Element: Items of an array are known as its elements, which are kept in an
array and can be accessed randomly with the help of their index number.
 Array Index: In an array, elements are recognized by their indices. Array index
begins from 0. In other words, zero-based indexing occurs in an array.
 Array Length: The number of elements in an array determines the array length.
 Contiguous Memory: Array elements are stored back-to-back in memory for fast
access

Representation of an array:

Several programming languages allow us to express an array in different ways. Let's look at an
array declaration in the C language as an example.

As seen in the example above, several of the following points are crucial:

 Index begins at 0.
 Because the array is 10 items long, 10 elements can be stored in it.
  The array's index can be used to access any element.

If you imagine yourself at the bottom of the stairwell in the above image, you can see the
staircase from above. The array's index can be used to uniquely identify each element (in a
similar way as you could identify your friends by the step on which they were on in the above
example).
Why are arrays required?
In computer programming; most cases require storing a large number of data of a similar type.
To store such an amount of data, we need to define a large number of variables. It would be
very difficult to remember the names of all the variables while writing the programs. Instead of
naming all the variables with a different name, it is better to define an array and store all the
elements into it.

Arrays are useful because -

o Sorting and searching a value in an array is easier.

o Arrays are best to process multiple values quickly and easily.
o Arrays are good for storing multiple values in a single variable

Applications of Array Data Structure:

Arrays mainly have advantages like random access and cache friendliness over other data
structures that make them useful.

Below are some applications of arrays.

 Storing and accessing data: Arrays store elements in a specific order and allow
constant-time O(1) access to any element.

 Searching: If data in array is sorted, we can search an item in O(log n) time. We can
also find floor(), ceiling(), kth smallest, kth largest, etc efficiently.
  Matrices: Two-dimensional arrays are used for matrices in computations like graph
algorithms and image processing.

 Implementing other data structures: Arrays are used as the underlying data
structure for implementing stacks and queues.

 Dynamic programming: Dynamic programming algorithms often use arrays to store

intermediate results of subproblems in order to solve a larger problem.

 Data Buffers: Arrays serve as data buffers and queues, temporarily storing incoming
data like network packets, file streams, and database results before processing.

Advantages of Array Data Structure:

 Efficient and Fast Access: Arrays allow direct and efficient access to any element in
the collection with constant access time, as the data is stored in contiguous memory
locations.

 Memory Efficiency: Arrays store elements in contiguous memory, allowing efficient

allocation in a single block and reducing memory fragmentation.

 Versatility: Arrays can be used to store a wide range of data types, including integers,
floating-point numbers, characters, and even complex data structures such as objects
and pointers.

 Compatibility with hardware: The array data structure is compatible with most
hardware architectures, making it a versatile tool for programming in a wide range of
environments.

Disadvantages of Array Data Structure:

 Fixed Size: Arrays have a fixed size set at creation. Expanding an array requires
creating a new one and copying elements, which is time-consuming and memory-
intensive.

 Memory Allocation Issues: Allocating large arrays can cause memory exhaustion,
leading to crashes, especially on systems with limited resources.

 Insertion and Deletion Challenges: Adding or removing elements requires shifting

subsequent elements, making these operations inefficient.

 Limited Data Type Support: Arrays support only elements of the same type,
limiting their use with complex data types.

 Lack of Flexibility: Fixed size and limited type support make arrays less adaptable
than structures like linked lists or trees.
Basic operations:

Now, let's discuss the basic operations supported in the array -

 Traversal: The array's elements are printed using this operation.

 Insertion: This process adds an element to a specific index.
 Deletion: It is used to remove a specific element from an index.
 Search: You can use this to look up an element using either the provided index or its
value.
 Update: This operation changes an element at a specific index.

Memory allocation of an array (Array Indexing)

An array's data elements are kept together in contiguous regions in the main memory. The
address of the first element in main memory, also known as the base address, is represented by
the array name. The array's elements are each represented by an appropriate index.

We can define the indexing of an array in the below ways -

1. No indexing: Arr[0] will be the first element of the array (zero-based indexing).

2. 1 (one-based indexing): arr[1] will be the array's first element.

3. n (n-based indexing): The array's first member can be located at any arbitrary index
number.

We've displayed the memory allocation for a 5-by-5 array in the image above. The array has a
0-based method of indexing. The array's base address is 100 bytes. That is arr[0] address's, As
the data type used in this case is 4 bytes in size, each element will occupy 4 bytes in the RAM.

Memory Calculation of array:

It is the total memory (physical size) used by the array. The total memory occupied by an
array can be calculated by using the following formula:

Total Memory = Number of Elements × Size of Each Element

For Example, If an array has 5 elements of type int, then total memory occupied by an array
will be 10 bytes because int has 2 bytes.

Number of elements in an array (or range of indices):

The formula is used to calculate the number of elements in an array is given below:

Number of Elements = (Upper Bound − Lower Bound) + 1

Where:

 Lower bound index of the first element of the array

 Upper bound index of the last element of the array

For Example: int arr[10]; // index range: 0 to 9

In the given example arr[0----9], Lower Bound = 0, and Upper Bound = 9

Total no. of element = (9−0)+1=10 elements

 One-Dimensional and Two-dimensional Array

Array is a data structure that is used to store variables that are of similar data types
at contiguous locations. The main advantage of the array is random access and cache
friendliness. There are mainly three types of the array:
 One-dimensional arrays (1D)
 2-dimensional arrays (2D),
 multidimensional arrays

One Dimensional Array:

 It is a list of the variable of similar data types.

 It allows random access and all the elements can be accessed with the help of their
index.
 The size of the array is fixed.
 For a dynamically sized array, vector can be used in C++.
 Representation of 1D array:

An array can be declared with the bracket punctuators [ ], as shown in the below syntax:

 Data_Type Array_Name[Number_Of_Elements]
The below example shows a declaration of an array having the capacity to hold 50
elements of type integers and the name of that array is arr :
int arr[50];

Initializing the array:

We can initialize an array in C by assigning value to each index one by one or by using a
single statement as follows −
Example 1 :

Assign one value each time to the array

int arr[50];

arr[0]=12;
arr[1]= 43;
arr[2] = 14;
.
.
.
.
.
arr[49] = 54;
Example 2:

Using a single statement

int arr[5] = {10,32,11,45,38};

Program in C to implement One dimensional array:

#include <stdio.h>

int main() {

int n;

printf("Enter number of elements: ");

scanf("%d", &n);

int arr[n]; // Declare array of size n

printf("Enter %d elements:\n", n);

for(int i = 0; i < n; i++) {

scanf("%d", &arr[i]); // Taking input

printf("You entered:\n");
 for(int i = 0; i < n; i++) {

printf("%d ", arr[i]); // Printing array

return 0;

Two Dimensional Array:

 It permits random access, all components may be obtained with the aid of their
index, and it is a list of lists of the same data type.

 It may alternatively be thought of as a group of 1D arrays. The Matrix is another

name for it.
 Its dimensions can be raised from two to three, four, and so on.
 Each of them is known as a multi-dimension array.

 A 2D array is the most typical type of multidimensional array.

2D array representation:

We can say a Multidimensional array is an array of arrays. Two Dimensional arrays is also
a multidimensional array. In a Multi-Dimensional array, elements of an array are arranged
in the form of rows and columns.
Multidimensional array stores elements in tabular form which is also known as in row-
major order or column-major order.

Declaration of Multi-dimensional Array:

data_type array_name[size1][size2]….[sizeN];
 data_type: It defines the type of data that can be held by an array. Here data_type
can be int, char, float. etc.
 array_name: Name of the array
 size1, size2,… ,sizeN: Sizes of the dimensions

Pictorial representation of a multidimensional array:

number_of_arrays: number of arrays which flow in the z-axis

rows: number of the rows in the y-axis
columns: number of the columns flow in the x-axis

Two-dimensional array

int arr1[10][20];
Program in C to implement two dimensional array:

#include <stdio.h>

int main() {

int arr[3][3];

int i, j;

// Input elements

printf("Enter elements of 3x3 matrix:\n");

for (i = 0; i < 3; i++) {

for (j = 0; j < 3; j++) {

scanf("%d", &arr[i][j]);

// Output elements

printf("Matrix is:\n");

for (i = 0; i < 3; i++) {

for (j = 0; j < 3; j++) {

printf("%d\t", arr[i][j]);

printf("\n");

}
 return 0;

Three-dimensional array:

A three-dimensional (3D) array in C is an extension of the concept of a 2D array. While a

2D array can be visualized as a table of rows and columns, a 3D array can be imagined as
multiple such tables (or matrices) stacked together, forming a “cube-like” structure. It is
declared using three dimensions: [blocks][rows][columns]. For example, int arr[2][3][4];
creates an array with 2 blocks, each containing 3 rows and 4 columns, giving a total of 24
elements. Each element is accessed using three indices, such as arr[i][j][k], where i refers to
the block, j refers to the row, and k refers to the column.

Declaration of 3D Array:
data_type array_name[size1][size2][size3];

For Example: int arr[2][3][4];

 2 blocks (first dimension)

 Each block has 3 rows (second dimension)

 Each row has 4 columns (third dimension)

 Total elements = 2 × 3 × 4 = 24

Initialization:

int arr[2][2][3] = { { {1, 2, 3}, {4, 5, 6} }, { {7, 8, 9}, {10, 11, 12} }};
C Program for 3D Array:

#include <stdio.h>

int main() {

int arr[2][2][3];

int i, j, k;

// Input elements

printf("Enter 12 elements for 2x2x3 array:\n");

for (i = 0; i < 2; i++) {

 for (j = 0; j < 2; j++) {

for (k = 0; k < 3; k++) {

scanf("%d", &arr[i][j][k]);

// Output elements

printf("\n3D Array Elements:\n");

for (i = 0; i < 2; i++) {

printf("Block %d:\n", i);

for (j = 0; j < 2; j++) {

for (k = 0; k < 3; k++) {

printf("%d ", arr[i][j][k]);

printf("\n");

printf("\n");

return 0;

Difference Table:

Basis One Dimension Array Two Dimension Array

Store a single list of the

element of a similar data Store a ‘list of lists’ of the element of
Definition type. a similar data type.

Represent multiple data Represent multiple data items as a

Representation items as a list. table consisting of rows and columns.
 The declaration varies for
different programming
language: The declaration varies for different
programming language:
1. For C++,
datatype 1. For C++,
variable_name[row] datatype variable_name[row]
2. For Java, [column]
datatype [] 2. For Java,
variable_name= new datatype [][] variable_name= new
Declaration datatype[row] datatype[row][column]

Dimension One Two

size of(datatype of the size of(datatype of the variable of the

variable of the array) * size array)* the number of rows* the
Size(bytes) of the array number of columns.

Address of a[i][j] can be calculated in

two ways row-major and column-
major
1. Column Major: Base Address +
Size of each element (number of
rows(j-lower bound of the column)
+(i-lower bound of the rows))
Address of a[index] is 2. Row Major: Base Address + Size
equal to (base Address+ of each element (number of
Address Size of each element of columns(i-lower bound of the row)
calculation. array * index). +(j-lower bound of the column))

int arr[2][5]; //an array with two rows

int arr[5]; //an array with
and five columns will be created.
one row and five columns
will be created. a b c d e
{a , b , c , d , e} f g h i j
Example

Address calculation for 1-D, 2-D, and 3-D elements using row-major and column-major
order:
In data structures, array addressing refers to the process of calculating the memory address of
an element in an array. Arrays are stored in contiguous memory locations, and each element
can be accessed using its index. The formula for calculating the address depends on the type of
array (1D, 2D, or 3D) and the storage order (row-major or column-major).

1. Address Calculation for 1D Array

An array is a collection of elements of the same data type stored in contiguous memory
locations. To access any element, we calculate its address using the base address and the
index.

An example of a linear array is a 1-dimensional array, often known as a single-dimension

array. A single subscript, which can stand for either a row or column index, is used to
access each element.

The following formula is used to determine the address of an element in an array:

Address (A[i]) = B + (i−LB) × W

Where:

 Address (A[i]) = Address of element A[i]

 B = Base address (starting address of array)
 i = Index of the element
 LB = Lower bound of the array (index of the first element of the array)
 W = Size of each element (in bytes)

Example 1: Get the address of A[1700] given that the base address of an array
A[1300........... 1900] is 1020 and that each element has a size of 2 bytes in the memory.

Solution:
Given:
B = Base Address 1020
Lower Bound of array is 1300.
One element's storage space in any array W = 2 Byte
Index of element with address i = 1700.
Formula used:
Address of A[i] = B + W * (i – LB)
Address of A[1700] = 1020 + 2 * (1700 – 1300)
= 1020 + 2 * (400)
= 1020 + 800
Address of A[1700] = 1820

Example 2: Get the address of A[3] given that the base address of an array A[10] is 1000
and that each element has a size of 4 bytes in the memory.

Solution: Given:
B = Base Address 1000
Lower Bound of array is 0.
One element's storage space in any array W = 4 Byte
Index of element with address i = 3.

Formula used:

Address of A[i] = B + W * (i – LB)

Address(A[3]) = 1000 + 4 × (3 - 0) = 1012

2. Address Calculation for 2D Array:

An array of arrays can be used to define a 2-dimensional array. The 2-Dimensional arrays
are arranged as matrices, which may be written as array[M][N], where M denotes the
number of rows and N the number of columns.

There are two approaches to determine the address of any element in a 2-Dimensional
array:

1. Row Major Order

2. Major Column Order
1. Row Major Order:

Row major ordering places things in successive memory locations as they move across the
rows and then down the following row. In Row major method elements of an array are
arranged sequentially row by row. Thus, elements of first row occupies first set of memory
locations reserved for the array, elements of second row occupies the next set of memory and
so on.
The following formula is used to determine the address of the element using row-major order:

Address of A[i][j] = B + W*[ N * (i-L 1) + (j-L2)]

Where:

 Address (A[i][j]) = Address of element A[i][j]

 M = number of rows (U1-L1+1)
 N = number of columns (U2-L2+1)
 B = base address of array
 W = size of each element (bytes)
 i = row index (0 ≤ i < m)
 j = column index (0 ≤ j < n)
 L1 = Lower bound of rows
 U1 = Upper bound of rows
 L2 = Lower bound of columns
 U2 = Upper bound of columns

Example 1: Given an array, arr[1.........10][1.........15] with a base value of 100 and 1 byte
for each element in memory. Using row-major order, locate the address of arr[8][6].
Solution:
Given:
Address at base B = 100
One element's storage space in any array W = 1 byte

row index i= 8
column index j = 6
Lower bound of rows L1 = 1

Upper bound of rows U1 = 10

Lower bound of columns L2 = 1

Upper bound of columns U2 = 15

Total number of column in given matrix N is equal to Upper Bound - Lower Bound + 1.
= 15 – 1 + 1
= 15
Formula:
Address of A[i][j] = B + W*[ N * (i-L 1) + (j-L2)]

Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))

= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[8][6] = 210

2. Column Major Order:

Column-major order refers to the arrangement of array elements when they are stored by
traversing one column before advancing to the next. In Column major method elements of
an array are arranged sequentially column by column. Thus, elements of first column
occupies first set of memory locations reserved for the array, elements of second column
occupies the next set of memory and so on.

The following formula is used to determine the address of the element using row-major order:

Address of A[i][j] = B + W*[ M * (j-L 2) + (i-L1)]

Where:

 Address (A[i][j]) = Address of element A[i][j]

 M = number of rows (U1-L1+1)
 N = number of columns (U2-L2+1)
 B = base address of array
 W = size of each element (bytes)
 i = row index (0 ≤ i < m)
 j = column index (0 ≤ j < n)
 L1 = Lower bound of rows
 U1 = Upper bound of rows
 L2 = Lower bound of columns
 U2 = Upper bound of columns
Example 1: Given an array, arr[1.........10][1.........15] with a base value of 100 and 1 byte
for each element in memory. Using column-major order, locate the address of arr[8][6].
Solution:
Given:
Address at base B = 100
One element's storage space in any array W = 1 byte

row index i= 8
column index j = 6
Lower bound of rows L1 = 1

Upper bound of rows U1 = 10

Lower bound of columns L2 = 1

Upper bound of columns U2 = 15

Total number of row in given matrix N is equal to Upper Bound - Lower Bound + 1.
= 10 – 1 + 1
= 10
Formula:
Address of A[i][j] = B + W*[ M * (j-L 2) + (i-L1)]

Address of A[8][6] = 100 + 1 * ((6 – 1) * 10+ (8 – 1))

= 100 + 1 * ((5) * 10 + (7))
= 100 + 1 * (57)
Address of A[8][6] = 157

3. Address Calculation for 3D Array:

A 3D array is an extension of 2D arrays, where we add a depth (z-dimension).

Calculate the address of any element in the 3-D Array:

A set of 2-Dimensional arrays makes into a 3-Dimensional array. Three subscripts are used
to make it explicit:
1. Block size
2. Row width
2. Column width
A larger array can store more data if it has more dimensions.
Example:
 3-D array

There are two approaches to determine the address of any element in 3-Dimensional arrays:
-
 Row Major Order
 Column Major Order

For a 3D array i.e. int A[x][y][z];, the formula extends further:

Row-Major Order:

Address of A[i][j][k] = B + W *[(M* N * (i-L1) + N*(j-L2) + (k-L3)]

 B = Base Address (start address)

 W = Weight (storage size of one element stored in the array)
 P = Width (total number of cells depth-wise) (U1-L1+1)
 M = Row (total number of rows) (U2-L2+1)
 N = Column (total number of columns) (U3-L3+1)
 i = plane index (0 ≤ i < x)
 j = row index (0 ≤ j < y)
 k = column index (0 ≤ k < z)
 L1 = Lower bound of Plans/width
 U1 = Upper bound of Plans/width
 L2 = Lower bound of rows
 U2 = Upper bound of rows
 L3 = Lower bound of columns
 U3 = Upper bound of columns
Example: Given an array, arr[1:9, -4:1, 5:10] with a base value of 400 and the size of each
element is 2 Bytes in memory find the address of element arr[5][-1][8] with the help of row-
major order?

Solution:

Given:

Block Subset of an element whose address to be found i = 5

Row Subset of an element whose address to be found j = -1

Column Subset of an element whose address to be found k = 8

Base address B = 400

Storage size of one element store in any array(in Byte) W = 2

Lower Limit of blocks in matrix L1 = 1

Lower Limit of row/start row index of matrix L2 = -4

Lower Limit of column/start column index of matrix L3 = 5

M(row) = Upper Bound - Lower Bound + 1 = 1 - (-4) + 1 = 6

N(Column)= Upper Bound - Lower Bound + 1 = 10 - 5 + 1 = 6

Formula used:

Address of A[i][j][k] = B + W *[(M* N * (i-L1) + N*(j-L2) + (k-L3)]

Address of arr[5][-1][8] = 400 + 2 * {[6 * 6 * (5 - 1)] + 6 * [(-1 + 4)]} + [8 - 5]

= 400 + 2 * (6*6*4)+(6*3)+3

= 400 + 2 * (165)

= 730

Column-Major Order:

Address of A[i][j][k] = B + W *[(P* M * (k-L3) + P*(j-L2) + (i-L1)]

Where:

 B = Base Address (start address)

 W = Weight (storage size of one element stored in the array)
  P = Width (total number of cells depth-wise) (U1-L1+1)
 M = Row (total number of rows) (U2-L2+1)
 N = Column (total number of columns) (U3-L3+1)
 i = plane index (0 ≤ i < x)
 j = row index (0 ≤ j < y)
 k = column index (0 ≤ k < z)
 L1 = Lower bound of Plans/width
 U1 = Upper bound of Plans/width
 L2 = Lower bound of rows
 U2 = Upper bound of rows
 L3 = Lower bound of columns
 U3 = Upper bound of columns

Example: Given an array arr[1:8, -5:5, -10:5] with a base value of 400 and the size of
each element is 4 Bytes in memory find the address of element arr[3][3][3] with the help
of column-major order?

Solution:
Given:
Row Subset of an element whose address to be found i = 3
Column Subset of an element whose address to be found j = 3
Block Subset of an element whose address to be found k = 3
Base address B = 400
Storage size of one element store in any array(in Byte) W = 4
Lower Limit of blocks in matrix L 1 = 1
Lower Limit of row/start row index of matrix L 2 = -5
Lower Limit of column/start column index of matrix L 3 = -10
P (width)= Upper Bound - Lower Bound + 1 = 8 - 1 + 1 = 8
M (row)= Upper Bound - Lower Bound + 1 = 5 - (-5 ) + 1 = 11

Formula used:
Address of A[i][j][k] = B + W *[(P* M * (k-L3) + P*(j-L2) + (i-L1)]

Address of arr[3][3][3] = 400 + 4 * ((8*11*(3-(-10)+ 8*(3-(-5)+ (3-1))

= 400 + 4 * ((88 * 13+ 8 * 8 + 2)
= 400 + 4 * (1210)
= 400 + 4840
= 5240
 Sparse Matrix and its representations

A matrix is a two-dimensional data item with total values of m x n and is composed of m

rows and n columns. A matrix is referred to as sparse if the majority of its elements have a
value of 0.
 Why use a sparse matrix rather than a basic matrix
 Storage: Less memory can be utilised to keep solely non-zero elements because there
are fewer of them than zeros.
 Computing time: By rationally creating a data structure that only traverses non-zero
components, computation time can be reduced.

Example:

00304
00570
00000
02600
As most zeroes in a sparse matrix are useless, representing it using a 2D array wastes a
significant amount of memory. Hence, we solely store non-zero elements and don't keep
zeroes along with them. This entails using triples to store non-zero elements (Row,
Column, value).
There are numerous ways to express sparse matrices. Here are two popular representations:
1. Array representation
2. Linked list representation

Method 1: Using Arrays:

 A sparse matrix with three rows called and represented by a 2D array is
 Row: The row's index where the non-zero element is situated
 Column:Index of the column containing the non-zero element
 Value: Value of the element at index - that is non-zero (row,column)

Implementation:

// C++ program for Sparse Matrix Representation

// using Array
#include<stdio.h>
intmain()
{
// Assume 4x5 sparse matrix
intsparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
intsize = 0;
for(inti = 0; i < 4; i++)
for(intj = 0; j < 5; j++)
if(sparseMatrix[i][j] != 0)
size++;

// number of columns in compactMatrix (size) must be

// equal to number of non - zero elements in
// sparseMatrix
intcompactMatrix[3][size];
// Making of new matrix
intk = 0;
for(inti = 0; i < 4; i++)
for(intj = 0; j < 5; j++)
if(sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
 for(inti=0; i<3; i++)
{
for(intj=0; j<size; j++)
printf("%d ", compactMatrix[i][j]);
printf("\n");
}
return0;
}

Output
001133
242312
345726

Time Complexity: O(NM), where N and M are the number of rows and columns in the
sparse matrix, respectively.

Auxiliary Space: O(NM), where N and M are the number of rows and columns,
respectively, in the sparse matrix.
 Linked List Data Structure
A linear data structure called a linked list has elements that are not kept in consecutive locations
in memory. As seen in the graphic below, pointers are used to connect the elements in a linked
list:
 A linked list is a group of randomly stored nodes, which are objects, in the memory.
 Each node has two fields: the data that is stored there and a pointer that points to the
node after it in the memory.
 A pointer to the null is contained in the list's final node.

A linked list is made up of nodes, each of which has a data field and a reference (or link) to the
node after it in the list.

Uses of Linked List

 A continuous presence of the list in memory is not necessary. The node can be located
anywhere in memory and connected to other nodes to form a list. This optimises the use of
available space.
 list size is constrained by memory size and does not require prior declaration.
 An empty node is not permitted in a linked list.
 A singly linked list can be used to hold values of either primitive kinds or objects.
Why use linked list over array?

The group of elements that are to be saved independently in memory up until this point have
been organised using an array data structure. But, in order to choose the data structure that
will be used throughout the programme, it is important to be aware of the advantages and
disadvantages of Array.

Array contains following limitations:

1. The size of array must be known in advance before utilising it in the programme.

2. Raising the array's size is a laborious operation. At runtime, increasing the array's size is
virtually difficult.

3. The RAM must be used to continuously store every element of the array. Any element that
is added to the array requires the relocation of all of its predecessors.

The data structure that can overcome all of an array's drawbacks is a linked list. The usage of
linked lists is advantageous because

1. It uses dynamic memory allocation. The linked list's nodes are all kept in memory in a non-
contiguous fashion and connected via pointers.
2. Sizing is no longer a concern as we do not need to declare its size at the time of
declaration. List expansion is governed by software requirements and memory space
constraints.

Linked List vs Array:

Array: A faster way to access an element at a certain index is made possible by the fact that
elements in arrays are kept in contiguous memory locations, resulting in easily calculable
addresses for the elements stored.

Linked List: Because the storage structure of linked lists is less strict and the components
are typically not stored in close proximity to one another, it is necessary to store the elements
with additional tags that refer to the subsequent elements.

Whether data structure would be better appropriate for a particular case depends on the
difference in the data storage technique.
Differences between array and linked-list
 Size: Since data can only be stored in contiguous blocks of memory in an array, its size
cannot be altered at runtime due to the risk of overwriting other data.
However, each node in a linked list points to the following one. such that data can exist
at scattered (non-contiguous) addresses; this allows for a dynamic size that can change
at runtime.

 Memory allocation: For arrays at compile time and at runtime for linked lists. but, a
dynamically allocated array also allocates memory at runtime.

 Memory efficiency: For the same number of elements, linked lists use more memory as
a reference to the next node is also stored along with the data. However, size flexibility
in linked lists may make them use less memory overall; this is useful when there is
uncertainty about size or there are large variations in the size of data elements;
Memory equivalent to the upper limit on the size has to be allocated (even if not all of it
is being used) while using arrays, whereas linked lists can increase their sizes step-by-
step proportionately to the amount of data.

 Execution time: Any element in an array can be directly accessed with its index.
However, in the case of a linked list, all the previous elements must be traversed to
reach any element.
Also, better cache locality in arrays (due to contiguous memory allocation) can
significantly improve performance. As a result, some operations (such as modifying a
certain element) are faster in arrays, while others (such as inserting/deleting an element
in the data) are faster in linked lists.
 Insertion: In an array, insertion operation takes more time but in a linked list these
operations are fast. For exampling order to add a new element to the array at the end
position in the array and the array is full then we copies the array into another array and
then we can add an element whereas if the linked list is full then we find the last node
and make it next to the new node.

 Dependency: In an array, values are independent of each other but

In the case of linked list nodes are dependent on each other. one node is dependent on
its previous node. If the previous node is lost then we can’t find its next subsequent
nodes.

Difference Between Array and linked List:

Advantages of Linked Lists:
 We must be aware of the maximum number of elements because the size of the
arrays is fixed. Also, regardless of utilisation, the allotted RAM is typically equal to
the upper limit, and in actual use, the top limit is rarely surpassed.
 Adding a new element to an array of elements is expensive because space must be
made for it and other elements must be moved to make that space.
Disadvantages of Linked Lists:
 Random access is prohibited. Accessing elements requires going from the root node
sequentially.
 Hence, using linked lists for a binary search is not possible.
 Arrays offer superior cache locality, which can significantly improve performance.
 While working with pointers, it will be confusing and take a lot of time to traverse
and change the pointers.

Applications of Linked Lists:

 Linked Lists can be used to implement stacks, queue, deque, sparse matrices and
adjacency list representation of graphs.
 Dynamic memory allocation in operating systems and compilers (linked list of free
blocks).
 Manipulation of polynomials
 Arithmetic operations on long integers.
 In operating systems, they can be used in Memory management, process scheduling
(for example circular linked list for round robin scheduling) and file system.
 Algorithms that need to frequently insert or delete items from large collections of
data.
 LRU cache, which uses a doubly linked list to keep track of the most recently used
items in a cache.

Types of Linked List:

There are four types of Linked List in Data Structures which are discussed below:

 Singly Linked list

 Doubly Linked list
 Circular Linked list
 Doubly Circular Linked list

1) Singly Linked List:

It is the commonly used linked list in programs. The singly linked list is a data structure
that contains two parts, i.e., one is the data part, and the other one is the address part, which
contains the address of the next or the successor node. The address part in a node is also
known as a pointer.

Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300
respectively. The representation of three nodes as a linked list is shown in the below figure:
We can observe in the above figure that there are three different nodes having address 100,
200 and 300 respectively. The first node contains the address of the next node, i.e., 200, the
second node contains the address of the last node, i.e., 300, and the third node contains the
NULL value in its address part as it does not point to any node. The pointer that holds the
address of the initial node is known as a head pointer.

The linked list, which is shown in the above diagram, is known as a singly linked list as it
contains only a single link. In this list, only forward traversal is possible; we cannot
traverse in the backward direction as it has only one link in the list.

Representation of the node in a singly linked list

struct node
{
int data;
struct node *next;
}

In the above representation, we have defined a user-defined structure named a node

containing two members, the first one is data of integer type, and the other one is the
pointer (next) of the node type.

Applications of Singly linked List:

Application Explanation Example / Use Case
Used to manage free memory malloc() and free() in C keep
Dynamic Memory
blocks dynamically without track of free memory using
Management
wasting space. linked lists.
Singly linked list allows efficient
Implementation of
push and pop operations in O(1) Undo operations in text editors.
Stack
time.
Enqueue and dequeue operations
Implementation of Printer queue, customer service
can be done easily using linked
Queue queue.
lists.
Each node stores coefficient and
Polynomial Storing 5x² + 4x + 7 as linked list
exponent → allows easy addition
Representation nodes.
& multiplication.
Sparse Matrix Stores only non-zero elements → Large matrices in scientific
Representation saves memory compared to arrays. computation.
Symbol Tables in Used to store identifiers and their C/Java compiler maintains
Application Explanation Example / Use Case
Compilers attributes in compiler design. variable details.
Collisions in hash tables are
Hashing with
resolved by storing keys in a Hash map implementations.
Chaining
linked list.
Directory/File Stores file details in nodes Linux/Windows file directory
Systems connected as linked lists. management.
Music playlists,
Real-Life Used in sequential navigation
Forward/Backward navigation in
Applications tasks.
browsers.

Advantage
 Dynamic size (no fixed limit like arrays)
 Efficient insertion and deletion (especially in the middle)
 Can implement complex data structures like stack, queue, graph
Disadvantage
 Extra memory required for storing pointers
 No direct/random access (need traversal)
 Cache unfriendly (not stored in contiguous memory)

Common Operation in Singly Linked List:

Operation Explanation Example

Build a linked list by allocating nodes
Creation List: 10 → 20 → 30
dynamically and linking them.
Visit each node from head to last using next
Traversal Display: 10 20 30
pointer.
Insertion Add a new node before the first node (update
Insert 5 → 5 10 20 30
(Beg) head).
Insertion
Add a new node after the last node. Insert 40 → 10 20 30 40
(End)
Insertion Add a new node at any position by adjusting Insert 25 after 20 → 10
(Pos) links. 20 25 30
Deletion (Beg) Remove the first node and update head pointer. Delete 10 → 20 30
Deletion Remove the last node by setting second last
Delete 30 → 10 20
(End) node’s next = NULL.
Deletion (Pos) Remove a node from a specific position. Delete 25 → 10 20 30
Traverse and compare data with key value until
Searching Search 20 → FOUND
found.
Counting Count number of nodes by traversing the list. Count = 3
Update 20 → 200 → 10
Updating Modify node data at a given position.
200 30
Rearrange nodes in ascending or descending
Sorting Sort → 10 20 30 40
order.

2) Doubly Linked List

As the name suggests, the doubly linked list contains two pointers. We can define the
doubly linked list as a linear data structure with three parts: the data part and the other two
address part. In other words, a doubly linked list is a list that has three parts in a single
node, includes one data part, a pointer to its previous node, and a pointer to the next node.

Suppose we have three nodes, and the address of these nodes are 100, 200 and 300,
respectively. The representation of these nodes in a doubly-linked list is shown below:

As we can observe in the above figure, the node in a doubly-linked list has two address
parts; one part stores the address of the next while the other part of the node stores the
previous node's address. The initial node in the doubly linked list has the NULL value in
the address part, which provides the address of the previous node.

Representation of the node in a doubly linked list

struct node
{
int data;
struct node *next;
struct node *prev;
}
In the above representation, we have defined a user-defined structure named a node with
three members, one is data of integer type, and the other two are the pointers, i.e., next and
prev of the node type. The next pointer variable holds the address of the next node, and the
prev pointer holds the address of the previous node. The type of both the pointers, i.e., next
and prev is struct node as both the pointers are storing the address of the node of the struct
node type.

Applications of Doubly linked list:

Application Area Explanation
Web Browsers Used for forward and backward navigation in history.
Text Editors Supports undo and redo operations.
Media Players Maintains playlists, allowing previous/next song navigation.
Efficient implementation of double-ended queues
Deque & Queue
(insert/delete from both ends).
Used in OS to keep track of free and allocated memory
Memory Management
blocks.
Each term of polynomial can be stored as a node in DLL for
Polynomial Operations
easy manipulation.
Navigation Systems Useful in metro/train routes, where traversal is needed in
Application Area Explanation
both directions.
Cache Implementation Used along with hash maps to design Least Recently Used
(LRU) (LRU) caches.

Advantages of Doubly Linked List:

1. Bidirectional Traversal: You can traverse forward (using next) as well as
backward (using prev).
2. Efficient Deletion: Given a pointer to a node, you can delete it in O(1) time (no
need to traverse from the head), since you can update both prev and next.
3. Insertion at Both Ends: Insertion at head or tail is efficient because you can update
both directions easily.
4. Easy to Implement Deque / Navigation Features: Useful for undo/redo, browser
history, and music playlist navigation, where both forward and backward movement
is needed.

Disadvantages of Doubly Linked List:

1. Extra Memory Per Node: Each node requires an additional pointer (prev), making
DLL more memory-consuming than singly linked list.
2. More Complex Implementation: Both prev and next must be handled carefully
during insertion and deletion, which increases chances of errors (broken links, null
pointer issues)
3. Slower Operations Due to Overhead: Extra pointer manipulations during
insertion/deletion cause slightly more overhead compared to singly linked list.
4. Not Cache-Friendly: Like singly linked list, nodes are scattered in memory, so
traversals may be slower compared to arrays due to poor locality of reference.

Common Operation in Doubly Linked List:

3) Circular Linked List:

A circular linked list is a variation of a singly linked list. The only difference between the
singly linked list and a circular linked list is that the last node does not point to any node in
a singly linked list, so its link part contains a NULL value. On the other hand, the circular
linked list is a list in which the last node connects to the first node, so the link part of the
last node holds the first node's address. The circular linked list has no starting and ending
node. We can traverse in any direction, i.e., either backward or forward. The diagrammatic
representation of the circular linked list is shown below:
Representation of the node in a Circular linked list

struct node
{
int data;
struct node *next;
}
A circular linked list is a sequence of elements in which each node has a link to the next
node, and the last node is having a link to the first node. The representation of the circular
linked list will be similar to the singly linked list.

Applications of Circular linked list:

Application Area Explanation
Round-Robin Used in CPU process scheduling (time-sharing systems). Each
Scheduling process is given a fixed time slice in a circular fashion.
After the last song/video, it loops back to the first one → supports
Music/Video Playlists
continuous play.
Multiplayer Games Helps in cycling through players’ turns (e.g., Ludo, Card games).
Circular lists are used to implement circular buffers (useful in
Buffer Management
producer-consumer problems, streaming).
Queue Particularly in circular queues, where insertion and deletion happen
Implementation in a circular manner.
Used in task scheduling and managing memory blocks in a circular
Operating Systems
fashion.
In slide shows or carousel apps, after the last image, it returns to
Image/Slide Viewers
the first.
Polynomials Useful in polynomial addition/multiplication where terms are
Representation stored in a circular linked list.

Advantage of Circular Linked List:

 Efficient Traversal: In CLL, we can start from any node and traverse the entire list
(since it loops back to the start).
 No Null Pointers: Unlike linear linked lists, there is no NULL pointer because the
last node points to the first node.
Useful in Applications Requiring Cyclic Nature: Ideal for round-robin
scheduling, playlists, games, and circular queues.
 Insertion/Deletion at Both Ends: Can easily insert or delete at the beginning, end,
or any position without needing to traverse fully.
 Efficient Memory Utilization: Can repeatedly reuse nodes by traversing circularly
without extra conditions for the end of the list.

Disadvantage of Circular Linked List:

 Complex Implementation: Insertion and deletion require more pointer adjustments
than singly linked lists.
 Difficult Traversal Control: Traversal may go into an infinite loop if not handled
carefully (since it has no NULL end).
 Harder to Debug: Errors like infinite looping or pointer mismanagement are
common and harder to detect.
  Deletion Complexity: Deletion in a Circular Linked List is complex because we
must traverse the list to find and correctly update the previous and last node
pointers, which often takes O(n) time.
 Memory Overhead (for Doubly Circular LL): Circular doubly linked lists require
extra memory for the prev pointer.
 Searching is Still O(n): Even though traversal is circular, searching for an element
still takes linear time.

Common Operation in Circular Linked List:

Operation Description
Traversal (Forward & Visiting all nodes starting from head (forward) or from tail
Backward) (backward).
Create a new node and insert it before the first node (update
Insertion at Beginning
head).
Create a new node and insert it after the last node (update
Insertion at End
tail).
Insert a node at a given index/position (adjust previous and
Insertion at Position
next links).
Remove the first node (update head and previous of next
Deletion from Beginning
node).
Remove the last node (update tail and next of previous
Deletion from End
node).
Remove a node at a given position (relink previous and next
Deletion from Position
nodes).
Search Traverse DLL to find whether a given key/data exists.
Update Traverse DLL and update a node’s data value.
Count Counts the total number of nodes in DLL.
Sort Rearranges nodes in ascending/descending order.

4) Circular Doubly Linked List:

The doubly circular linked list has the features of both the circular linked list and doubly
linked list.
The above figure shows the representation of the doubly circular linked list in which the
last node is attached to the first node and thus creates a circle. It is a doubly linked list also
because each node holds the address of the previous node also. The main difference
between the doubly linked list and doubly circular linked list is that the doubly circular
linked list does not contain the NULL value in the previous field of the node. As the doubly
circular linked contains three parts, i.e., two address parts and one data part so its
representation is similar to the doubly linked list.

Representation of the node in a Circular Doubly linked list

struct node
{
int data;
struct node *next;
struct node *prev;
}

Applications of Circular Doubly linked list:

Application Area Explanation
Supports continuous play — after the last song/video, it loops back
Music/Video Playlist
to the first one. Also allows previous/next navigation.
Browser Tabs / Tabs or history can be traversed forward and backward in a circular
Navigation way.
Round-Robin Used in CPU process scheduling to allocate time slices to processes
Scheduling in a circular order.
Deque Efficient for double-ended queue (deque) where insertion and
Implementation deletion can happen at both ends.
Helps in tracking players in turn-based games, cycling through
Multiplayer Games
players circularly.
Memory
Useful in maintaining circular free list of memory blocks.
Management
Real-Time Used in apps requiring continuous traversal (e.g., carousel/slide
Applications show, image viewer).

Advantages of Circular Doubly Linked List :

 Efficient Traversal: A circular doubly linked list's nodes can be efficiently
traversed in both ways, or forward and backward.
 Insertion and deletion: A circular doubly linked list makes efficient use of
insertion and deletion operations. The head and tail nodes are connected because the
list is circular, making it simple to add or remove nodes from either end.
 Implementation of Circular Data Structures: The implementation of circular data
structures like circular queues and circular buffers makes extensive use of circular
doubly linked lists.

Disadvantages of Circular Doubly Linked List :
 Complexity: Compared to a singly linked list, the circular doubly linked list has
more complicated operations, which can make it more difficult to develop and
maintain.
  Cost of Circularity: In some circumstances, the list's circularity may result in
additional overhead. For instance, it may be challenging to tell whether the traversal
of the list has completely circled the object and returned to its beginning place.
 More Complex to Debug: Circular doubly linked lists can be more difficult to
debug than single-linked lists because the circular nature of the list might introduce
loops that are challenging to find and repair.

Common Operation in Circular Doubly Linked List:

Operation Description

Traversal (Forward & Visit all nodes starting from head in forward or backward direction
Backward) (since it’s circular, traversal can continue indefinitely).

Insert a new node before the head node and update head, previous,
Insertion at Beginning
and next pointers.

Insertion at End Insert a new node after the last node and update circular links.

Insert a node at a specific position (middle) by updating previous

Insertion at Position
and next pointers.

Delete the head node and update the head to the next node, also fix
Deletion at Beginning
circular links.

Delete the last node and update circular pointers to maintain the
Deletion at End
structure.

Remove a node from a specific position, adjusting previous and

Deletion at Position
next pointers.

Search Traverse the CDLL to find whether a given key/data exists.

Update Modify the data part of a specific node.

Count the number of nodes in the list by traversing once through the
Count
circular structure.