Data Structure

A data structure is a storage that is used to store and organize data. It is a way of
arranging data on a computer so that it can be accessed and updated efficiently.
A data structure is not only used for organizing the data. It is also used for
processing, retrieving, and storing data.

Classification of Data Structure

 Linear data structure: Data structure in which data elements are

arranged sequentially or linearly, where each element is attached to
its previous and next adjacent elements, is called a linear data
structure.
Examples of linear data structures are array, stack, queue, linked list, etc.
 Static data structure: Static data structure has a fixed memory
size. It is easier to access the elements in a static data
structure.
An example of this data structure is an array.
 Dynamic data structure: In dynamic data structure, the size is not
fixed. It can be randomly updated during the runtime which may
be considered efficient concerning the memory (space)
complexity of the code.
Examples of this data structure are queue, stack, etc.
 Non-linear data structure: Data structures where data elements are not
placed sequentially or linearly are called non-linear data structures.
In a non-linear data structure, we can’t traverse all the elements in a
single run only.
Examples of non-linear data structures are trees and graphs.
Algorithm
An algorithm is a well-defined sequential computational technique that
accepts a value or a collection of values as input and produces the
output(s) needed to solve a problem.
Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have
the following characteristics −
 Unambiguous − Algorithm should be clear and unambiguous. Each
of its steps (or phases), and their inputs/outputs should be clear
and must lead to only one meaning.
 Input − An algorithm should have 0 or more well-defined inputs.
 Output − An algorithm should have 1 or more well-defined outputs,
and should match the desired output.
 Finiteness − Algorithms must terminate after a finite number of
steps.
 Feasibility − Should be feasible with the available resources.
 Independent − An algorithm should have step-by-step directions,
which should be independent of any programming code.

Complexities of an Algorithm
The complexity of an algorithm computes the amount of time and spaces
required by an algorithm for an input of size (n). The complexity of an
algorithm can be divided into two types. The time complexity and
the space complexity.
Time complexity
The time complexity of an algorithm is a measure of how much time it
takes to run as a function of the input size.
Space complexity
The space complexity of an algorithm is a measure of how much memory
it needs to run as a function of the input size.
Asymptotic Notation and Analysis
In Asymptotic Analysis, we evaluate the performance of an algorithm
in terms of input size (we don’t measure the actual running time). We
calculate, how the time (or space) taken by an algorithm increases with
the input size.

Asymptotic notation is a way to describe the running time or space

complexity of an algorithm based on the input size. It is commonly used
in complexity analysis to describe how an algorithm performs as the size
of the input grows. The three most commonly used notations are Big O,
Omega, and Theta.
1. Big O notation (O): This notation provides an upper bound on the
growth rate of an algorithm’s running time or space usage. It
represents the worst-case scenario, i.e., the maximum amount of time
or space an algorithm may need to solve a problem. For example, if
an algorithm’s running time is O(n), then it means that the running
time of the algorithm increases linearly with the input size n or less.

Big-O notation represents the upper bound of the running time of an

algorithm. Therefore, it gives the worst-case complexity of an
algorithm.

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.
The execution time serves as an upper bound on the algorithm’s
time complexity.
Mathematical Representation of Big-O Notation:
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n)
≤ cg(n) for all n ≥ n0 }

2. Omega notation (Ω): This notation provides a lower bound on the

growth rate of an algorithm’s running time or space usage. It
represents the best-case scenario, i.e., the minimum amount of time
or space an algorithm may need to solve a problem. For example, if
an algorithm’s running time is Ω(n), then it means that the running time
of the algorithm increases linearly with the input size n or more.

Omega notation represents the lower bound of the running time of an

algorithm. Thus, it provides the best case complexity of an algorithm.

The execution time serves as a lower bound on the algorithm’s time

complexity.
It is defined as the condition that allows an algorithm to complete
statement execution in the shortest amount of time.
Let g and f be the function from the set of natural numbers to itself. The
function f is said to be Ω(g), if there is a constant c > 0 and a natural
number n0 such that c*g(n) ≤ f(n) for all n ≥ n0

Mathematical Representation of Omega notation :

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n)
≤ f(n) for all n ≥ n0 }
3. Theta notation (Θ): This notation provides both an upper and lower
bound on the growth rate of an algorithm’s running time or space
usage. It represents the average-case scenario, i.e., the amount of
time or space an algorithm typically needs to solve a problem. For
example, if an algorithm’s running time is Θ(n), then it means that the
running time of the algorithm increases linearly with the input size n.

Theta notation encloses the function from above and below. Since it
represents the upper and the lower bound of the running time of an
algorithm, it is used for analyzing the average-case complexity of an
algorithm.

Let g and f be the function from the set of natural numbers to itself. The
function f is said to be Θ(g), 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

Mathematical Representation of Theta notation:

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤
c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0}
Array Data Structure
Array is a linear data structure that is a collection of similar data types.
Arrays are stored in contiguous memory locations. It is a static data
structure with a fixed size. It combines data of similar types.
Following are the important terms to understand the concept of Array.
 Element − Each item stored in an array is called an element.
 Index − Each location of an element in an array has a numerical
index, which is used to identify the element.

Types of Array operations:

 Traversal: Traverse through the elements of an array.
 Insertion: Inserting a new element in an array.
 Deletion: Deleting element from the array.
 Searching: Search for an element in the array.
 Sorting: Maintaining the order of elements in the array.

Applications of Array Data Structure:

Below are some applications of arrays.
 Storing and accessing data: Arrays are used to store and retrieve
data in a specific order. For example, an array can be used to store
the scores of a group of students, or the temperatures recorded by a
weather station. 
 Sorting: Arrays can be used to sort data in ascending or descending
order. Sorting algorithms such as bubble sort, merge sort, and
quicksort rely heavily on arrays.
 Searching: Arrays can be searched for specific elements using
algorithms such as linear search and binary search.
 Matrices: Arrays are used to represent matrices in mathematical
computations such as matrix multiplication, linear algebra, and image
processing.
 Stacks and queues: Arrays are used as the underlying data structure
for implementing stacks and queues, which are commonly used in
algorithms and data structures.
 Graphs: Arrays can be used to represent graphs in computer science.
Each element in the array represents a node in the graph, and the
relationships between the nodes are represented by the values stored
in the array.
 Dynamic programming: Dynamic programming algorithms often use
arrays to store intermediate results of subproblems in order to solve a
larger problem.

Advantages of array data structure:

 Efficient access to elements: Arrays provide direct and efficient
access to any element in the collection. Accessing an element in an
array is an O(1) operation, meaning that the time required to access
an element is constant and does not depend on the size of the array.
 Fast data retrieval: Arrays allow for fast data retrieval because the
data is stored in contiguous memory locations. This means that the
data can be accessed quickly and efficiently without the need for
complex data structures or algorithms.
 Memory efficiency: Arrays are a memory-efficient way of storing
data. Because the elements of an array are stored in contiguous
memory locations, the size of the array is known at compile time. This
means that memory can be allocated for the entire array in one block,
reducing memory fragmentation.
 Easy to implement: Arrays are easy to implement and understand,
making them an ideal choice for beginners learning computer
programming.

Disadvantages of array data structure:

 Fixed size: Arrays have a fixed size that is determined at the time of
creation. This means that if the size of the array needs to be
increased, a new array must be created and the data must be copied
from the old array to the new array, which can be time-consuming and
memory-intensive.
 Memory allocation issues: Allocating a large array can be
problematic, particularly in systems with limited memory. If the size of
the array is too large, the system may run out of memory, which can
cause the program to crash.
 Insertion and deletion issues: Inserting or deleting an element from
an array can be inefficient and time-consuming because all the
elements after the insertion or deletion point must be shifted to
accommodate the change.
 Wasted space: If an array is not fully populated, there can be wasted
space in the memory allocated for the array. This can be a concern if
memory is limited.
 Limited data type support: Arrays have limited support for complex
data types such as objects and structures, as the elements of an array
must all be of the same data type.
Advantages of Structure over Array:
 The structure can store different types of data whereas an array can
only store similar data types.
 Structure does not have limited size like an array.
 Structure elements may or may not be stored in contiguous locations
but array elements are stored in contiguous locations.
 In structures, object instantiation is possible whereas in arrays objects
are not possible.

Array representation
Address of A[I] = B + W * (I – LB)
I = Subset of element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LB = Lower Limit/Lower Bound of subscript(If not specified assume zero).

To find the address of any element in a 2-Dimensional array there are

the following two ways-
1. Row Major Order
2. Column Major Order
1. Row Major Order:
Row major ordering assigns successive elements, moving across the
rows and then down the next row, to successive memory locations. In
simple language, the elements of an array are stored in a Row-Wise
fashion.
To find the address of the element using row-major order uses the
following formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
 B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume
it as zero),
LC = Lower Limit of column/start column index of the matrix(If not given
assume it as zero),
N = Number of column given in the matrix.
2. Column Major Order:
If elements of an array are stored in a column-major fashion means
moving across the column and then to the next column then it’s in
column-major order. To find the address of the element using column-
major order use the following formula:
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))

I = Row Subset of an element whose address to be found,

J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume it as
zero),
LC = Lower Limit of column/start column index of matrix(If not given
assume it as zero),
M = Number of rows given in the matrix.

Applications of Array
1. Storing Data: Arrays are widely used to store collections of data elements of the same type,
such as integers, characters, or floating-point numbers.
2. Representing Strings: Arrays are often used to represent strings in programming languages,
where each element of the array corresponds to a character in the string.
3. Implementing Lists: Arrays can be used to implement list data structures like stacks and
queues. For example, in a stack, elements are added and removed from one end of the array.
4. Matrices and Multi-dimensional Arrays: Arrays can represent matrices and multi-
dimensional data structures, making them suitable for applications like image processing,
graphics, and scientific computing.
5. Sorting and Searching Algorithms: Arrays play a fundamental role in sorting and searching
algorithms such as bubble sort, quicksort, merge sort, linear search, and binary search.
6. Buffers and Caches: In computer systems, arrays are used as buffers and caches to store
data temporarily, facilitating efficient data processing and I/O operations.
7. Hash Tables: Arrays are used as the underlying data structure for hash tables, where each
element in the array represents a bucket that can store multiple key-value pairs.
8. Sparse Arrays: Sparse arrays, where most of the elements are empty or zero, are used in
applications like representing large matrices with mostly zero values efficiently.
Linked List
A Linked List is a linear data structure which looks like a chain of nodes,
where each node is a different element. Unlike Arrays, Linked List
elements are not stored at a contiguous location. They include a series of
connected nodes. Here, each node stores the data and the address of
the next node.

It is basically chains of nodes, each node contains information such

as data and a pointer to the next node in the chain. In the linked list
there is a head pointer, which points to the first element of the linked list,
and if the list is empty then it simply points to null or nothing.

Why linked list data structure needed?

Here are a few advantages of a linked list that is listed below, it will help
you understand why it is necessary to know.
 Dynamic Data structure: The size of memory can be allocated or de-
allocated at run time based on the operation insertion or deletion.
 Ease of Insertion/Deletion: The insertion and deletion of elements
are simpler than arrays since no elements need to be shifted after
insertion and deletion, Just the address needed to be updated.
 Efficient Memory Utilization: As we know Linked List is a dynamic
data structure the size increases or decreases as per the requirement
so this avoids the wastage of memory.
 Implementation: Various advanced data structures can be
implemented using a linked list like a stack, queue, graph, hash maps,
etc.

Advantages of Linked Lists over arrays:

 Dynamic Array.
 Ease of Insertion/Deletion.
 Insertion at the beginning is a constant time operation and takes O(1)
time, as compared to arrays where inserting an element at the
 beginning takes O(n) time,where n is the number of elements in the
array.
Types Of Linked List:

1. Singly Linked List

It is the simplest type of linked list in which every node contains some
data and a pointer to the next node of the same data type.
The node contains a pointer to the next node means that the node stores
the address of the next node in the sequence. A single linked list allows
the traversal of data only in one way. Below is the image for the same:

2.Doubly Linked List

A doubly linked list or a two-way linked list is a more complex type of
linked list that contains a pointer to the next as well as the previous node
in sequence.
Therefore, it contains three parts of data, a pointer to the next node, and
a pointer to the previous node. This would enable us to traverse the list in
the backward direction as well. Below is the image for the same:

3. Circular Linked List

A circular linked list is that in which the last node contains the pointer to
the first node of the list.
While traversing a circular linked list, we can begin at any node and
traverse the list in any direction forward and backward until we reach the
same node we started. Thus, a circular linked list has no beginning and
no end. Below is the image for the same:

Basic operations on Linked Lists:

 Deletion
 Insertion
 Search
 Display

The following operations are performed on a Single Linked List

 Insertion: The insertion operation can be performed in three ways.
They are as follows…
 Inserting At the Beginning of the list
 Inserting At End of the list
 Inserting At Specific location in the list
 Deletion: The deletion operation can be performed in three ways.
They are as follows…
 Deleting from the Beginning of the list
 Deleting from the End of the list
 Deleting a Specific Node
 Search: It is a process of determining and retrieving a specific node
either from the front, the end or anywhere in the list.
 Display: This process displays the elements of a Single-linked list.
Inserting At the Beginning of the list

Algorithm insertAtBeginning(list, data):

1. Create a new node with the given data

2. Set the next pointer of the new node to the current head of the list

3. Set the head of the list to the new node

4. Return the updated list

Inserting At End of the list

Algorithm insertAtLast(list, data):

1. Create a new node with the given data

2. If the list is empty, make the new node the head of the list and return

3. Initialize a pointer variable to the head of the list

4. Traverse the list with the pointer variable until you reach the last
node

5. Set the next pointer of the last node to the new node

6. Return the updated list

Inserting At Specific location in the list

Algorithm insertAtPosition(list, data, position):

1. Create a new node with the given data

2. If the position is 1, make the new node the head of the list and
return

3. Initialize a pointer variable to the head of the list

4. Traverse the list with the pointer variable until you reach the node
just before the insertion point

5. Set the next pointer of the new node to the next node of the pointer
variable

6. Set the next pointer of the pointer variable to the new node

7. Return the updated list

Deleting from the Beginning of the list

Algorithm deleteFromBeginning(list):

1. If the list is empty, return null

2. Set a pointer variable to the head of the list

3. Set the head of the list to the next node of the pointer variable

4. Free the memory occupied by the pointer variable

5. Return the updated list

Deleting from the End of the list

Algorithm deleteFromEnd(list):
1. If the list is empty, return null
2. If the list contains only one node, set the head of the list to null
3. Set a pointer variable to the head of the list
4. Traverse the list until the pointer variable points to the second-
last node
5. Set the next pointer of the second-last node to null
6. Free the memory occupied by the last node
7. Return the updated list

Deleting a Specific Node

Algorithm deleteSpecificNode(list, value):

1. If the list is empty, return null
2. If the node to be deleted is the head node, set the head of the
list to the next node
3. Set a pointer variable to the head of the list
4. Traverse the list until the pointer variable points to the node to
be deleted
5. Set the next pointer of the previous node to the next node of
the node to be deleted
6. Free the memory occupied by the node to be deleted
7. Return the updated list
Search Operation in Linked List

Algorithm searchNode(list, value):

1. Set a pointer variable to the head of the list

2. Traverse the list until the pointer variable points to the node
with the given value or until the end of the list is reached

3. If the node with the given value is found, return the node

4. If the end of the list is reached without finding the node, return
null

Polynomial Representation using Linked List

A polynomial is a collection of different terms, each comprising coefficients, and

exponents. It can be represented using a linked list. This representation makes
polynomial manipulation efficient.

While representing a polynomial using a linked list, each polynomial term

represents a node in the linked list. To get better efficiency in processing, we
assume that the term of every polynomial is stored within the linked list in the
order of decreasing exponents. Also, no two terms have the same exponent, and
no term has a zero coefficient and without coefficients. The coefficient takes a
value of 1.

Each node of a linked list representing polynomial constitute three parts:

 The first part contains the value of the coefficient of the term.
  The second part contains the value of the exponent.
 The third part, LINK points to the next term (next node).

The structure of a node of a linked list that represents a polynomial is shown below:

Consider a polynomial P(x) = 7x4 + 15x3 - 2 x2 + 9. Here 7, 15, -2, and 9 are the coefficients,
and 4,3,2,0 are the exponents of the terms in the polynomial. On representing this
polynomial using a linked list, we have

Addition of Polynomials:
Let us consider an example an example to show how the addition of two
polynomials is performed,

P(x) = 3x4 + 2x3 - 4 x2 + 7

Q (x) = 5x3 + 4 x2 - 5

These polynomials are represented using a linked list in order of decreasing

exponents as follows:
To generate a new linked list for the resulting polynomials that is formed on the
addition of given polynomials P(x) and Q(x), we perform the following steps,

1. Traverse the two lists P and Q and examine all the nodes.
2. We compare the exponents of the corresponding terms of two
polynomials. The first term of polynomials P and Q contain exponents 4
and 3, respectively. Since the exponent of the first term of the polynomial P
is greater than the other polynomial Q, the term having a larger exponent
is inserted into the new list. The new list initially looks as shown below:

3. We then compare the exponent of the next term of the list P with the
exponents of the present term of list Q. Since the two exponents are equal,
so their coefficients are added and appended to the new list as follows:

4. Then we move to the next term of P and Q lists and compare their
exponents. Since exponents of both these terms are equal and after
 addition of their coefficients, we get 0, so the term is dropped, and no
node is appended to the new list after this,

5. Moving to the next term of the two lists, P and Q, we find that the
corresponding terms have the same exponents equal to 0. We add their
coefficients and append them to the new list for the resulting polynomial
as shown below:

Adding two polynomials Algorithm

1. Define Node Structure: Define a node structure for the linked list, where each
node contains two fields: coefficient and exponent.
2. Initialize Pointers: Initialize pointers ptrA and ptrB to the heads of the linked
lists representing polynomials A and B, respectively.
3. Traverse: Loop through both linked lists simultaneously until both are
exhausted.
 If ptrA points to a node with a higher exponent than ptrB, append a
new node with the same coefficient and exponent to the result linked list.
 If ptrB points to a node with a higher exponent than ptrA, append a
new node with the same coefficient and exponent to the result linked list.
 If both ptrA and ptrB point to nodes with the same exponent, add their
coefficients and append a new node with the sum coefficient and the
same exponent to the result linked list.
4. Append Remaining Terms: If any of the linked lists have remaining terms after
the loop, append their nodes to the result linked list.
5. Output: The result linked list contains the sum of the two polynomials.