DATA STRUCTURE

[BCS-301]

Shyam B. Verma
(Assistant Professor, CSE Department)
 Syllabus
• 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)
 Text Books
• Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J.
Augenstein, “Data Structures Using C and C++”, PHI Learning
Private Limited, Delhi India
• Horowitz and Sahani, “Fundamentals of Data Structures”,
Galgotia Publications Pvt Ltd Delhi India.
• Lipschutz, “Data Structures” Schaum’s Outline Series, Tata
McGraw-hill Education (India) Pvt. Ltd.
• Thareja, “Data Structure Using C” Oxford Higher Education.
 Course Outcomes [CO]
• CO1: Describe the ways arrays, linked lists, stacks, queues, trees,
and graphs are represented in memory, used by the algorithms and
their common applications
• CO2: Understand and implement linear data structures such as
Stack, Queue and Priority Queue.
• CO3: Analyze the computational efficiency of the Sorting and
Searching algorithms.
• CO4: Implementation of Trees and Graphs and perform various
operations on these data structure.
• CO5: Identify the alternative implementations of data structures
with respect to its performance to solve a real world problem.
 Introduction
• Data is a collection of facts and figures or a set of values that can be
recorded.
• Data Structure is a way of collecting and organizing data in such a way
that we can perform operations on these data in an effective way.
• Data Structure is a particular way of storing and organizing data in the
memory of the computer so that these data can easily be retrieved and
efficiently utilized in the future when required.
• The choice of a good data structure makes it possible to perform varieties of
critical operations effectively.
• An efficient data structure also uses minimum memory space and minimum
execution time to process the task. The main goal is to reduce the space
and time complexities of different tasks.
 Why is Data Structure important?
• Data structure is important because it is used in almost every program or
software system.
• Data Structures are necessary for designing efficient algorithms.
• Using appropriate data structures can help programmers save a good
amount of time while performing operations such as storage, retrieval, or
processing of data.
• Manipulation of large amounts of data is easier.
• Data structures can help improve the performance of our code by reducing
the time and space complexity of algorithms.
• Data structures can help you solve complex problems by breaking
them down into smaller, more manageable parts.
• Data structures provide a way to abstract the underlying complexity of a
problem and simplify it, making it easier to understand and solve.
 Basic Types of Data Structures
• As we have discussed above, anything that can store data can be called as
a data structure, hence Integer, Float, Boolean, Char etc, all are data
structures. They are known as Primitive Data Structures.
• Then we also have some complex Data Structures, which are used to store
large and connected data. Some example of Abstract Data
Structure are :
▫ Arrays
▫ Linked List
▫ Tree
▫ Graph
▫ Stack, Queue etc.
• All these data structures allow us to perform different operations on data.
We select these data structures based on which type of operation is
required.
 Characteristic Description
Linear In Linear data structures, the data items are arranged in a linear
sequence and sequential order. Example: Array, Linked List

Non-Linear In Non-Linear data structures, the data items are not in sequence.
Example: Tree, Graph
Homogeneous In homogeneous data structures, all the elements are of same
type. Example: Array
Non- In Non-Homogeneous data structure, the elements may or may
not be of the same type. Example: Structures
Homogeneous
Static Static data structures are those whose sizes and structures
associated memory locations are fixed, at compile time.
Example: Array
Dynamic Dynamic structures are those which expands or shrinks
depending upon the program need and its execution. Also, their
associated memory locations changes. Example: Linked List
created using pointers
 Operations on Data Structure
The major or the common operations that can be performed on the data structures are:
• Traversal: To access each data exactly once.
• Searching: We can search for any element in a data structure.
• Sorting: We can sort the elements of a data structure either in an ascending or
descending order.
• Insert: We can also insert the new element in a data structure.
• Update: We can also update the element, i.e., we can replace the element with another
element.
• Delete: We can also perform the delete operation to remove the element from the data
structure.
 Basic Terminologies
• Data: We can define data as an elementary value or a collection of values. For
example, the Employee's name and ID are the data related to the Employee.
• Data Items: A Single unit of value is known as Data Item.
• Group Items: Data Items that have subordinate data items are known as Group
Items. For example, an employee's name can have a first, middle, and last name.
• Elementary Items: Data Items that are unable to divide into sub-items are known
as Elementary Items. For example, the ID of an Employee.
• Entity and Attribute: A class of certain objects is represented by an Entity. It
consists of different Attributes. Each Attribute symbolizes the specific property of
that Entity.
• Meaningful or processed data is called information. The
collection of data is organized into the hierarchy of fields, records
and files. A single elementary unit of information representing an
attribute of an entity is called a Field.
• Records are the collection of field values of a given entity.
Collection of records of the entities in a given entity set is called
a file. Each record may contain a certain field that uniquely
represents that record. Such a field is called a primary key.
• Based on their length, records may be classified into two. They
are:
▫ Fixed-length record : All record contain the same data items with
the same amount of space assigned to each items.
▫ Variance length record: Records may contain different length
data items.
 What is an Algorithm ?
• An algorithm is any well-defined computational procedure that takes some value, or set of
values, as input and produces some value, or set of values, as output.
• An algorithm is a set of well-defined instructions to solve a particular problem. It takes a set of
input(s) and produces the desired output.
• Properties of an algorithm:
• Input- There should be 0 or more inputs supplied externally to the algorithm.
• Output- There should be at least 1 output obtained.
• Definiteness- Every step of the algorithm should be clear and well defined.
• Finiteness- The algorithm should have finite number of steps.
• Correctness- Every step of the algorithm must generate a correct output.
Characteristics
 Efficiency of an Algorithm
• The efficiency of an algorithm depends on its design,
implementation, resources, and memory required by it for the
computation.
• An algorithm is said to be efficient and fast, if it takes less time to
execute and consumes less memory space. The performance of an
algorithm is measured on the basis of following properties :
• Time Complexity
• Space Complexity
 Space Complexity
• It is the amount of memory space required by the algorithm, during
the course of its execution. Space complexity must be taken seriously
for multi-user systems and in situations where limited memory is
available.
• Auxiliary Space is the extra space or temporary space used by an
algorithm.
• Space Complexity of an algorithm is the total space taken by the
algorithm with respect to the input size. Space complexity includes
both Auxiliary space and space used by input.
• Note: Space complexity depends on a variety of things such as the
programming language, the compiler, or even the machine running
the algorithm.
 Time Complexity
• Time Complexity is a way to represent the amount of time required
by the program to run till its completion.
• It's generally a good practice to try to keep the time required
minimum, so that our algorithm completes it's execution in the
minimum time possible.
• The time complexity of an algorithm depends on the behavior of
input:
▫ Worst-case
▫ Best-case
▫ Average-case
 Best, Average and Worst-case
Analysis of Algorithms
• We all know that the running time of an algorithm increases (or
remains constant) as the input size (n) increases.
• Sometimes even if the size of the input is same, the running time
varies among different instances of the input.
• In that case, we perform best, average and worst-case analysis.
• The best case gives the minimum time, the worst case running time
gives the maximum time and average case running time gives the
time required on average to execute the algorithm.
int LinearSearch(int a, int n, int item) {
int i;
for (i = 0; i < n; i++) {
if (a[i] == item) {
return a[i];
}
}
return -1;
}
Best case happens when the item we are looking for is in the very first
position of the array: Θ(1)
Worst case happens when the item we are searching is in the last position
of the array or the item is not in the array: Θ(n)
Average case analyses all possible inputs and calculate the running time
for all inputs. Add up all the calculated values and divide the sum by the
total number of entries:(1+2+3+…+n+(n+1))/(n+1)
=O(n)
 Example-1
int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + 1;
}
for (j = 0; j < M; j++) {
b = b + 1;
}
• O(N + M) time, O(1) space
• The first loop is O(N) and the second loop is O(M).
Since N and M are independent variables, so we can’t say which one is
the leading term. Therefore Time complexity of the given problem will
be O(N+M).
Since variables size does not depend on the size of the input,
therefore Space Complexity will be constant or O(1).
 Example-2
int i, j, k = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j = j +1) {
k = k + n / 2;
}
}

• Time complexity: O(n2)

• Space complexity: O(1)
 Example-3
int i, j, k = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j = j * 2) {
k = k + j;
}
}

• Time complexity: O(nlogn) & space complexity: O(1)

• If you notice, j keeps doubling till it is less than or
equal to n. We can double a number till it is less than n
requires log2(n) steps.
So, total steps = O(n/ 2 * log2 (n)) = O(n*log2n)
 Example-4
int i;
int j;
int k = 0;
for (i = 1; i <= n; i++) {
printf(“%d”, i);
printf(“%d”, i*i);
for (j = 1; j <= n; j = j +1) {
k = k +i + j;
}
}
• T(n)=n2+2n+3
• Time complexity: O(n2) & space complexity: O(1)
 GATE-CS-2005
double fun (int n)
{
int i;
double sum;
if (n = = 0) return 1.0;
else
{
sum = 0.0;
for (i = 0; i < n; i++)
sum = sum + fun (i);
return sum;
}
}
• Function fun() is recursive. Space complexity is O(n) as there can be
at most O(n) active functions at a time.
 GATE-CS-2004
Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is
a function whose time complexity is θ(m).

counter = 0;
for (i = 1; i < = n; i++)
{
if (A[i] == 1)
counter++;
else {
f(counter);
counter = 0;
}
}
• The complexity of this program fragment is θ(n)
 Asymptotic Notations
• When it comes to analyzing the complexity of any algorithm in
terms of time and space, we can never provide an exact number to
define the time required and the space required by the algorithm,
instead we express it using some standard notations, also known
as Asymptotic Notations.
• When we analyse any algorithm, we generally get a formula to
represent the amount of time required for execution or the time
required by the computer to run the lines of the code, number
of memory accesses, number of comparisons, temporary
variables occupying memory space etc.
• Asymptotic Notations allow us to analyze an algorithm's running
time by identifying its behavior as its input size grows. This is also
referred to as an algorithm's growth rate.
Let us take an example, if some algorithm has a time complexity of
T(n) = (n2 + 3n + 4), which is a quadratic equation. For large values of n, the 3n
+ 4 part will become insignificant compared to the n2 part.
Growth rate of functions
• Logarithmic Function - log n
• Linear Function - an + b
• Quadratic Function - an2 + bn + c
• Polynomial Function - anz + . . . + an2 + an1 + an0, where z is some
constant
• Exponential Function - an, where a is some constant

GATE-CS-2021
Consider the following three functions.
f1=10n
f2=nlogn
f3=n√n
Arranges the functions in the increasing order of asymptotic growth rate:
f2<f3<f1
 AKTU Questions
• Define best case, average case and worst case for analyzing
the complexity of a program. [2022-23] [2 Marks]
• Rank the following typical bounds in increasing order of
growth rate: O(log n), O(n4), O(1), O(n2 log n) [2021-22] [2
Marks]
• Define the following terms: (i) Time complexity (ii) Space
complexity (iii) Asymptotic notation (iv) Big O notation
[2019-20] [10 Marks]
 What is Asymptotic Behavior?
• The word Asymptotic means approaching a value or curve
arbitrarily closely (i.e., as some sort of limit is taken).
• In asymptotic notations, we use the some model to ignore
the constant factors and insignificant parts of an
expression, to device a better way of representing
complexities of algorithms, in a single term, so that
comparison between algorithms can be done easily.
• Let's take an example to understand this:
• If we have two algorithms with the following expressions representing the
time required by them for execution:
• Expression 1: (20n2 + 3n - 4)
• Expression 2: (n3 + 100n - 2)
• Now, as per asymptotic notations, we should just worry about how the
function will grow as the value of n (input) will grow, and that will entirely
depend on n2 for the Expression 1, and on n3 for Expression 2. Hence, we
can clearly say that the algorithm for which running time is represented by
the Expression 2, will grow faster than the other one, simply by analyzing
the highest power coefficient and ignoring the other constants(20 in 20n2)
and insignificant parts of the expression(3n - 4 and 100n - 2).
• The main idea behind casting aside the less important part is to make
things manageable.
• All we need to do is, first analyze the algorithm to find out an expression to
define it's time requirements and then analyse how that expression will
grow as the input (n) will grow.
 Types of Asymptotic Notations
We use three types of asymptotic notations to represent the
growth of any algorithm, as input increases:
▫ Big Theta (Θ)
▫ Big Oh(O)
▫ Big Omega (Ω)
 Upper Bounds: Big-O
• This notation is known as the upper bound of the algorithm, or a
Worst Case of an algorithm.
• It tells us that a certain function will never exceed for any value of
input n at any time.
• Consider Linear Search algorithm, in which we traverse an array
elements, one by one to search a given number.
• In Worst case, starting from the front of the array, we find the
element we are searching for at the end, which will lead to a time
complexity of n, where n represents the number of total elements.
• If the element we are searching for is the first element of the array,
in which case the time complexity will be constant.
• So, the time complexity is O(n) in worst case.
Let f(n) and g(n) are two nonnegative functions indicating the running
time of two algorithms. We say, g(n) is providing an upper bound to f(n)
if there exist some positive constants c and n0 such that
0 ≤ f(n) ≤ c.g(n) for all n ≥ n0. It is denoted as f(n) = Ο(g(n)).
 Lower Bounds: Omega
• Big Omega notation is used to define the lower bound of any
algorithm or we can say the best case of any algorithm.
• This always indicates the minimum time required for any
algorithm for all input values, therefore the best case of any
algorithm.
• In simple words, when we represent a time complexity for any
algorithm in the form of big-Ω, we mean that the algorithm will take
at least this much time to complete it's execution. It can definitely
take more time than this too.
Let f(n) and g(n) are two nonnegative functions indicating the running time of two
algorithms. We say the function g(n) is lower bound of function f(n) if there exist
some positive constants c and n0 such that 0 ≤ c.g(n) ≤ f(n) for all n ≥ n0. It is
denoted as f(n) = Ω (g(n)).
 Tight Bounds: Theta
• When we say tight bounds, we mean that the time complexity
represented by the Big-Θ notation is like the average value or range
within which the actual time of execution of the algorithm will be.
• For example, if for some algorithm the time complexity is
represented by the expression 3n2 + 5n, and we use the Big-Θ
notation to represent this, then the time complexity would be Θ(n2),
ignoring the constant coefficient and removing the insignificant part,
which is 5n.
• Here, in the example above, complexity of Θ(n2) means, that the
average time for any input n will remain in between, c1*n2 and c2*n2,
where c1, c2 are two constants, thereby tightly binding the expression
representing the growth of the algorithm.
Let f(n) and g(n) are two nonnegative functions indicating running time of two
algorithms. We say the function g(n) is tight bound of function f(n) if there exist
some positive constants c1, c2, and n0 such that 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) for all
n ≥ n0. It is denoted as f(n) = Θ (g(n)).
 ISRO CS 2015
int recursive (int n)
{
if(n == 1)
return (1);
else return (recursive (n-1) + recursive (n-1));
}

• The time complexity of the following C function is (assume

n > 0): O(2n)
 Complexity And Space-Time Tradeoff
• An Algorithm is the best which helps to solve a problem that requires
less space in memory and also takes less time to generate the
output. But in general, it is not always possible to achieve both of
these conditions at the same time.
• In computer science, a space-time or time-memory tradeoff is a
way of solving a problem or calculation in less time by using more
storage space (or memory), or by solving a problem in very little
space by spending a long time.
• So, if your problem is taking a long time but not much memory, a
space-time tradeoff would let you use more memory and solve the
problem more quickly. Or, if it could be solved very quickly but
requires more memory than you have, you can try to spend more
time solving the problem in the limited memory.
• Suppose a file of thousands records contains name, SSN and much
addition information. Searching (linear search) a record for a give name
will take much time. Sorting the file by the name and using binary search
will reduce the search time.
• But on the other hand, searching a record by using SSN will again take a
lot time. There are two approaches to solve this problem:
▫ Create a duplicate file and sort the records on the basis of SSN and the
main file is sorted by name. This approach will double the memory
requirement.
▫ Another approach is to sort the main file by SSN and an auxiliary
array with two columns, first column contains sorted name and the
second column contains pointers which give the location of the
corresponding records in the main file.
 Abstract Data Type (ADT)
• The Data Type is basically a type of data that can be used in different
computer program. It signifies the type like integer, float etc, the
space like integer will take 4-bytes, character will take 1-byte of space
etc.
• The abstract datatype is special kind of datatype, whose behavior
is defined by a set of values and set of operations. The keyword
“Abstract” is used as we can use these data types, we can perform
different operations, but how those operations are working that is
totally hidden from the user. The ADT is made of with primitive
data types, but operation logics are hidden.
Abstract data type model
• head(): returns the value of the node present at the front of the list.
• tail(): returns the value of the node present at the back of the list.
• push_front(int val): creates a node with data = val and keeps this node to the front of the
linked list.
• push_back(int val): creates a node with data = val and keeps this node at the back of the
linked list.
• pop_front(): removes the front node from the list.
• pop_back(): removes the last node from the list.
• empty(): returns true if the list is empty, otherwise returns false.
• size(): returns the number of nodes present in the list.
▫ isFull(): This is used to check whether queue is full or not
▫ isEmpry(): This is used to check whether queue is empty or not
▫ enqueue(): Insert an element at the end of the queue.
▫ dequeue(): Remove and return the first element of the queue, if the queue isn't
empty.
▫ delete(): This is used to delete one element from the front end of the queue
▫ size(): this function is used to get number of elements present into the queue
▫ isFull(): This is used to check whether stack is full or not
▫ isEmpry(): This is used to check whether stack is empty or not
▫ push(x): This is used to push x into the stack
▫ pop(): This is used to delete one element from top of the stack
▫ peek(): This is used to get the top most element of the stack
▫ size(): this function is used to get number of elements present into the stack
ARRAY
 Syllabus
• 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.
 Introduction to Arrays
• The simplest and linear type of data structure is a linear (or 1D)
array.
• One way is to have linear relationship between elements by means
of sequential (contiguous) memory locations.
• An array is collection of items stored at contiguous memory
locations. The idea is to store multiple items of same type
(homogenous) together.
• It easier to calculate the location of each element by simply
adding an offset to a base value, i.e., the memory location of the
first element of the array.
• Remember: “Location of next index depends on the data type
we use”.
Arrays can be declared in various ways in different languages. For illustration, let's
take C array declaration.

As per the above illustration, following are the important points to be considered.
1. Index starts with 0.
2. Array length is 10 which means it can store 10 elements.
3. Each element can be accessed via its index. For ex, we can fetch an element at index 6 as 27.
 Calculation of address
• The address of any particular element in the 1-D array can be
calculated by the following equation:
Address of element a[k] = Base address + W*E
• Here, W is the size of each element of the array, and E is the
effective index (E=k-LB) of element we need in the array.
• Example:
We wish to find the address of a 6th element of the 1-dimensional
array ‘a[10]’, whose base address is 1000. The size of each element
in this example is 4 byte. So, the calculation based on this can be
performed in the following way.
Address of element a[6] = 1000+4*6
= 1000+24
= 1024
 Basic Operations
Following are the basic operations supported by an array.
• Traversal − Process all the array elements one by one.
• Insertion − Adds an element at the given index.
• Deletion − Deletes an element at the given index.
• Search − Search an element using the given index or by the
value.
• Update − Updates an element at the given index.
 Traversal of Array
• The method of processing each element in the array exactly
once for a specific purpose is known as Traversal. In array Traversal
starts from first element in the array and ends at the last element of
the array.
• For ex. printing every element, counting the total number of
elements, or performing any process on these elements.
• Time complexity of traversal algorithm is O(n) in all cases.
Algorithm for Array Traversal
Step 1: START = 0
Step 2: Repeat Step-3 while (START<N)
Step 3: Read A[START]
START = START + 1
 Program for Array Traversal
#include<stdio.h>
#define N 5
void traverse(int *A);
int main()
{
int A[N]={10,20,30,40,50};
traverse(A);
}
void traverse(int *A)
{
int START=0;
while(START<N)
{
printf("%d\n“, A[START]);
START=START+1;
}
}
 Insertion in an Array
Following can be a situation with array insertion:
▫ Insertion at the beginning of an array
▫ Insertion at the given index of an array
▫ Insertion after/before the given index of an array
 Insertion at the Beginning of an Array
• When the insertion happens at the beginning, it causes all the
existing data items to shift one step towards right.
• We assume A is an array with N elements. The maximum numbers
of elements it can store is defined by MAX. We shall first check if
an array has any empty space to store any element and then we
proceed with the insertion process. The time complexity is O(n).
Algorithm
1. Begin
2. IF N == MAX
return
3. ELSE N = N + 1
a. For all Elements in A Move to next adjacent location
b. A[FIRST] = New Element
4. End
 Insertion at the given index of an array
• In this scenario, we are given the exact location (index) of an array where a new
data element (value) needs to be inserted. First we shall check if the array is full, if
it is not, then we shall move all data elements from that location to one step towards
right. This will make room for a new data element.
• We assume A is an array with N elements. The maximum numbers of elements it
can store is defined by MAX.
Algorithm
1. Begin
2. IF N == MAX
return
3. ELSE N = N + 1
a. Input index
b. For All Elements from A[index] to A[N], Move to next adjacent location
c. A[index] = New Element
4. End
 Insertion after the given index of an array
• In this scenario we are given a location (index) of an array after which a
new data element (value) has to be inserted. Only the seek process varies,
the rest of the activities are the same as in the previous example.
• We assume A is an array with N elements. The maximum numbers of
elements it can store is defined by MAX.
• Algorithm
1. Begin
2. IF N = MAX
return
3. ELSE
N=N+1
a. Input index
b. For All Elements from A[index + 1] to A[N] Move to next adjacent location
c. A[index + 1] = New Element
3. End
The time complexity of insertion
algorithm in:

Best case: Ω(1)

Worst Case: O(n)
Average Case: θ(n)
 Deletion in Array
• Deletion refers to removing an existing element from the array and
re-organizing all elements of an array.
 Deleting the first element of the array

 Deleting the specified element of the array

The time complexity of deletion
algorithm in:

Best case: Ω(1)

Worst Case: O(n)
Average Case: θ(n)
 Searching in Array
• Not even a single day pass, when we do not have to search for something
in our day to day life, car keys, books, pen, mobile charger and what not.
Same is the life of a computer, there is so much data stored in it, that
whenever a user asks for some data, computer has to search it's memory
to look for the data and make it available to the user. And the computer
has it's own techniques to search through it's memory fast.
• What if you have to write a program to search a given number in an array?
How will you do it?
• Well, to search an element in a given array, there are two popular
algorithms available:
▫ Linear Search
▫ Binary Search
 Linear Search
• Linear search is a very basic and simple search algorithm. In
Linear search, we search an element or value in a given array
by traversing the array from the starting, till the desired
element or value is found.
• It compares the element to be searched with all the elements
present in the array and when the element
is matched successfully, it returns the index of the element
in the array, else it return -1.
• Linear Search is applied on unsorted or unordered lists,
when there are fewer elements in a list.
 Algorithm
• Consider LA is a linear array with N elements and K is a
positive integer such that K<=N. Following is the algorithm to
find an element with a value of ITEM using Linear search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM then GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop
 Features of Linear Search Algorithm
• It is used for unsorted, unordered and small list of elements.
• It has a very simple implementation.

The time complexity of linear search algorithm is:

Best case: Ω(1)
Worst Case: O(n)
Average Case: θ(n)

The time is linearly dependent on the number of elements, which is not bad, but
not that good too.
 Binary Search
• Binary Search is useful when there are large numbers of elements in
an array and they are sorted. So a necessary condition for Binary
search to work is that the list/array should be sorted.

Features of Binary Search

• It is great to search through large sorted arrays.
• It has a simple implementation.
The time complexity of Binary search algorithm is:
Best case: Ω(1)
Worst Case: O(log2 n)
Average Case: θ(log2 n)
 Updating an Array
• Update operation refers to updating an existing element from the
array at a given index. The time complexity will be O(1).
Algorithm
• Consider LA is a linear array with N elements and K is a positive
integer such that K<N. Following is the algorithm to update an
element available at the Kth position of LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop
 Time complexity of Array Operations
Lets take a look at the time complexity of various operations on arrays.
Operation Best Case Worst Case Average Case

Read Ω(1) O(1) ϴ(1)

Insert Ω(1) O(n) ϴ(n)

Delete Ω(1) O(n) ϴ(n)

Linear Search Ω(1) O(n) ϴ(n)

Binary Search Ω(1) O(log n) ϴ(log n)

 ISRO 2018
Which of the following operations is not O(1) for an array of
sorted data. You may assume that array elements are
distinct.
▫ Find the ith largest element
▫ Delete an element
▫ Find the ith smallest element
▫ All of the above

▫ Delete an element
 GATE-CS-2015 (Set 2)
• An unordered array contains n distinct elements. The number of
comparisons to find an element in this list that is neither maximum nor
minimum is:
• Θ(1)
• Θ(nlogn)
• Θ(n)
• Θ(logn)

• Θ(1) We only need to consider any 3 elements and compare them. Using
3 comparisons, we can find that the middle element. So the number of
comparisons is constants, that makes time complexity as Θ(1).
 UGC NET CS 2016 July – III
Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j],
then the pair (i, j) is called an inversion of A. What is the expected
number of inversions in any permutation on n elements ?
▫ n(n-1)/2
▫ n(n-1)/4
▫ n(n+1)/4
▫ 2n[logn]

▫ n(n-1)/4
 GATE CS 2005
• A program P reads in 500 integers in the range
[0..100] representing the scores of 500 students. It then
prints the frequency of each score above 50. What would be
the best way for P to store the frequencies?
▫ An array of 50 numbers
▫ An array of 100 numbers
▫ An array of 500 numbers
▫ A dynamically allocated array of 550 numbers

▫ An array of 50 numbers
 Advantages and disadvantages of Arrays
Advantages
1. Reading an array element is simple and efficient. This is because any
element can be access directly using indexes.
2. Array is a foundation for other data structures. For example other
data structures such as Linked List, Stack, Queue etc. are
implemented using array.
3. All the elements of an array can be accessed using a single name
(array name) along with the index, which is readable, user-friendly
and efficient rather than storing those elements in different-2
variables.
4. All the elements in array are stored at contiguous memory
locations.
Disadvantages
1. While using array, we must need to make the decision of the size of
the array in the beginning (static memory allocation), so if we
are not aware how many elements we are going to store in array, it
would make the task difficult.
2. The size of the array is fixed so if at later point, if we need to store
more elements in it then it can’t be done. On the other hand, if we
store less number of elements than the declared size, the remaining
allocated memory is wasted.
3. Insertion and deletion operations required O(n) shifting of
elements.
 Two dimensional (2D) arrays
• An array of arrays is known as 2D array. The two dimensional (2D) array is also
known as matrix. A matrix can be represented as a table of rows and columns.
• A two-dimensional array is stored in the form of the row-
column matrix, where the first index designates the row and
second index shows the column.
These matrices are stored in the memory as given below.
▫ Row-Major order Implementation
▫ Column-Major order Implementation
 Row-Major order Implementation
• In Row-Major Implementation of the arrays, the arrays are
stored in the memory in terms of the row design, i.e. first the first
row of the array is stored in the memory then second and so on.
Suppose we have an array named arr having 3 rows and 4 columns
then it can be stored in the memory in the following manner:
 Column-Major Implementation
• In Column-Major Implementation of the arrays, the arrays are stored in
the memory in the term of the column design, i.e. the first column of the array is
stored in the memory then the second and so on.
 UGC NET CS 2014 Dec - II
• Consider a two-dimensional array A[20][10]. Assume 4 words per
memory cell, the base address of array A is 100, elements are stored
in row-major order and first element is A[0][0]. What is the address
of A[11][5] ?
▫ 560
▫ 460
▫ 570
▫ 575

▫ 560
 GATE-CS-2014-(Set-3)
Let A be a square matrix of size n x n. What is the expected output of the following program:
C = 100
for i = 1 to n do • The matrix A itself
for j = 1 to n do • Transpose of matrix A
{ • Adding 100 to the upper diagonal elements
Temp = A[i][j] + C and subtracting 100 from diagonal
A[i][j] = A[j][i] elements of A
A[j][i] = Temp - C • None of the above
}
for i = 1 to n do
for j = 1 to n do
Output(A[i][j]);

• The matrix A itself

 Multidimensional Array
• An n-dimensional matrix can be of any dimension. In 1-D array the elements are
linearly arranged and can be addressed as a[0], a[1], .. .
• In 2-D array elements have row and column indexes and can be represented as a[0][0],
a[0][1] etc. and they are stored row-wise/column-wise in the memory, because the
memory is linear.
• A 3-D array is collection of many 2D matrix and can be accessed by 3 index numbers.
Representation in RMO
Representation in CMO
Address Calculation
• Suppose the array is of N-dimensions having the size of each
dimension as L1, L2, L3, ..., Ln
where Li=UB-LB+1
• for a given subscript Ki, the effective index Ei of Li is the no. of
indices preceding Ki
where Ei=Ki-LB
• The element size is w, Base Address is BA and the index number of
the element to find the address is given as K1, K2, K3, . . . .Kn .Then the
formula will be:
• In column-major order
BA+w[(((…(ENLN-1+EN-1)LN-2)+…+E3)L2+E2)L1+E1]
• In row-major order
BA+w[(…((E1L2+E2)L3+E3)L4+…+EN-1)LN+EN]
 AKTU Question
• Suppose a 3-dimensional array A is declared using A[1:10, -5:5, -10:5)
(i) Find the length of each dimension and the number of elements in A
(ii) Explain Row major order and Column Major Order in detail with explanation
formula expression.
(iii) Calculate the address of element A[7,3,4] if base address is 2000 and each element is
taking 2 bytes in memory. [AKTU-2021][10 Marks]

• Suppose multi dimensional arrays P and Q are declared as P(-2:12, 4:22) and
Q(1:9, -5:15, -3:8) stored in column major order.
(i) Find the length of each dimensions of P and Q.
(ii) Find the number of elements in P and Q.
(iii) Assuming base address (Q) =400, W=4, find the effective indices E1, E2 and E3 and
address of element Q[3,3, 3]. [AKTU-2018][10 Marks]
 Applications of Array
• Array stores data elements of the same data type.
• Arrays help to maintain large data under a single variable name. This
avoids the confusion of using multiple variables.
• Arrays can be used for sorting data elements. Different sorting
techniques like the Bubble sort, Insertion sort, Selection sort, etc use
arrays to store and sort elements easily.
• Arrays can be used for performing matrix operations.
• Many databases, small and large, consist of one-dimensional and
two-dimensional arrays whose elements are records.
• Arrays can be used for CPU scheduling.
• Arrays are also used to implement other data structures like Stacks,
Queues, Heaps, Hash tables, etc.
 Sparse Matrix
• If a matrix contains more number of ZERO values than NON-ZERO values. Such
matrix is known as sparse matrix.
Sparse matrix is a matrix which contains very few non-zero elements.
• When a sparse matrix is represented with a 2-dimensional array, we waste a lot
of space to represent that matrix.

Why to use Sparse Matrix instead of simple matrix ?

• Storage: There are lesser non-zero elements than zeros and thus lesser memory
can be used to store only those elements.
• Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements.
 Sparse Matrix Representations
A sparse matrix can be represented by using TWO
representations, those are as follows...
▫ Triplet Representation (Array Representation)
▫ Linked Representation
 Triplet Representation
• In this representation, we consider only non-zero values along with their row and
column index values. In this representation, the 0th row stores the total number
of rows, columns and the number of non-zero values in the sparse matrix.
For example, consider a matrix of size 5 X 6 containing 6 number of non-zero
values. This matrix can be represented as shown in the image:
 Linked Representation
In linked representation, we use a linked list data structure to represent a sparse matrix. In linked
list, each node has four fields. These four fields are defined as:
• Row: Index of row, where non-zero element is located
• Column: Index of column, where non-zero element is located
• Value: Value of the non zero element located at index (row, column)
• Next node: Address of the next node
 Triangular Matrix
There are two types of triangular matrices:
▪ Upper triangular matrix
▪ Lower triangular matrix.
Triangular matrices have the same number of rows as they have
columns; that is, they have n rows and n columns.
S11 S12 S13 S11 0 0

0 S22 S23 S21 S22 0

0 0 S33 S31 S32 S33

 Representation of Lower Triangular Matrix
Total no. of non-zero elements in the matrix:
1+2+3+……….+n = n(n+1)/2
To find the position of A[i][j] in 1-D array:
No. of elements above the ith row:
1+2+3+………+(i-1) = i(i-1)/2
No. of elements before jth column in ith row:
= (j-1)
So, position of a[i][j] in 1-D array is:
= i(i-1)/2 + (j-1) + 1
= i(i-1)/2 + j
 Tri-diagonal Matrix

Representation of tri-diagonal matrix in 1-D array

Total non-zero elements = (n-1) + n + (n-1)
= (3n-2) where n is the dimension of matrix.
Index of (i,j) = [3*(i-2)+2] + [j-i+2]
= 2*i + j - 2
LINKED LIST
 Syllabus
• 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.
 Introduction
• A linked list is a linear data structure, in which the elements are not
stored at contiguous memory locations. The elements in a linked list
are linked using pointers as shown in the below image.
• Linked List can be defined as collection of objects called nodes that
are randomly stored in the memory.
• Each node holds its own data and the address of the next node
hence forming a chain like structure.
 Representation of Linked List
• There are two ways to implement a linked list.
▫ Static implementation (Using Array)
▫ Dynamic implantation (Linked list)
Linked List Implementation using Array
 Linked List Implementation using DMA
• A linked list is a collection of nodes. Each node consists of two part.
▫ Data/Info
▫ Address of next node in the list
• The Head will store the address of first node in the list.
 Types of Linked Lists
There are 3 different implementations of Linked List available, they
are:
▫ Singly Linked List
▫ Circular Linked List
▫ Doubly Linked List
▫ Doubly Circular List
Let's know more about them and how they are different from each
other.
 Basic Operations
Following are the basic operations supported by a list.
• Insertion − Adds an element in the list.
• Deletion − Deletes an element from the list.
• Traversal/Display − Traverse the complete list.
• Search − Searches an element using the given key.
• Sorting- Sort the elements of list in ascending/descending order.

https://visualgo.net/en/list?slide=1
https://cmps-people.ok.ubc.ca/ylucet/DS/Algorithms.html
 Singly Linked List
• Singly linked lists contain nodes which have a data part as well as an
address part i.e. next, which points to the next node in the
sequence of nodes.
• A singly linked list is formed when many such nodes are linked
together to form a chain. Each node points to the next node present
in the order. The first node is always used as a reference to traverse
the list and is called HEAD. The last node points to NULL.
 Declaring a Linked list
In C language, a linked list can be implemented using structure and pointers.
struct LinkedList
{
int data;
struct LinkedList *next;
};
• The above definition is used to create a node in the list. The data field stores the
value and the next is a pointer to store the address of the next node.
• Noticed something unusual with next?
• In place of a data type, struct LinkedList is written before next. That's
because its a self-referencing pointer. It means a pointer that points to
whatever it is a part of. Here next is a part of a node and it will point to the next
node.
 Inserting a node in Singly Linked List
A node can be added in three ways:
1) At the front (beginning) of the linked list
2) At a given position k.
3) At the end of the linked list.
 Insertion at the beginning of the list
• In the first case, we make a new node and points its next to the head
of the existing list and then change the head to the newly added node.
It is similar to picture given below.
• Time complexity of this algorithm is O(1) as it does constant
amount of work.
 Insertion of a node at a given position
• Time complexity of this algorithm is O(n) as n can be any
position.
 Insertion at the end of the linked list
• Time complexity of this algorithm is O(n) where n is the number
of nodes in linked list. Since there is a loop from head to end, the
function does O(n) work.
• This method can also be optimized to work in O(1) by keeping an
extra pointer to tail (end) of the linked list.
 ISRO CS 2014
Consider a single linked list where F and L are pointers to the first and last
elements respectively of the linked list. The time for performing which of the
given operations depends on the length of the linked list?

 Delete the first element of the list

 Interchange the first two elements of the list
 Delete the last element of the list
 Add an element at the end of the list
 Delete the last element of the list
 GATE CS 2020
What is the worst case time complexity of inserting n elements
into an empty linked list, if the linked list needs to be
maintained in sorted order?
▫ Θ(n)
▫ Θ(n log n)
▫ Θ(n2)
▫ Θ(1)
 Deleting a node from the singly linked list
• A node can be deleted in three ways from a singly linked
list:
1) From the front (beginning) of the linked list
2) After a given node.
3) From the end of the linked list.
 Deleting the first node of the linked list
• Time complexity of this algorithm is O(1) as it does constant amount of work.
 Deleting the nth node of the linked list
• To delete a node from linked list, we need to do following steps.
1) Find previous node of the node to be deleted.
2) Change the next of previous node.
3) Free memory for the node to be deleted.
• Time complexity of this algorithm is O(n) where n is the number
of nodes in linked list. Since there is a loop from head to end, the
function does O(n) work.
 Deleting the last node of the linked list
• Time complexity of this algorithm is O(n) where n is the number of
nodes in linked list. Since there is a loop from head to end, the
function does O(n) work.
 Traversing the singly linked list
1. Create a temporary variable for traversing. Assign reference of head
node to it, temp = head.
2. Repeat below step till temp!= NULL.
3. temp->data contains the current node data. You can print it or can
perform some calculation on it.
4. Once done, move to next node using temp = temp->next.
5. Go back to 2nd step.
Time complexity of this algorithm is O(n) where n is the number of
nodes in linked list. Since there is a loop from head to end, the
function does O(n) work.
 GATE-IT-2004
What does the following function do for a given Linked List with first node
as head?
void fun1(struct node* head) {
if(head == NULL) return;
fun1(head->next);
printf("%d ", head->data);
}
▫ Prints all nodes of linked lists
▫ Prints all nodes of linked list in reverse order
▫ Prints alternate nodes of Linked List
▫ Prints alternate nodes in reverse order

▫ Prints all nodes of linked list in reverse order

 Searching an element using the given key
Search an element in linked list is fairly similar to how you search an element in
arrays. Here we will learn to perform linear search on singly linked list.
1. Input element to search from user. Store it in some variable say keyToSearch.
2. Declare two variable one to store index of found element and other to iterate
through list. Say index = 0; and struct node *curNode = head;
3. If curNode is not NULL and its data is not equal to keyToSearch. Then,
increment index and move curNode to its next node.
4. Repeat step 3 till curNode != NULL and element is not found, otherwise move to
5th step.
5. If curNode is not NULL, then element is found hence return index otherwise return
-1.
• Time complexity of this algorithm is O(n) where n is the number of nodes in
linked list. Since there is a loop from head to end, the function does O(n) work.
 GATE CS 2020
Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the
list. What is the worst-case time complexity of the best known algorithm to
delete the node Q from the list?
▫ O(n)
▫ O(log2 n)
▫ O(logn)
▫ O(1)
O(n). Fast solution is to copy the data from the next node to the node to be deleted and delete
the last node.
 UGC NET CS 2016 Aug – II
Consider an implementation of unsorted single linked list. Suppose it has its
representation with a head and a tail pointer (i.e. pointers to the first and last
nodes of the linked list). Given the representation, which of the following
operation can not be implemented in O(1) time ?

▫ Insertion at the front of the linked list.

▫ Insertion at the end of the linked list.
▫ Deletion of the front node of the linked list.
▫ Deletion of the last node of the linked list.

▫ Deletion of the last node of the linked list.

 Doubly Linked List
Doubly linked list is a type of linked list in which each node apart from
storing its data has two pointers. The first link points to the
previous node in the list and the second link points to the next
node in the list. The first node of the list has its previous link
pointing to NULL similarly the last node of the list has its next node
pointing to NULL.
 XOR List Representation of DLL
• A memory-efficient version of Doubly Linked List that can be created using only one
space for the address field with every node.
• The List uses bitwise XOR operation to save space for one address. In the XOR linked
list, instead of storing actual memory addresses, every node stores the XOR of
addresses of previous and next nodes.

• To find the address of next node = XOR(prev, curr -> next);

 Basic Operations
Following are the basic operations supported by a list.
• Insertion − Adds an element at the beginning of the list.
• Deletion − Deletes an element at the beginning of the list.
• Insert Last − Adds an element at the end of the list.
• Delete Last − Deletes an element from the end of the list.
• Insert After − Adds an element after an item of the list.
• Delete − Deletes an element from the list using the key.
• Display forward − Displays the complete list in a forward
manner.
• Display backward − Displays the complete list in a backward
manner
 Insert a node at the front
Algorithm
Step 1 - Create a newNode with given value and newNode → prev as NULL.
Step 2 - Check whether list is Empty (head == NULL)
a) newNode → next=NULL
b) head=newNode.
Step 3 - If it is not Empty then,
a) newNode → next=head
b) head=newNode
Algorithm Inserting at the end of the list
Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty, then assign NULL to newNode →
previous and newNode to head.
Step 4 - If it is not Empty, then, define a node pointer temp and initialize
with head.
Step 5 - Keep moving the temp to its next node until it reaches to the last node in
the list (until temp → next is equal to NULL).
Step 6 - Assign newNode to temp → next and temp to newNode →
previous.
Inserting At Specific location in the list (After a Node)
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, assign NULL to both newNode → previous & newNode →
next and set newNode to head.
Step 4 - If it is not Empty then, define two node pointers temp1 & temp2 and
initialize temp1 with head.
Step 5 - Keep moving the temp1 to its next node until it reaches to the node after which we want to
insert the newNode (until temp1 → data is equal to location, here location is the node value
after which we want to insert the newNode).
Step 6 - Every time check whether temp1 is reached to the last node. If it is reached to the last node
then display 'Given node is not found in the list!!! Insertion not possible!!!' and
terminate the function. Otherwise move the temp1 to next node.
Step 7 - Assign temp1 → next to temp2, newNode to temp1 → next, temp1 to newNode →
previous, temp2 to newNode → next and newNode to temp2 → previous.
 ISRO CS 2017 - May
• In a doubly linked list, the number of pointers affected for an
insertion operation will be:
▫ 4
▫ 0
▫ 2
▫ 1
ISRO CS 2008
Which of the following operations is performed more efficiently by
doubly linked list than by linear linked list?
 Deleting a node whose location is given
 Searching an unsorted list for a given item
 Inserting a node after the node with a given location
 Traversing the list to process each node
 Deletion Operations in Doubly Linked List
In a double linked list, the deletion operation can be performed in
three ways as follows...
• Deleting from Beginning of the list
• Deleting from End of the list
• Deleting a Specific Node
 Deletion from Beginning of the list
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
Step 3 - If it is not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4 - Check whether list is having only one node (temp → previous is equal to temp → next)
Step 5 - If it is TRUE, then set head to NULL and delete temp (Setting Empty list conditions)
Step 6 - If it is FALSE, then assign temp → next to head, NULL to head → previous and
delete temp.
 Deleting a Specific Node from the list
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and terminate
the function.
Step 3 - If it is not Empty, then define a Node pointer 'temp' and initialize with head.
Step 4 - Keep moving the temp until it reaches to the exact node to be deleted or to the last node.
Step 5 - If it is reached to the last node, then display 'Given node not found in the list!
Deletion not possible!!!' and terminate the fuction.
 Deletion from End of the list
• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty, then display 'List is Empty!!! Deletion is not possible' and
terminate the function.
• Step 3 - If it is not Empty then, define a Node pointer 'temp' and initialize with head.
• Step 4 - Check whether list has only one Node (temp → previous and temp → next both
are NULL)
• Step 5 - If it is TRUE, then assign NULL to head and delete temp. And terminate from the
function. (Setting Empty list condition)
• Step 6 - If it is FALSE, then keep moving temp until it reaches to the last node in the list.
(until temp → next is equal to NULL)
• Step 7 - Assign NULL to temp → previous → next and delete temp.
 Traversing a Double Linked List
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty, then display 'List is Empty!!!' and terminate
the function.
Step 3 - If it is not Empty, then define a Node pointer 'temp' and
initialize with head.
Step 4 - Display 'NULL <--- '.
Step 5 - Keep displaying temp → data with an arrow (<===>)
until temp reaches to the last node
Step 6 - Finally, display temp → data with arrow pointing
to NULL (temp → data ---> NULL).
 ISRO CS 2018
• A doubly linked list is declared as
struct Node {
int Value;
struct Node *Fwd;
struct Node *Bwd;
};
Which of the following segments of code deletes the node pointed to by X
from the doubly linked list, if it is assumed that X points to neither the
first nor the last node of the list?
▫ X->Bwd->Fwd = X->Fwd; X->Fwd->Bwd = X->Bwd ;
▫ X->Bwd.Fwd = X->Fwd ; X.Fwd->Bwd = X->Bwd ;
▫ X.Bwd->Fwd = X.Bwd ; X->Fwd.Bwd = X.Bwd ;
▫ X->Bwd->Fwd = X->Bwd ; X->Fwd->Bwd = X->Fwd;
 Advantages over singly linked list
1) A DLL can be traversed in both forward and backward
direction.
2) The delete operation in DLL is more efficient if pointer to
the node to be deleted is given.
3) We can quickly insert a new node before a given node.
In singly linked list, to delete a node, pointer to the previous
node is needed. To get this previous node, sometimes the
list is traversed. In DLL, we can get the previous node using
previous pointer.
 Disadvantages over singly linked list
1) Every node of DLL Require extra space for a previous
pointer. It is also possible to implement DLL with single
pointer (using XOR representation) though.

2) All operations require an extra pointer previous to be

maintained. For example, in insertion, we need to modify
previous pointers together with next pointers. For example,
in following functions for insertions at different positions, we
need 1 or 2 extra steps to set previous pointer.
 Circular Linked List
• In single linked list, every node points to its next node in the sequence and the
last node points NULL. But in circular linked list, every node points to its next
node in the sequence but the last node points to the first node in the list.
• A circular linked list is a sequence of elements in which every element
has a link to its next element in the sequence and the last element has
a link to the first element.
• That means circular linked list is similar to the single linked list except that the
last node points to the first node in the list.
 Advantages of Circular Linked Lists
1) Any node can be a starting point. We can traverse the whole list by starting from any
point. We just need to stop when the first visited node is visited again.
2) Useful for implementation of queue. Unlike this implementation, we don’t need to
maintain two pointers for front and rear if we use circular linked list. We can maintain
a pointer to the last inserted node and front can always be obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example,
when multiple applications are running on a PC, it is common for the operating system
to put the running applications on a list and then to cycle through them, giving each of
them a slice of time to execute, and then making them wait while the CPU is given to
another application. It is convenient for the operating system to use a circular list so
that when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures
like Fibonacci Heap.
 Operations
In a circular linked list, we perform the following
operations...
• Insertion
• Deletion
• Display
 Insertion
In a circular linked list, the insertion operation can be
performed in three ways. They are as follows...
• Inserting At Beginning of the list
• Inserting At End of the list
• Inserting At Specific location in the list
 Inserting At Beginning of the list
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set head = newNode and newNode→next = head .
Step 4 - If it is Not Empty then, define a Node pointer 'temp' and initialize with 'head'.
Step 5 - Keep moving the 'temp' to its next node until it reaches to the last node (until 'temp →
next == head').
Step 6 - Set 'newNode → next =head', 'head = newNode' and 'temp → next = head'.
 Inserting At End of the list
Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode and newNode → next = head.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next == head).
Step 6 - Set temp → next = newNode and newNode → next = head.
Inserting At Specific location in the list
 Deletion Operations
In a circular linked list, the deletion operation can be
performed in three ways those are as follows...
• Deleting from Beginning of the list
• Deleting from End of the list
• Deleting a Specific Node
 Deleting from Beginning of the list
• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
• Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and
'temp2' and initialize both 'temp1' and 'temp2' with head.
• Step 4 - Check whether list is having only one node (temp1 →
next == head)
• Step 5 - If it is TRUE then set head = NULL and
delete temp1 (Setting Empty list conditions)
• Step 6 - If it is FALSE move the temp1 until it reaches to the last node.
(until temp1 → next == head )
• Step 7 - Then set head = temp2 → next, temp1 → next = head and
delete temp2
 Deleting from End of the list
• Step 1 - Check whether list is Empty (head == NULL)
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
• Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and
'temp2' and initialize 'temp1' with head.
• Step 4 - Check whether list has only one Node (temp1 → next == head)
• Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And
terminate from the function. (Setting Empty list condition)
• Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to
its next node. Repeat the same until temp1 reaches to the last node in the
list. (until temp1 → next == head)
• Step 7 - Set temp2 → next = head and delete temp1.
Deleting a Specific Node from the list
 Displaying a circular Linked List
Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty, then display 'List is Empty!!!' and terminate
the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and
initialize with head.
Step 4 - Keep displaying temp → data with an arrow (--->)
until temp reaches to the last node
Step 5 - Finally display temp → data with arrow pointing to head →
data.
 GATE 2004
• A circularly linked list is used to represent a Queue. A single variable p is
used to access the Queue. To which node should p point such that both the
operations enQueue and deQueue can be performed in constant time?

▫ rear node
▫ front node
▫ not possible with a single pointer
▫ node next to front
 Polynomial Representation
A polynomial p(x) is the expression in variable x which is in the form (axn + bxn-1 +
…. + jx+ k), where a, b, c …., k fall in the category of real numbers and 'n' is non
negative integer, which is called the degree of polynomial.An essential
characteristic of the polynomial is that each term in the polynomial expression
consists of two parts:
• Coefficient
• Exponent
 Representation of Polynomial
Polynomial can be represented in the various ways. These are:
• By the use of arrays
• By the use of Linked List
Representation of Polynomial Using Arrays
 Addition of Two Polynomial
• For adding two polynomials using arrays is straightforward
method, since both the arrays may be added up element
wise beginning from 0 to n-1, resulting in addition of two
polynomials.
• Addition of two polynomials using linked list requires
comparing the exponents, and wherever the exponents are
found to be same, the coefficients are added up.
• For terms with different exponents, the complete term is
simply added to the result thereby making it a part of
addition result.
 Multiplication of Two Polynomial
• Multiplication of two polynomials however requires
manipulation of each node such that the exponents are
added up and the coefficients are multiplied.
• After each term of first polynomial is operated upon with
each term of the second polynomial, then the result has to be
added up by comparing the exponents and adding the
coefficients for similar exponents and including terms as
such with dissimilar exponents in the result.
Representation of Polynomial Using Linked List
To understand this concept better let's first brush up all the basic contents
that are required.
• linked list is a data structure that stores each element as an object in a
node of the list. every note contains two parts data and links to the next
node.
• Polynomial is a mathematical expression that consists of variables and
coefficients. for example x^2 - 4x + 7
• In the Polynomial linked list, the coefficients and exponents of the
polynomial are defined as the data node of the list.
• For adding two polynomials that are stored as a linked list. We need to
add the coefficients of variables with the same power. In a linked list node
contains 3 members, coefficient value link to the next node. A linked list
that is used to store Polynomial looks like − 4x7 + 12x2 + 45
Addition of two polynomials using Linked list
• Adding two polynomials that are represented by a linked list.
We check values at the exponent value of the node. For the
same values of exponent, we will add the coefficients.
• Example,
Input :p1= 13x8 + 7x5 + 32x2 + 54p2= 3x12 + 17x5 + 3x3 + 98
Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152
Multiplication of two polynomials using Linked list
 Two Variables Polynomial
• Polynomials in two variables are algebraic expressions consisting of
terms in the form axnym . The degree of each term in a polynomial in
two variables is the sum of the exponents in each term and
the degree of the polynomial is the largest such sum.
• Here are some examples of polynomials in two variables and their
degrees.
x2y−6x3y12+10x2−7y+1 degree : 15
6x4+8y4−xy2 degree : 4
x4y2−x3y3−xy+x4 degree : 6
6x14−10y3+3x−11y degree : 14
 Advantages of Linked Lists
• They are dynamic in nature i.e it allocates the memory when
required.
• The list is not required to be contiguously present in the
memory. The node can reside any where in the memory and
linked together to make a list. This achieves optimized
utilization of space.
• List size is limited to the memory size and doesn't need to be
declared in advance.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily implemented.
 Disadvantages of Linked Lists
• The memory is wasted as pointers require extra memory
for storage.
• No element can be accessed randomly; it has to access
each node sequentially.
• Not cache friendly. Since array elements are contiguous
locations, there is locality of reference which is not there in
case of linked lists.
• Reverse Traversing is difficult in linked list.
 Applications of Linked Lists
• Linked lists are used to implement stacks, queues, graphs, etc.
• Polynomial representation
• Representation of sparse matrices
• Symbol table creation in compiler
• Mailing list
• Memory management
• Linked lists let you insert elements at the beginning and end of the
list.
• In Linked Lists we don't need to know the size in advance.