Introduction of Data

Structures and Algorithms

Dr. Ankit Soni
Introduction to Data Structure
 Outline
 Data Management concepts
 Data types
• Primitive
• Non-primitive
 Types of Data Structures
• Linear Data Structures
• Non Linear Data Structures
 Performance Analysis and Measurement
 Time analysis of algorithms
 Space analysis of algorithms
What is Data?
 Data is the basic fact or entity that is utilized in calculation or manipulation.
 There are two different types of data Numeric data and Alphanumeric data.
 When a programmer collects such type of data for processing, he would require to
store them in computer’s main memory.
 The process of storing data items in computer’s main memory is called representation.
 Data to be processed must be organized in a particular fashion, these organization
leads to structuring of data, and hence the mission to study the Data Structures.
What is Data Structure?..
 Data Structure is a representation of the logical relationship existing between
individual elements of data.
 In other words, a data structure is a way of organizing all data items that considers
not only the elements stored but also their relationship to each other.
 We can also define data structure as a mathematical or logical model of a particular
organization of data items.
 Data Structure mainly specifies the following four things
 Organization of Data
 Accessing Methods
 Degree of Associativity
 Processing alternatives for information
What is Data Structure?..
 The representation of a particular data structure in the memory of a computer is
called Storage Structure.
 The storage structure representation in auxiliary memory is called as File Structure.

Algorithm Data Structure Program

Classification of Data Structure
Data Structure

Primitive Data Structure Non-Primitive Data Structure

Integer Characters Arrays Lists Files

Floating Pointers
Point Linear Non-linear
List List

Stack Queue Graphs Trees

Classification of Data Structure
Primitive / Non-primitive data structures
 Primitive data structures
 Primitive data structures are basic structures and are directly operated upon by machine
instructions.
 Integers, floats, character and pointers are examples of primitive data structures.

 Non primitive data structure

 These are derived from primitive data structures.
 The non-primitive data structures emphasize on structuring of a group of homogeneous or
heterogeneous data items.
 Examples of Non-primitive data type are Array, List, and File.
Non primitive Data Structure
 Array: An array is a fixed-size sequenced collection of elements of the same data type.
 List: An ordered set containing variable number of elements is called as Lists.
 File: A file is a collection of logically related information. It can be viewed as a large list
of records consisting of various fields.

Array

File
List
Linear / Non-Linear data structure
 Linear data structures
 A data structure is said to be Linear, if its elements are connected in linear fashion by means of
logically or in sequence memory locations.
 Examples of Linear Data Structure are Stack and Queue.

 Nonlinear data structures

 Nonlinear data structures are those data structure in which data items are not arranged in a
sequence.
 Examples of Non-linear Data Structure are Tree and Graph.

Stack Queue Tree Graph

Operations of Data Structure
 Create: It results in reserving memory for program elements.
 Destroy: It destroys memory space allocated for specified data structure.
 Selection: It deals with accessing a particular data within a data structure.
 Updation: It updates or modifies the data in the data structure.
 Searching: It finds the presence of desired data item in the list of data items.
 Sorting: It is a process of arranging all data items in a data structure in a particular
order.
 Merging: It is a process of combining the data items of two different sorted list into a
single sorted list.
 Splitting: It is a process of partitioning single list to multiple list.
 Traversal: It is a process of visiting each and every node of a list in systematic manner.
Difference Between Linear and Non-linear Data Structures
Introduction of Algorithm
 In real life, problem solving is done with help of data structures and
algorithms.
 An algorithm is the step-by-step unambiguous instructions to solve a given problem which are
implemented in form of methods or functions or routines in programming. To get a problem solved we
not only want algorithm, but also an efficient algorithm. One criteria of efficiency is time taken by the
algorithm, another could be the memory it takes at run time.

 Sometimes, we can have more than one algorithm for the same problem to process a data structure, and
we have to choose the best one among available algorithms for example, a sorting problem has many
algorithms, like insertion sort, selection sort, quick sort and many more . This is done by algorithm
analysis.

“The best algorithm is the one which has a fine balance between time taken and
memory consumption.”
Introduction of Algorithm
Algorithm analysis helps us to determine which algorithm is most efficient in terms of
time and space consumed.

But what to give more priority if needed to

compromise with one ????
We generally give more priority to the time taken by the algorithm on memory
consumption. As memory is getting cheaper and computers have more memory today
than previous time, therefore, run time analysis becomes more significant than memory.
ABSTRACT DATA TYPE (ADT)

• In order to simplify the process of complex problem solving, user defined data types are used,
which are the combination of data structures with their operations, and we call this Abstract Data
Type or ADT.
• Most commonly used ADTs are : Linked Lists, Array, Stacks, Queues, Priority Queues, Trees etc.
 Outline
Looping
 Array
• Representation of arrays
• One dimensional array
• Two dimensional array
 Applications of arrays
• Symbol Manipulation (matrix representation of polynomial
equation)
• Sparse matrix
 Sparse matrix and its representation
What is an Array?

 What is an array?
 First and most basic data structure, once array is created one memory block
is blocked. Elements of array are accessed in constant time using index value
of the array.
• Why constant time for accessing array element?
One Dimensional Array
 Simplest data structure that makes use of computed address to locate its elements is
the one-dimensional array or vector.
 Number of memory locations is sequentially allocated to the vector.
 A vector size is fixed and therefore requires a fixed number of memory locations.
 Vector A with subscript lower bound of “one” is represented as below….
L0 • L0 is the address of the first word allocated to the first element of vector A
i-1 • C words is size of each element or node
• The address of element Ai is
L0+(i-1)C
Loc(Ai) = L0 + (C*(i-1))
A[i] • Let’s consider the more general case of a vector A with lower bound for it’s
subscript is given by some variable b.
• The address of element Ai is
Loc(Ai) = L0 + (C*(i-b))
Example:
 Example: Address Calculation for a Vector
 Given:
1. Base Address (L0): 1000 (assume in memory
units).
2. Size of Each Element (C): 4 words.
3. Lower Bound of Subscript (b): 3.
 Find: The address of the element A6 Loc(A6)=1000+(4⋅(6−3)) = 1012
Two Dimensional Array
 Two dimensional arrays are also called table or matrix
 Two dimensional arrays have two subscripts
 Column major order matrix: Two dimensional array in which elements are stored
column by column is called as column major matrix
 Two dimensional array consisting of two rows and four columns is stored sequentially
by columns : A[1,1], A[2,1],A[1,2], A[2,2], A[1,3],A[2,3], A[1,4], A[2,4]

Col-1 Col-2 Col-3 Col-4

Row 1 [1,1] [1,2] [1,3] [1,4]

Row 2 [2,1] [2,2] [2,3] [2,4]

Column major order matrix
Col-1 Col-2 Col-3 Col-4
Row 1 [1,1] [1,2] [1,3] [1,4]

Row 2 [2,1] [2,2] [2,3] [2,4]

 The address of element A [ i , j ] can be obtained by expression

Loc (A [ i , j ]) = L0 + (j-1)*2 + (i-1)
Loc (A [2, 3]) = L0 + (3-1)*2 + (2-1) = L0 + 5
 In general for two dimensional array consisting of n rows and m columns the address
element A [ i , j ] is given by
Loc (A [ i , j ]) = L0 + (j-1)*n + (i – 1)
Row major order matrix
 Row major order matrix: Two dimensional array in which elements are stored row by
row is called as row major matrix
b2 u2 n = no of rows, m = no of columns
b1 [1,1] [1,2] [1,3] [1,m]
b1 = lower bound subscript of row
[2,1] [2,2] [2,3] [2,m] u1 = upper bound subscript of row
n = u1 – b1 + 1

b2 = lower bound subscript of column

u1 [n,1] [n,2] [n,3] [n,m] u2 = upper bound subscript of column
nxm m = u2 – b2 + 1

• The address element A [ i , j ] is given by

Loc (A [ i , j ]) = L0 + (i-1)*m + (j – 1)
Applications of Array
1. Symbol Manipulation (matrix representation of polynomial equation)
2. Sparse Matrix

 Matrix representation of polynomial equation

 We can use array for different kind of operations in polynomial equation such as addition,
subtraction, division, differentiation etc…
 We are interested in finding suitable representation for polynomial so that different operations like
addition, subtraction etc… can be performed in efficient manner.
 Array can be used to represent Polynomial equation.
Representation of Polynomial equation
Y Y2 Y3 Y4
X XY XY2 XY3 XY4
X2 X3Y X2Y2 X2Y3 X2Y4
X3 X3Y X3Y2 X3Y3 X3Y4
X4 X4Y X4Y2 X4Y3 X4Y4

2X2 + 5XY + Y2 X2 + 3XY + Y2+Y-X

Y Y2 Y3 Y4 Y Y2 Y3 Y4
0 0 01 0 0 0 1
0 01 0 0
X 0 05 0 0 0 X -1
0 30 0 0 0
X2 20 0 0 0 0 X2 10 0 0 0 0
X3 0 0 0 0 0 X3 0 0 0 0 0
X4 0 0 0 0 0 X4 0 0 0 0 0
Sparse matrix
 An m x n matrix is said to be sparse if “many” of its elements are zero.
 A matrix that is not sparse is called a dense matrix.
 We can device a simple representation scheme whose space requirement equals the
size of the non-zero elements.
Column - 8
Column - 3

Column - 5

Column - 7
Column - 6
Column - 4
Column - 1
Column - 2

Row - 1 0 0 0 2 0 0 1 0 Terms 0 1 2 3 4 5 6 7 8
Row 1 1 2 2 2 3 3 4 4
Row - 2 0 6 0 0 7 0 0 3
Column 4 7 2 5 8 4 6 2 3
Row - 3 0 0 0 9 0 8 0 0 Value 2 1 6 7 3 9 8 4 5
Row - 4 0 4 5 0 0 0 0 0
Linear Representation of given matrix
4x8
Sparse matrix Cont…
 To construct matrix structure from liner representation we need to record.
 Original row and columns of each non zero entries.
 Number of rows and columns in the matrix.

 So each element of the array into which the sparse matrix is mapped need to have three
fields: row, column and value
Sparse matrix Cont…
1 2 3 4 5 6 7
Linear representation of Matrix
1 0 0 6 0 9 0 0
Row Column A
2 2 0 0 7 8 0 4
1 3 6
A= 3 10 0 0 0 0 0 0
4 0 0 12 0 0 0 0 1 5 9
5 0 0 0 0 0 0 0 2 1 2
6 0 0 0 3 0 0 5 2 4 7
6x7
2 5 8
Memory Space required to store 4
2 7
6x7 matrix
3 1 10
42 x 4 = 168 bytes
4 3 12
6 4 3
Memory Space required to store
6 7 5
Linear Representation

(10 + 10 +10 ) x 4 = 120 Space Saved = 168– 120 = 48 bytes

bytes
Sparse matrix Cont…
Linear Representation of Matrix Linear Representation of Matrix
Row Column A Column A
1 3 6 1 3 6
1 5 9 2 5 9
Row
2 1 2 3 1 2
1 1
2 4 7 4 4 7
2 3
2 5 8 5 5 8
3 7
2 7 4 6 7 4
4 8
3 1 10 7 1 10
5 0
4 3 12 8 3 12
6 9
6 4 3 9 4 3
6 7 5 10 7 5

Memory Space required to store Liner Representation = 26 x 4 = 104 bytes

Sparse matrix Cont…
 Memory Savings:
• Storing a dense matrix would waste a lot of memory in this case because most of the
matrix elements are zero.
• By using a sparse matrix, you save 40 bytes (100 bytes - 60 bytes), which is 40% of the
memory, despite representing the same data.
 Computational Efficiency:
• When performing matrix operations (like multiplication, solving linear equations, etc.),
operations on zero elements can be skipped entirely in the sparse matrix
representation, making computations faster.
• For instance, if you're multiplying matrices, you only multiply the non-zero elements,
rather than iterating through every single element, which would include many
unnecessary zero multiplications in the dense format.
THANK YOU
 Array & Strings

Dr. Ankit Soni

Need of Arrays
 Suppose we need to store rollno of the student in the integer variable.

Declaration
int rollno;

 Now we need to store rollno of 100 students.

Declaration
int rollno101, rollno102, rollno103, rollno104...;

 This is not appropriate to declare these many integer variables.

e.g. 100 integer variables for rollno.
 Solution to declare and store multiple variables of similar type is an array.
 An array is a variable that can store multiple values.
Definition of Array

 An array is a fixed size sequential collection of elements of same data type grouped under
single variable name.

[0] [1] [2] … [99]

int rollno[100];

Fixed Size Sequential Same Data type Single Name

Here, the size of an array It is indexed to 0 to 99 in All the elements (0-99) All the elements (0-99)
is 100 (fixed) to store sequence will be integer variables will be referred as a
rollno common name rollno
Declaration of Array

Syntax  By default array index starts with

data-type variable-name[size]; 0.
 If we declare an array of size 5
Integer Array [0] [1] [2] [3] [4] then its index ranges from 0 to
int mark[5]; 4.
 First element will be store at
integer
mark[0] and last element will
be stored at mark[4] not
Float Array [0] [1] [2] [3] [4]
mark[5].
float avg[5];
 Like integer and float array we
float can declare array of type char.
Initialing and Accessing an Array

Declaring, initializing and accessing single integer variable

int mark=90; //variable mark is initialized with value 90
printf("%d",mark); //mark value printed

Declaring, initializing and accessing integer array variable

int mark[5]={85,75,76,55,45}; //mark is initialized with 5 values
printf("%d",mark[0]); //prints 85
printf("%d",mark[1]); //prints 75
printf("%d",mark[2]); //prints 65
printf("%d",mark[3]); //prints 55
printf("%d",mark[4]); //prints 45

[0] [1] [2] [3] [4]

mark[5] 85 75 65 55 45
Read(Scan) Array Elements
Reading array without loop Reading array using loop
1 void main() 1 void main()
2 { 2 {
3 int mark[5]; 3 int mark[5],i;
printf("Enter array element="); for(i=0;i<5;i++)
4 4
scanf("%d",&mark[0]); {
5 printf("Enter array element="); 5 printf("Enter array element=");
6 scanf("%d",&mark[1]); 6 scanf("%d",&mark[i]);
7 printf("Enter array element="); 7 }
8 scanf("%d",&mark[2]); 8 for(i=0;i<5;i++)
9 printf("Enter array element="); 9 {
10 scanf("%d",&mark[3]); 10 printf("%d",mark[i]);
11 printf("Enter array element="); 11 }
scanf("%d",&mark[4]);
12 12 }
13 printf("%d",mark[0]);
14 printf("%d",mark[1]);
15 printf("%d",mark[2]);
16 printf("%d",mark[3]); [0] [1] [2] [3] [4]
17 printf("%d",mark[4]); mark[5] 85 75 65 55 45
18 }
Develop a program to read n numbers in an array and print them in reverse
order.
Program
1 void main()
2 { Output
3 int num[100],n,i; Enter number of array
4 printf("Enter number of array elements="); elements=5
5 scanf("%d",&n); Enter array element=1
6 //loop will scan n elements only Enter array element=2
7 for(i=0;i<n;i++) Enter array element=3
8 { Enter array element=4
9 printf("Enter array element="); Enter array element=5
10 scanf("%d",&num[i]); 5
11 } 4
12 //negative loop to print array in reverse order 3
13 for(i=n-1;i>=0;i--) 2
14 { 1
15 printf("%d\n",num[i]);
16 }
17 }
Multi Dimensional Array
Declaring 2 Dimensional Array

Syntax  A two dimensional array can be

data-type variable-name[x][y]; seen as a table with ‘x’ rows
and ‘y’ columns.
Declaration
int data[3][3]; //This array can hold 9 elements  The row number ranges from 0
to (x-1) and column number
ranges from 0 to (y-1).
int data[3][3];
Column-0 Column-1 Column-2

Row-0 data[0][0] data[0][1] data[0][2]

Row-1 data[1][0] data[1][1] data[1][2]

Row-2 data[2][0] data[2][1] data[2][2]

Initialing and Accessing a 2D Array: Example-1
Program
1 int data[3][3] = {
2 {1,2,3}, //row 0 with 3 elements
3 {4,5,6}, //row 1 with 3 elements
4 {7,8,9} //row 2 with 3 elements
5 }; Column-0 Column-1 Column-2
6 printf("%d",data[0][0]); //1
7 printf("%d",data[0][1]); //2 Row-0 1 2 3
8 printf("%d\n",data[0][2]); //3
9 Row-1 4 5 6
10 printf("%d",data[1][0]); //4
11 printf("%d",data[1][1]); //5 Row-2 7 8 9
12 printf("%d\n",data[1][2]); //6
13
14 printf("%d",data[2][0]);//7
15 printf("%d",data[2][1]); //8
16 printf("%d",data[2][2]); //9
1 // data[3][3] can be initialized like this also
2 int data[3][3]={{1,2,3},{4,5,6},{7,8,9}};
Read(Scan) 2D Array Elements Column-0 Column-1 Column-2

Program Row-0 1 2 3
1 void main(){ Row-1 4 5 6
2 int data[3][3],i,j;
3 for(i=0;i<3;i++) Row-2 7 8 9
4 {
5 for(j=0;j<3;j++)
6 { Output
7 printf("Enter array element="); Enter array element=1
8 scanf("%d",&data[i][j]); Enter array element=2
9 } Enter array element=3
10 } Enter array element=4
11 for(i=0;i<3;i++) Enter array element=5
12 { Enter array element=6
13 for(j=0;j<3;j++) Enter array element=7
14 { Enter array element=8
15 printf("%d",data[i][j]); Enter array element=9
16 } 123
17 printf("\n"); 456
18 } 789
19 }
Definition: String

 A String is a one-dimensional array of characters terminated by a null('\0').

[0] [1] [2] … [9]

char name[10];

 Each character in the array occupies one byte of memory, and the last character must always
be null('\0').
 The termination character ('\0') is important in a string to identify where the string ends.
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
name[10] T H A P A R \0
Declaring & Initializing String

Declaration
char name[10];

Initialization method 1:
char name[10]={‘T',’H',’A',’P',’A',’R','\0'};

Initialization method 2:
char name[10]=“THAPAR";
//'\0' will be automatically inserted at the end in this type of declaration.

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
name[10] T H A P A R \0
Read String: scanf()
Program
Output
1 void main()
2 { Enter name: Thapar
3 char name[10]; Name=Thapar
4 printf("Enter name:"); Output
5 scanf("%s",name);
Enter name: ECE Thapar
6 printf("Name=%s",name);
Name=ECE
7 }

 There is no need to use address of (&) operator in scanf to store a string.

 As string name is an array of characters and the name of the array, i.e., name indicates the
base address of the string (character array).
 scanf() terminates its input on the first whitespace(space, tab, newline etc.) encountered.
Read String: gets()
Program
1 #include<stdio.h> Output
2 void main() Enter name:THAPAR Institute
3 { Name=THAPAR Institute
4 char name[10];
5 printf("Enter name:");
6 gets(name); //read string including white spaces
7 printf("Name=%s",name);
8 }

 gets(): Reads characters from the standard input and stores them as a string.
 puts(): Prints characters from the standard.
 scanf(): Reads input until it encounters whitespace, newline or End Of File(EOF)
whereas gets() reads input until it encounters newline or End Of File(EOF).
 gets(): Does not stop reading input when it encounters whitespace instead it takes
whitespace as a string.
Format specifiers in C
Format
Data Type Size (Bytes) Example
Specifier
%c char 1 'A'
%s char[] (string) Varies (depends on Hello (6 bytes including \0)
string length)
%f float 4 3.14
%e float (scientific 4 1.23e+04
notation)
%lf double 8 3.141592654
 References and
Memory Address

Dr. Ankit Soni

Records
Outline:

Records (in C++) is similar to Structure in C language.

Is a user defined datatype.

used to store data items of different kinds.

Basic difference between C and C++
 Access Specifiers:
 In C, all members of a struct are public by default.
 In C++, members are also public by default in a struct, but C++ structures can have access
specifiers (public, private, and protected), just like classes.
 Object-Oriented Features:
 In C++, structures can have member functions, constructors, destructors, and even inheritance,
making them similar to classes.
 In C, struct is purely a data container.
 Default Access Control:
 In struct (C++), the default access specifier is public.
 In class (C++), the default access specifier is private.
Example of struct in C++
struct Record { int main() {
int id; Record rec(1, “Hello");
string name; rec.display(); // Output: ID: 1, Name: Hello
Record(int i, string n) { return 0;
id = i; }
name = n;
}
void display() {
cout << "ID: " << id << ", Name: " << name << endl;
}
};
Example of struct in C
#include <stdio.h> int main() {
#include <string.h> struct Record rec;
rec.id = 1;
// Struct definition strcpy(rec.name, “Hello");
struct Record {
int id; printf("ID: %d, Name: %s\n", rec.id, rec.name);
char name[50]; // Output: ID: 1, Name: Hello
}; return 0;
}
Example of String
 It is group of characters (including spaces).
 Is a 1-D array of characters.
 String is supported by most of the programming languages viz. C, C++ etc.
Operation with string
 strcpy(string1, string2): Copies the content of string2 into string1.
 strcat(string1, string2): Appends string2 to the end of string1.
 strlen(string1): Returns the length of string1 (excluding the null terminator).
 strcmp(string1, string2): Compares string1 with string2. Returns:
 0 if the strings are equal.
 A negative value if string1 is lexicographically smaller than string2.
 A positive value if string1 is lexicographically greater than string2.

 strchr(string1, ch): Searches for the first occurrence of character ch in string1. Returns a
pointer to the character if found, otherwise returns nullptr.
 strstr(string1, string2): Searches for the first occurrence of the substring string2 in string1.
Returns a pointer to the substring if found, otherwise returns nullptr.
Example
// Declaring C-style strings
char string1[100] = "Hello";
char string2[] = "World";
1. strcpy(string1, string2); cout << "After strcpy: " << string1 << endl;
2. strcat(string1, " ");
strcat(string1, string2); cout << "After strcat: " << string1 << endl;
3. strlen(string1);
4. strcmp(string1, string2);
5. strchr(string1, 'o’);
1. After strcpy: World
6. strstr(string1, "lo"); 2. After strcat: World World
3. Length of string1: 11
4. string1 is greater than string2.
5. First occurrence of 'o' in string1: o World
6. Substring 'lo' found in string1: lo World
Basic C++ code for string
#include <iostream> void display() {
cout << "Name: " << name << endl;
#include <string>
cout << "Email: " << email << endl;
using namespace std; }
class Person { };
int main() {
private: Person person;
string name; // Taking input from user
person.getInput();
string email; // Displaying the entered details
public: person.display();
return 0;
void getInput() { }
cout << "Enter name: ";
getline(cin, name); Output:
cout << "Enter email: "; Enter name: Ankit Soni
Enter email: ankit12@gmail.com
getline(cin, email); Name: Ankit Soni
} Email: ankit12@gmail.com
C++ REFERENCES
 we have read that C++ supports two types of variables:
 An ordinary variable is a variable that contains the value of some type. For example, we create
a variable of type int, which means that the variable can hold the value of type integer.
 A pointer is a variable that stores the address of another variable. It can be dereferenced to
retrieve the value to which this pointer points to.
 There is another variable that C++ supports, i.e., references. It is a variable that behaves as an
alias for another variable.
HOW TO CREATE A REFERENCE?
 Reference can be created by simply using an ampersand (&) operator. When we create a
variable, then it occupies some memory location. We can create a reference of the variable;
therefore, we can access the original variable by using either name of the variable or reference.
For example,
int a=10;
 Now, we create the reference variable of the above variable.
int &ref=a;
 The above statement means that 'ref' is a reference variable of 'a', i.e., we can use the 'ref'
variable in place of 'a' variable.
A Reference Must Be Initialized
#include <iostream>
using namespace std;
int main() {
int num = 10;
int &ref;
cout << "Original value: " << num << endl;
cout << "Reference value: " << ref << endl;
return 0;
}

Output:
Error
References to non-const values
#include <iostream>
using namespace std;
int main() {
int num = 10;
int &ref = num; // Creating a reference to num
cout << "Original value: " << num << endl;
cout << "Reference value: " << ref << endl;
return 0;
}

Output:
Original value: 10
Reference value: 10
References to non-const values
#include <iostream>
using namespace std;
int main() {
int num = 10;
int &ref1 = num; // Creating a reference1 to num
int &ref2 = ref1; // Creating a reference2 to num
int &ref3 = ref2; // Creating a reference3 to num
cout << "Original value: " << num << endl;
cout << "Reference value1: " << ref1 << endl; Output:
cout << "Reference value2: " << ref2 << endl; Original value: 10
cout << "Reference value3: " << ref3 << endl; Reference value1: 10
return 0; Reference value2: 10
} Reference value3: 10
A Reference Cannot Be Null
#include <iostream>
using namespace std;
int main() {
int num = 10;
int &ref = nullptr;
cout << "Original value: " << num << endl;
cout << "Reference value: " << ref << endl;
return 0;
}

Output:
Error
A Reference pointer Can Be Null
#include <iostream>
using namespace std;
int main() {
int num = 10;
int *ref = nullptr;
cout << "Original value: " << num << endl;
cout << "Reference value: " << ref << endl;
return 0;
}

Output:
10
0
A Reference Cannot Be Reassigned
#include <iostream>
using namespace std;
int main() {
int a = 10, b = 20;
int &ref = a; Output:
ref = b; Error
ref = &b;
cout << "Original value-a: " << a << endl;
cout << "Original value-b: " << b << endl;
cout << "reference value-ref:" << a << endl;
return 0;
}
A Reference Is Just an Alias
#include <iostream>
using namespace std;
int main() {
int a = 10, b = 20;
int &ref = a; Output:
ref = b; Original value-a: 20
cout << "Original value-a: " << a << endl;
Original value-b: 20
reference value-ref:20
cout << "Original value-b: " << b << endl;
cout << "reference value-ref:" << a << endl;
return 0;
}
A Reference Cannot Be Declared Without a Type
int main() {
int x = 10; double y = 20.5;
int &ref1 = x;
double &ref2 = y;
int &ref3 = y; Output:
cout << "x: " << x << endl; Error
cout << "y: " << y << endl;
cout << "ref1:" << ref1 << endl;
cout << "ref2:" << ref2 << endl;
cout << "ref3:" << ref3 << endl;
return 0;
}
A Reference Is Just an Alias
int main() {
int x = 10; double y = 20.5;
int &ref1 = x;
double &ref2 = y;
double &ref3 = y; Output:
cout << "x: " << x << endl; x: 10
cout << "y: " << y << endl;
y: 20.5
ref1:10
cout << "ref1:" << ref1 << endl;
ref2:20.5
cout << "ref2:" << ref2 << endl;
ref3:20.5
cout << "ref3:" << ref3 << endl;
return 0;
}
Reference variable
 You cannot create a reference to an array directly, but you can reference individual elements
int arr[3] = {1, 2, 3};
int &ref = arr[0]; // Correct: Refers to the first element of the array

 Use in Function Parameters

void increment(int &x) {
x++;
}
int a = 10;
increment(a); // a becomes 11
Memory Address
Memory Address
#include <iostream>
using namespace std;
int main() {
int x = 10;
cout << "Address of x: " << &x << endl;
return 0; Output:
Address of x: 0x7ffee59c2a3c
}
Pointers Hold Memory Addresses
#include <iostream>
using namespace std;
int main() {
int x = 20;
int *ptr = &x; // Pointer holds the address of x
cout << "Address of x: " << ptr << endl;
cout << "Value of x using pointer: " << *ptr << endl; Output:
Address of x: 0x7ffee59c2a3c
return 0; Value of x using pointer: 20
}
References Have the Same Address as the Variable They Alias
#include <iostream>
using namespace std;
int main() {
int x = 30;
int &ref = x;
cout << "Address of x: " << &x << endl;
cout << "Address of ref: " << &ref << endl; Output:
Address of x: 0x7ffee59c2a3c
return 0; Address of ref: 0x7ffee59c2a3c
}
Arrays and Addresses
#include <iostream>
using namespace std;
int main() {
int arr[3] = {1, 2, 3};
cout << "Address of arr: " << arr << endl;
cout << "Address of arr[0]: " << &arr[0] << endl;
cout << "Address of arr[1]: " << &arr[1] << endl; Output:
Address of arr: 0x7ffee59c2a3c
return 0; Address of arr[0]: 0x7ffee59c2a3c
Address of arr[1]: 0x7ffee59c2a40
}
Dynamically Allocated Variables Have Unique Addresses
#include <iostream>
using namespace std;
int main() {
int *ptr = new int(50);
cout << "Address of dynamically allocated variable: " << ptr << endl;
cout << "Value of dynamically allocated variable: " << *ptr << endl;
delete ptr; // Free memory
return 0;
}
Output:
Address of dynamically allocated variable: 0x600001e2c040
Value of dynamically allocated variable: 50
Pointer Arithmetic Works With Contiguous Memory
#include <iostream>
using namespace std;
int main() {
int arr[3] = {10, 20, 30};
int *ptr = arr;
cout << "Address of arr[0]: " << ptr << endl;
Output:
cout << "Address of arr[1]: " << (ptr + 1) << endl; Address of arr[0]: 0x7ffee59c2a3c
return 0; Address of arr[1]: 0x7ffee59c2a40

}
Nullptr Represents a Null Address
#include <iostream>
using namespace std;
int main() {
int *ptr = nullptr; // Pointer is null
if (ptr == nullptr)
cout << "Pointer is null." << endl;
return 0; Output:
Pointer is null.
}
Void Pointers Can Store Any Address
#include <iostream>
using namespace std;
int main() {
int x = 100;
void *ptr = &x; // Void pointer holding address of x
cout << "Address stored in void pointer: " << ptr << endl;
cout << "Value of x (using typecasting): " << *(int *)ptr << endl;
return 0;
}
Output:
Address stored in void pointer: 0x7ffee59c2a3c
Value of x (using typecasting): 100
Linked List
Why Linked lists ?

Array:
?
1) Static size
2) Expensive to Insertion or deletion of New elements in array.

So what are the advantage of linked lists over array

1) Dynamic size
2) Ease of insertion/deletion
Drawbacks
 While linked lists are powerful, they also have disadvantages:
• Extra Memory: Each node in a linked list requires additional memory for storing the pointer to
the next node.
• Sequential Access: Accessing an element in a linked list requires traversing the list from the
head, whereas arrays allow direct access by index.
• Cache Performance: Arrays provide better cache locality since elements are stored
contiguously in memory, improving performance in certain scenarios.
Linked Storage Representation
 There are many applications where sequential allocation method is unacceptable because of
following characteristics
 Unpredictable storage requirement
 Extensive manipulation of stored data

 One method of obtaining the address of node is to store address in computer’s main memory,
we refer this addressing mode as pointer of link addressing.
 A simple way to represent a linear list is to expand each node to contain a link or pointer to the
next node. This representation is called one-way chain or Singly Linked Linear List.
Linked Storage Representation
NULL
Last Node Value
A 1000 B 2050 C 3335 D
5000 1000 2050 3335
A linked List
 The linked allocation method of storage can result in both efficient use of computer storage
and computer time.
 A linked list is a non-sequential collection of data items.
 Each node is divided into two parts, the first part represents the information of the element and the second
part contains the address of the next mode.
 The last node of the list does not have successor node, so null value is stored as the address.
 It is possible for a list to have no nodes at all, such a list is called empty list.
Pros & Cons of Linked Allocation
 Insertion Operation
 We have an n elements in list and it is required to insert a new element between the first and second element,
what to do with sequential allocation & linked allocation?
 Insertion operation is more efficient in Linked allocation.

A 1000 B 2050 C 3335 D

5000 1000 2050 3335

A 2100 B 2050 C 3335 D

5000 1000 2050 3335

X 1000
2100
Pros & Cons of Linked Allocation
 Deletion Operation
 Deletion operation is more efficient in Linked Allocation

A 1000 B 2050 C 3335 D

5000 1000 2050 3335

A 2050 B 2050 C 3335 D

5000 1000 2050 3335
Pros & Cons of Linked Allocation
 Search Operation
 If particular node in the list is required, it is necessary to follow links from the first node onwards until the
desired node is found, in this situation it is more time consuming to go through linked list than a sequential
list.
 Search operation is more time consuming in Linked Allocation.

 Join Operation
 Join operation is more efficient in Linked Allocation.

A 1000 B 2050 C 3335 D 5050

5000 1000 2050 3335

12 580 52 5096 15 5145 100

5050 580 5096 5145
Pros & Cons of Linked Allocation
 Split Operation
 Split operation is more efficient in Linked Allocation

A 1000 B 2050 C 3335 D

5000 1000 2050 3335

A 1000 B 2050 C 3335 D

5000 1000 2050 3335

 Linked list require more memory compared to array because along with value it stores pointer
to next node.
 Linked lists are among the simplest and most common data structures. They can be used to
implement other data structures like stacks, queues, and symbolic expressions, etc…
Operations & Type of Linked List
Operations on Linked List Types of Linked List
 Insert  Singly Linked List
• Insert at first position  Circular Linked List
• Insert at last position  Doubly Linked List
• Insert into ordered list
 Delete
 Traverse list (Print list)
 Copy linked list
Singly Linked List

A next B next C next D

NULL
FIRST

 It is basic type of linked list.

 Each node contains data and pointer to next node.
 Last node’s pointer is null.
 First node address is available with pointer variable FIRST.
 Limitation of singly linked list is we can traverse only in one direction, forward direction.
Node Structure of Singly List

Info Link
Accessing Part

Node
of Node
Typical Node Info (Node)
Data Pointer to Link (Node)

Next Node

struct node
{
C Structure to int info;
represent a node struct node *link;
};
Algorithms for singly linked list
1. Insert at first position
2. Insert at last position
3. Insert in Ordered Linked list
4. Delete Element
Availability Stack
 A pool or list of free nodes, which we refer to as the availability stack is maintained in
conjunction with linked allocation.
 Whenever a node is to be inserted in a list, a free node is taken from the availability stack and
linked to the new list.
 On other end, the deleted node from the list is added to the availability stack.

AVAIL NEW Check for free node in Availability Stack

AVAIL IF AVAIL is NULL
THEN Write(‘Availability Stack Underflow’)
Return

Obtain Address of next free node

NEW  AVAIL

Remove free node from Availability Stack

AVAIL  LINK(AVAIL)
Function: INSERT(X, First)
 This function inserts a new node at the first position of Singly linked list.
 This function returns address of FIRST node.
 X is a new element to be inserted.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Each node has two parts: INFO (stores the data) and LINK (points to the next node).
 AVAIL is a pointer to the top element of the availability stack. (unused nodes)
 NEW is a temporary pointer variable.
Function: INSERT(X,FIRST) Cont…
1. [Underflow?]
IF AVAIL = NULL
Then Write (“Availability Stack Underflow”)
Return(FIRST)
2. [Obtain address of next free Node]
NEW  AVAIL
3. [Remove free node from availability Stack]
AVAIL  LINK(AVAIL)
4. [Initialize fields of new node and its link to the list]
INFO(NEW)  X
LINK (NEW)  FIRST
5. [Return address of new node]
Return (NEW)
Example: INSERT(50, FIRST)

50 link 10 link 50 link 35 link 20

NEW
FIRST

FIRST  INSERT (X, FIRST)

4. [Initialize fields of new node and its link to the list]

INFO(NEW)  X
LINK (NEW)  FIRST
5. [Return address of new node]
Return (NEW)
Example: INSERT(50, FIRST)

50 link 10 link 50 link 35 link 20

NEW
FIRST

FIRST  INSERT (X, FIRST)

4. [Initialize fields of new node and its link to the list]

INFO(NEW)  X
LINK (NEW)  FIRST
5. [Return address of new node]
Return (NEW)
Function: INSEND(X, FIRST)
 This function inserts a new node at the last position of linked list.
 This function returns address of FIRST node.
 X is a new element to be inserted.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Typical node contains INFO and LINK fields.
 AVAIL is a pointer to the top element of the availability stack.
 NEW is a temporary pointer variable.
Function: INSEND(X, First) Cont…
1. [Underflow?] 5. [Is the list empty?]
If AVAIL = NULL If FIRST = NULL
Then Write (“Availability Then Return (NEW)
Stack Underflow”)
Return(FIRST) 6. [Initialize search for a last node]
SAVE FIRST
2. [Obtain address of next free Node]
NEW  AVAIL 7. [Search for end of list]
Repeat while LINK (SAVE) ≠ NULL
3. [Remove free node from availability SAVE  LINK (SAVE)
Stack]
AVAIL  LINK(AVAIL) 8. [Set link field of last node to NEW]
LINK (SAVE)  NEW
4. [Initialize fields of new node]
INFO(NEW)  X 9. [Return first node pointer]
LINK (NEW)  NULL Return (FIRST)
Function: INSEND(50, FIRST)
4. [Initialize fields of new node] 7. [Search for end of list]
INFO(NEW)  X Repeat while LINK (SAVE) ≠ NULL
LINK (NEW)  NULL SAVE  LINK (SAVE)

5. [Is the list empty?] 8. [Set link field of last node to NEW]
If FIRST = NULL LINK (SAVE)  NEW
Then Return (NEW)
9. [Return first node pointer]
6. [Initialize search for a last node] Return (FIRST)
SAVE FIRST
SAVE

10 50 -1 8 35 44 50
NEW
FIRST
Function: INSEND(50, FIRST)
4. [Initialize fields of new node] 7. [Search for end of list]
INFO(NEW)  X Repeat while LINK (SAVE) ≠ NULL
LINK (NEW)  NULL SAVE  LINK (SAVE)

5. [Is the list empty?] 8. [Set link field of last node to NEW]
If FIRST = NULL LINK (SAVE)  NEW
Then Return (NEW)
9. [Return first node pointer]
6. [Initialize search for a last node] Return (FIRST)
SAVE FIRST
SAVE

10 50 -1 8 35 44 50
NEW
FIRST
Single Linked List
// Define the structure for a node // Function to handle stack underflow
struct Node { void handleUnderflow() {
int data; // INFO(NEW) if (avail == nullptr) { // If AVAIL = NULL
Node* link; // LINK(NEW) cout << "Underflow" << endl;
}; return;
// Initialize pointers for the linked list }
Node* avail = nullptr; // Availability stack }
pointer (AVAIL)
Node* first = nullptr; // First node in the list
(FIRST)
Single Linked List
Node* createNode(int x) { if (first == nullptr) {
handleUnderflow(); // Step 1: Check underflow first = newNode; // Set new node as FIRST
return first;
if (avail == nullptr) return first; // Return FIRST if
}
no node available // Step 6: Initialize search for the last node
// Step 2: Obtain address of next free node Node* save = first;

Node* newNode = avail; // Step 7: Search for the end of the list
// Step 3: Remove free node from availability stack while (save->link != nullptr) {
save = save->link;
avail = avail->link; }
// Step 4: Initialize fields of new node
// Step 8: Set link field of the last node to NEW
newNode->data = x; save->link = newNode;
newNode->link = nullptr;
// Step 9: Return the FIRST node pointer
// Step 5: Check if the list is empty return first;
}
Single Linked List
// Function to display the linked list
void displayList(Node* head) {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->link;
}
cout << "NULL" << endl;
}
Single Linked List
int main() {
// Insertvalues into the linked list
// Example: Initialize the first = createNode(10);
availability stack with some nodes first = createNode(20);
first = createNode(30);
avail = new Node{0, nullptr}; //
Predefined nodes for the availability
// Display the linked list
stack cout << "Linked List: ";
avail->link = new Node{0, nullptr}; // displayList(first);
Adding one more node
return 0;
}

Linked List: 10 -> 20 -> 30 -> NULL

Function: INSORD(X, FIRST)
 This function inserts a new node such that linked list preserves the ordering of the terms in
increasing order of their INFO field.
 This function returns address of FIRST node.
 X is a new element to be inserted.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Typical node contains INFO and LINK fields.
 AVAIL is a pointer to the top element of the availability stack.
 NEW is a temporary pointer variable. Predecessor

5 10 15 20 25 30

FIRST
22
NEW
Function: INSORD(X, FIRST)
 This function inserts a new node such that linked list preserves the ordering of the terms in
increasing order of their INFO field.
 This function returns address of FIRST node.
 X is a new element to be inserted.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Typical node contains INFO and LINK fields.
 AVAIL is a pointer to the top element of the availability stack.
 NEW is a temporary pointer variable. Predecessor

5 10 15 20 25 30

FIRST
22
NEW
Function: INSORD(X, FIRST)
1. [Underflow?] 6. [Does the new node precede all other
IF AVAIL = NULL node in the list?]
THEN Write (“Availability IF INFO(NEW) ≤ INFO (FIRST)
Stack Underflow”) THEN LINK (NEW)  FIRST
Return(FIRST) Return (NEW)
2. [Obtain address of next free Node] 7. [Initialize temporary pointer]
NEW  AVAIL SAVE  FIRST
3. [Remove free node from availability 8. [Search for predecessor of new node]
Stack] Repeat while LINK (SAVE) ≠ NULL
AVAIL  LINK(AVAIL) & INFO(NEW) ≥ INFO(LINK(SAVE))
4. [Initialize fields of new node] SAVE  LINK (SAVE)
INFO(NEW)  X 9. [Set link field of NEW node and its
5. [Is the list empty?] predecessor]
IF FIRST = NULL LINK (NEW)  LINK (SAVE)
THEN LINK(NEW)  NULL LINK (SAVE)  NEW
Return (NEW) 10. [Return first node pointer]
Return (FIRST)
Function: INSORD(3, FIRST)

5 10 15 20 25 30

FIRST
3
NEW

6. [Does the new node precede all other node in the list?]
IF INFO(NEW) ≤ INFO (FIRST)
THEN LINK (NEW)  FIRST
Return (NEW)
Function: INSORD(22, FIRST)
7. [Initialize temporary pointer] 9. [Set link field of NEW node and its
SAVE  FIRST predecessor]
8. [Search for predecessor of new node] LINK (NEW)  LINK (SAVE)
Repeat while LINK (SAVE) ≠ NULL LINK (SAVE)  NEW
& INFO(NEW) ≥ INFO(LINK(SAVE)) 10. [Return first node pointer]
SAVE  LINK (SAVE) Return (FIRST)

SAVE

5 10 15 20 25 30

FIRST

22
NEW
Function: INSORD(22, FIRST)
7. [Initialize temporary pointer] 9. [Set link field of NEW node and its
SAVE  FIRST predecessor]
8. [Search for predecessor of new node] LINK (NEW)  LINK (SAVE)
Repeat while LINK (SAVE) ≠ NULL LINK (SAVE)  NEW
& INFO(NEW) ≥ INFO(LINK(SAVE)) 10. [Return first node pointer]
SAVE  LINK (SAVE) Return (FIRST)

SAVE

5 10 15 20 25 30

FIRST

22
NEW
Procedure: DELETE(X, FIRST)
 This algorithm delete a node whose address is given by variable X.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Typical node contains INFO and LINK fields.
 SAVE & PRED are temporary pointer variable.

PRED SAVE

5 10 15 20 25 30

FIRST
Procedure: DELETE(X, FIRST)
 This algorithm delete a node whose address is given by variable X.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Typical node contains INFO and LINK fields.
 SAVE & PRED are temporary pointer variable.

PRED

5 10 15 25 30

FIRST
Procedure: DELETE( X, FIRST)
1. [Is Empty list?] 5. [Move to next node]
IF FIRST = NULL SAVE  LINK(SAVE)
THEN write (‘Underflow’) 6. [End of the list?]
Return If SAVE ≠ X
2. [Initialize search for X] THEN write (‘Node not found’)
SAVE  FIRST Return
3. [Find X] 7. [Delete X]
Repeat thru step-5 If X = FIRST
while SAVE ≠ X and THEN FIRST  LINK(FIRST)
LINK (SAVE) ≠ NULL ELSE LINK (PRED)  LINK (X)
4. [Update predecessor marker] 8. [Free Deleted Node]
PRED  SAVE Free (X)
Procedure: DELETE(7541, FIRST)
2. [Initialize search for X] 6. [End of the list?]
SAVE  FIRST If SAVE ≠ X
3. [Find X] THEN Write (‘Node not found’)
Repeat thru step-5 Return
while SAVE ≠ X and 7. [Delete X]
LINK (SAVE) ≠ NULL If X = FIRST
4. [Update predecessor marker] THEN FIRST  LINK(FIRST)
PRED  SAVE ELSE LINK (PRED)  LINK (X)
5. [Move to next node] 8. [Free Deleted Node]
SAVE  LINK(SAVE) Free (X)
SAVE
PRED

5 10 15 20 25 30
4455 8564 7541 1254 3254
5000
FIRST
Procedure: DELETE(7541, FIRST)
2. [Initialize search for X] 6. [End of the list?]
SAVE  FIRST If SAVE ≠ X
3. [Find X] THEN Write (‘Node not found’)
Repeat thru step-5 Return
while SAVE ≠ X and 7. [Delete X]
LINK (SAVE) ≠ NULL If X = FIRST
4. [Update predecessor marker] THEN FIRST  LINK(FIRST)
PRED  SAVE ELSE LINK (PRED)  LINK (X)
5. [Move to next node] 8. [Free Deleted Node]
SAVE  LINK(SAVE) Free (X)
SAVE
PRED

5 10 15 25 30
4455 8564 1254 3254
5000
FIRST
Function: COUNT_NODES(FIRST)
 This function counts number of nodes of the linked list and returns COUNT.
 FIRST is a pointer to the first element of a Singly linked linear list.
 Typical node contains INFO and LINK fields.
 SAVE is a Temporary pointer variable.

1. [Is list Empty?] 3. [Go for end of list]

IF FIRST = NULL Repeat while LINK (SAVE) ≠ NULL
Then COUNT  0 SAVE  LINK (SAVE)
Return(COUNT) COUNT  COUNT + 1
2. [Initialize loop for a last node 4. [Return Count]
to update count] Return (COUNT)
SAVE FIRST
Circularly Linked Linear List
 If we replace NULL pointer of the last node of Singly Linked Linear List with the address of its
first node, that list becomes circularly linked linear list or Circular List.
 FIRST is the address of first node of Circular List
 LAST is the address of the last node of Circular List
 Advantages of Circular List
 In circular list, every node is accessible from given node
 It saves time when we have to go to the first node from the last node. It can be done in single step because
there is no need to traverse the in between nodes. But in double linked list, we will have to go through in
between nodes LAST

5 10 15 20 25 30

FIRST
Circularly Linked Linear List Cont…
 Disadvantages of Circular List
 It is not easy to reverse the linked list.
 If proper care is not taken, then the problem of infinite loop can occur.
 If we at a node and go back to the previous node, then we can not do it in single step. Instead we have to
complete the entire circle by going through the in between nodes and then we will reach the required node.

 Operations on Circular List

 Insert at First
 Insert at Last
 Insert in Ordered List
 Delete a node
Procedure: CIR_INS_FIRST(X,FIRST,LAST)
 This procedure inserts a new node at the first position of Circular linked list.
 X is a new element to be inserted.
 FIRST and LAST are a pointer to the first & last elements of a Circular linked linear list,
respectively.
 Typical node contains INFO and LINK fields.
 NEW is a temporary pointer variable.
Procedure: CIR_INS_FIRST(X,FIRST,LAST)
1. [Creates a new empty node] IF FIRST = NULL
NEW NODE THEN LINK (NEW)  NEW
2. [Initialize fields of new node and FIRST  LAST  NEW
its link] ELSE LINK (NEW)  FIRST
INFO (NEW)  X LINK (LAST)  NEW
FIRST  NEW
FIRST
Return
NEW
FIRST LAST
50
LAST

50
NEW 5 10 1 -5

FIRST
Procedure: CIR_INS_FIRST(X,FIRST,LAST)
1. [Creates a new empty node] IF FIRST = NULL
NEW NODE THEN LINK (NEW)  NEW
2. [Initialize fields of new node and FIRST  LAST  NEW
its link] ELSE LINK (NEW)  FIRST
INFO (NEW)  X LINK (LAST)  NEW
FIRST  NEW
FIRST
Return
NEW
FIRST LAST
50
LAST

50
NEW 5 10 1 -5
Procedure: CIR_INS_LAST(X,FIRST,LAST)
 This procedure inserts a new node at the last position of Circular linked list.
 X is a new element to be inserted.
 FIRST and LAST are a pointer to the first & last elements of a Circular linked linear list,
respectively.
 Typical node contains INFO and LINK fields.
 NEW is a temporary pointer variable.
Procedure: CIR_INS_LAST( X,FIRST,LAST)
1. [Creates a new empty node] IF FIRST = NULL
NEW NODE THEN LINK (NEW)  NEW
2. [Initialize fields of new node FIRST  LAST  NEW
and its link] ELSE LINK (NEW)  FIRST
INFO (NEW)  X LINK (LAST)  NEW
LAST  NEW
Return

NEW
FIRST LAST
50
LAST
50
NEW
5 10 1 -5

FIRST
Procedure: CIR_INS_LAST( X,FIRST,LAST)
1. [Creates a new empty node] IF FIRST = NULL
NEW NODE THEN LINK (NEW)  NEW
2. [Initialize fields of new node FIRST  LAST  NEW
and its link] ELSE LINK (NEW)  FIRST
INFO (NEW)  X LINK (LAST)  NEW
LAST  NEW
Return
LAST
NEW
FIRST LAST
50

50
NEW
5 10 1 -5

FIRST
Procedure: CIR_INS_ORD(X,FIRST,LAST)
 This function inserts a new node such that linked list preserves the ordering of the terms in
increasing order of their INFO field.
 X is a new element to be inserted.
 FIRST and LAST are a pointer to the first & last elements of a Circular linked linear list,
respectively.
 Typical node contains INFO and LINK fields.
 NEW is a temporary pointer variable.
Procedure: CIR_INS_ORD(X,FIRST,LAST)
1. [Create New Empty Node] 5. [Initialize Temporary Pointer]
NEW NODE SAVE  FIRST
2. [Copy information content into new 6. [Search for Predecessor of new node]
node] Repeat while SAVE ≠ LAST &
INFO(NEW)  X INFO(NEW) ≥ INFO(LINK(SAVE))
3. [Is Linked List Empty?] SAVELINK(SAVE)
IF FIRST = NULL 7. [Set link field of NEW node and its
THEN LINK(NEW)  NEW Predecessor]
FIRST  LAST  NEW LINK(NEW)  LINK(SAVE)
Return LINK(SAVE)  NEW
4. [Does new node precedes all other IF SAVE = LAST
nodes in List?] THEN LAST  NEW
IF INFO(NEW)≤ INFO(FIRST) 8. [Finished]
THEN LINK(NEW)  FIRST Return
LINK(LAST)  NEW
FIRST  NEW
Return
Procedure: CIR_INS_ORD(3,FIRST,LAST)
1. [Create New Empty Node] 4. [Does new node precedes all other
NEW NODE nodes in List?]
2. [Copy information content into new IF INFO(NEW)≤ INFO(FIRST)
node] THEN LINK(NEW)  FIRST
INFO(NEW)  X LINK(LAST)  NEW
3. [Is Linked List Empty?] FIRST  NEW
IF FIRST = NULL Return
THEN LINK(NEW)  NEW
FIRST  LAST  NEW
Return FIRST
NEW

FIRST LAST 3
LAST

3
5 10 15 20
NEW
FIRST
Procedure: CIR_INS_ORD(3,FIRST,LAST)
1. [Create New Empty Node] 4. [Does new node precedes all other
NEW NODE nodes in List?]
2. [Copy information content into new IF INFO(NEW)≤ INFO(FIRST)
node] THEN LINK(NEW)  FIRST
INFO(NEW)  X LINK(LAST)  NEW
3. [Is Linked List Empty?] FIRST  NEW
IF FIRST = NULL Return
THEN LINK(NEW)  NEW
FIRST  LAST  NEW
Return FIRST
NEW

FIRST LAST 3
LAST

3
5 10 15 20
NEW
FIRST
Procedure: CIR_INS_ORD(18,FIRST,LAST)
5. [Initialize Temporary Pointer] 7. [Set link field of NEW node and its
SAVE  FIRST Predecessor]
6. [Search for Predecessor of new node] LINK(NEW)  LINK(SAVE)
Repeat while SAVE ≠ LAST & LINK(SAVE)  NEW
INFO(NEW) ≥ INFO(LINK(SAVE)) IF SAVE = LAST
SAVELINK(SAVE) THEN LAST  NEW
8. [Finished]
NEW Return

18
LAST
SAVE

5 10 15 20

FIRST
Procedure: CIR_INS_ORD(18,FIRST,LAST)
5. [Initialize Temporary Pointer] 7. [Set link field of NEW node and its
SAVE  FIRST Predecessor]
6. [Search for Predecessor of new node] LINK(NEW)  LINK(SAVE)
Repeat while SAVE ≠ LAST & LINK(SAVE)  NEW
INFO(NEW) ≥ INFO(LINK(SAVE)) IF SAVE = LAST
SAVELINK(SAVE) THEN LAST  NEW
8. [Finished]
NEW Return

18
LAST
SAVE

5 10 15 20

FIRST
Procedure: CIR_DELETE(X,FIRST,LAST)
 This algorithm delete a node whose address is given by variable X.
 FIRST & LAST are pointers to the First & Last elements of a Circular linked list, respectively.
 Typical node contains INFO and LINK fields.
 SAVE & PRED are temporary pointer variable.
Procedure: CIR_DELETE(X,FIRST,LAST)
1. [Is Empty List?] 6. [End of Linked List?]
IF FIRST = NULL IF SAVE ≠ X
THEN write(‘Linked List is THEN write(‘Node not found’)
Empty’) Return
Return 7. [Delete X]
2. [Initialize Search for X] IF X = FIRST
SAVE  FIRST THEN FIRSTLINK(FIRST)
3. [Find X] LINK(LAST)FIRST
Repeat thru step 5 ELSE LINK(PRED)LINK(X)
while SAVE≠X & SAVE≠LAST IF X = LAST
4. [Update predecessor marker] THEN LAST  PRED
PRED  SAVE 8. [Free Deleted Node]
5. [Move to next node] Free (X)
SAVE  LINK(SAVE)
Procedure: CIR_DELETE(7541,FIRST,LAST)
1. [Is Empty List?] 6. [End of Linked List?]
IF FIRST = NULL IF SAVE ≠ X
THEN write(‘Linked List is Empty’) THEN write(‘Node not found’)
Return Return
2. [Initialize Search for X] 7. [Delete X]
SAVE  FIRST IF X = FIRST
3. [Find X] THEN FIRSTLINK(FIRST)
Repeat thru step5 while SAVE≠X & SAVE≠LAST LINK(LAST)FIRST
4. [Update predecessor marker] ELSE LINK(PRED)LINK(X)
PRED  SAVE IF X = LAST
5. [Move to next node] THEN LAST  PRED
SAVE  LINK(SAVE) 8. [Free Deleted Node]
Free (X)

SAVE
PRED

5 10 15 20 25 30
4455 8564 7541 1254 3254
5000
FIRST LAST
Procedure: CIR_DELETE(7541,FIRST,LAST)
1. [Is Empty List?] 6. [End of Linked List?]
IF FIRST = NULL IF SAVE ≠ X
THEN write(‘Linked List is Empty’) THEN write(‘Node not found’)
Return Return
2. [Initialize Search for X] 7. [Delete X]
SAVE  FIRST IF X = FIRST
3. [Find X] THEN FIRSTLINK(FIRST)
Repeat thru step5 while SAVE≠X & SAVE≠LAST LINK(LAST)FIRST
4. [Update predecessor marker] ELSE LINK(PRED)LINK(X)
PRED  SAVE IF X = LAST
5. [Move to next node] THEN LAST  PRED
SAVE  LINK(SAVE) 8. [Free Deleted Node]
Free (X)

PRED

5 10 15 25 30
4455 8564 1254 3254
5000
FIRST LAST
Circularly Linked List with Header Node
 We can have special node, often referred to as Head node of Circular Linked List.
 Head node does not have any value.
 Head node is always pointing to the first node if any of the linked list.
 One advantage of this technique is Linked list is never be empty.
 Pointer variable HEAD contains the address of head node.

HEAD

10 15 20 25 30

HEAD
Empty List
LINK(HEAD)  HEAD
Doubly Linked Linear List
 Typical node of doubly linked linear list contains INFO, LPTR RPTR Fields
 LPTR is pointer variable pointing to Predecessor of a node
 RPTR is pointer variable pointing to Successor of a node
 Left most node of doubly linked linear list is called L, LPTR of node L is always NULL
 Right most node of doubly linked linear list is called R, RPTR of node R is always NULL

LPTR INFO RPTR

Typical node of
Doubly Linked List L Doubly linked linear list R
Insert node in Doubly Linked List
Insertion in the middle of Doubly Linked Linear List
Before Insertion M

L R
LPTR(NEW)  LPTR(M)
NEW RPTR(NEW)  M
LPTR(M)  NEW
RPTR(LPTR(NEW))  NEW
After Insertion
M

L R

NEW
Insert node in Doubly Linked List
Left most insertion in Doubly Linked Linear List
Before Insertion
M

L R
LPTR(NEW)  NULL
RPTR(NEW)  M
NEW LPTR(M)  NEW
L  NEW

M After Insertion

L
L R

NEW
Procedure: DOU_INS (L,R,M,X)
 This algorithm inserts a new node in doubly linked linear list.
 The insertion is to be performed to the left of a specific node with its address given by the
pointer variable M.
 Typical node of doubly linked list contains following fields LPTR, RPTR and INFO.
 LPTR is pointer variable pointing to Predecessor of a node.
 RPTR is pointer variable pointing to Successor of a node.
 L & R are pointer variables pointing for Leftmost and Rightmost node of Linked List.
 NEW is the address of New Node.
 X is value to be inserted.
Procedure: DOU_INS (L,R,M,X)
1. [Create New Empty Node] 4. [Is left most insertion ?]
NEW NODE IF M = L
2. [Copy information field] THEN LPTR(NEW)  NULL
INFO(NEW)  X RPTR(NEW)  M
3. [Insert into an empty list] LPTR(M) NEW
IF R = NULL L  NEW
THEN LPTR(NEW)  NULL Return
RPTR(NEW)  NULL 5. [Insert in middle]
L  R  NEW LPTR(NEW)  LPTR(M)
Return RPTR(NEW)  M
LPTR(M)  NEW
RPTR(LPTR(NEW))  NEW
Return
PROCEDURE: DOU _DEL (L, R, OLD)
 This algorithm deletes the node whose address is contained in the variable OLD.
 Typical node of doubly linked list contains following fields LPTR, RPTR and INFO.
 LPTR is pointer variable pointing to Predecessor of a node.
 RPTR is pointer variable pointing to Successor of a node.
 L & R are pointer variables pointing for Leftmost and Rightmost node of Linked List.
Delete from Doubly Linked List

10 L  R  NULL
OLD
L R

OLD OLD OLD

L L R R

L  RPTR(L) RPTR(LTRP(OLD))  RPTR(OLD) R  LPTR(R)

LPTR (L)  NULL LPTR(RTRP(OLD))  LPTR(OLD) RPTR (R)  NULL
Delete from Doubly Linked List

10 L  R  NULL
OLD
L R

L R

L  RPTR(L) RPTR(LTRP(OLD))  RPTR(OLD) R  LPTR(R)

LPTR (L)  NULL LPTR(RTRP(OLD))  LPTR(OLD) RPTR (R)  NULL
PROCEDURE: DOU _DEL (L, R, OLD)
1. [Is underflow ?]
IF R=NULL
THEN write (‘UNDERFLOW’)
Return
2. [Delete node]
IF L = R (single node in list)
THEN L  R  NULL
ELSE IF OLD = L (left most node)
THEN L  RPTR(L)
LPTR (L)  NULL
ELSE IF OLD = R (right most)
THEN R  LPTR (R)
RPTR (R)  NULL
ELSE RPTR(LPTR (OLD))  RPTR (OLD)
LPTR(RPTR (OLD))  LPTR (OLD)
3. [FREE deleted node ?]
FREE(OLD)
Stack
Stack
Definition: A stack is an ordered list in which insertion and deletion are done at one end, called
top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First out
(LIFO) or First in Last out (FILO) list. (Book: N. Karumanchi, “Data structures and algorithms
made easy”)

Insertion and deletion of data in stack

Stack
 A linear list which allows insertion and deletion of an element at one end only is called stack.
 The insertion operation is called as PUSH and deletion operation as POP.
 The most accessible elements in stack is known as top.
 The elements can only be removed in the opposite orders from that in which they were added to
the stack.
 Such a linear list is referred to as a LIFO (Last In First Out) list.
STACK OPERATIONS & EXCEPTIONS
 Operations:
 PUSH
 POP
 IsEmpty
 IsFull
 Peek

• Exceptions: Erroneous condition caused due to execution of an operation

HOW A STACK WORKS?
Procedure : PUSH (S, TOP, X)
 This procedure inserts an element X to the top of a stack.
 Stack is represented by a vector S containing N elements.
 A pointer TOP represents the top element in the stack.
1. [Check for stack overflow] Stack is empty, TOP = 0, N=3 TOP = 3 -5
If TOP ≥ N TOP = 2 8
Then write (‘STACK OVERFLOW’) PUSH(S, TOP, 10) TOP = 1 10
Return S
2. [Increment TOP] PUSH(S, TOP, 8)
TOP ← TOP + 1
PUSH(S, TOP, -5)
3. [Insert Element]
S[TOP] ← X
PUSH(S, TOP, 6)
4. [Finished]
Return Overflow
Function : POP (S, TOP)
 This function removes & returns the top element from a stack.
 Stack is represented by a vector S containing N elements.
 A pointer TOP represents the top element in the stack.
1. [Check for stack underflow] POP(S, TOP) TOP = 3 -5
If TOP = 0 TOP = 2 8
TOP = 1 10
Then write (‘STACK UNDERFLOW’) POP(S, TOP)
TOP = 0 S
Return (0)
2. [Decrement TOP] POP(S, TOP)
TOP ← TOP - 1
3. [Return former top element of POP(S, TOP)
stack]
Return(S[TOP + 1])
Underflow
Infix Prefix Postfix Conversion
 Evaluating Infix Expression

2+2*2+2*2
1 2
3
4

 A repeated scanning from left to right is needed as operators appears inside the operands.
 Repeated scanning is avoided if the infix expression is first converted to an equivalent
parenthesis free prefix or suffix (postfix) expression.
 Prefix Expression: Operator, Operand, Operand
 Postfix Expression: Operand, Operand, Operator
Difference
Sr. Infix Postfix Prefix
1 a a a
2 a+b ab+ +ab
3 a+b+c ab+c+ ++abc
4 a + (b + c) abc++ +a+bc
5 a + (b * c) abc*+ +a * b c
6 a * (b + c) abc+* *a+bc
7 a*b*c a b *c* ** a b c

a+b+c a+b+c (ab+)+ c (ab+) c + ab+c+

 Create an empty stack called stack for keeping operators. Create an empty list for output.
Read the character list from left to right and perform following steps
1 If the character is an operand (Variable), append it to the end of the output list
2 If the character is a left parenthesis ‘(’, push it on the stack
3 If the character is a right parenthesis ‘)’, pop the stack until the corresponding left parenthesis ‘)’ is
removed. Append each operator to the end of the output list.
4 If the token is an operator, *, /, +, or -, push it on the stack. However, first remove any operators already on
the stack that have higher or equal precedence and append them to the output list.

(a * (b + c))
Infix to Postfix Conversion
 Convert infix: A+B×(C−D) Step Action Stack Output

 Postfix: ? A Add operand to output A

+ Push operator to stack + A
B Add operand to output + AB
x Push operator to stack (higher precedence) +x AB
ABCD−×+ ( Push opening parenthesis +x( AB
C Add operand to output +x( ABC
- Push operator to stack +x(- ABC
D Add operand to output +x(- ABCD
) Pop to output until opening parenthesis +x ABCD-
End Pop remaining operators to output ABCD−×+
Postfix to Infix Conversion
Postfix:
Step Character Action Stack State
ABC*+D-
Infix: ??? 1 A Push operand ["A"]

2 B Push operand ["A", "B"]

3 C Push operand ["A", "B", "C"]

final Infix Expression: 4 * Pop C, B; form (B * C) ["A", "(B * C)"]

((A+(B×C))−D) 5 + Pop (B * C), A; form (A + (B * C)) ["(A + (B * C))"]

6 D Push operand ["(A + (B * C))", "D"]

7 - Pop D, (A + (B * C)); form ((A + (B * C)) - D) ["((A + (B * C)) - D)"]

QUEUE
Queue
 A linear list which permits deletion to be performed at one end of the list and insertion at the
other end is called queue.
 The information in such a list is processed FIFO (first in first out) or FCFS (first come first
served) manner.
 Front is the end of queue from that deletion is to be performed.
 Rear is the end of queue at which new element is to be inserted.
 Insertion operation is called Enqueue & deletion operation is called Dequeue.
10 8 5 80 50 100

Deletion Insertion

Front Rear
Applications of Queue
 Queue of people at any service point such as ticketing etc.
 Queue of air planes waiting for landing instructions.
 Queue of processes in OS.
 Queue is also used by Operating systems for Job Scheduling.
 When a resource is shared among multiple consumers. E.g., in case of printers the first one to
be entered is the first to be processed.
 When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.
 Queue is used in BFS (Breadth First Search) algorithm. It helps in traversing a tree or graph.
 Queue is used in networking to handle congestion.
Procedure: Enqueue (Q, F, R, N,Y)
 This procedure inserts Y at rear end of Queue. R

 Queue is represented by a vector Q containing N elements.

5 20 80
 F is pointer to the front element of a queue.
 R is pointer to the rear element of a queue. F

1. [Check for Queue Overflow] N=3, R=0, F=0

If R >= N
Then write (‘Queue Overflow’) F = 10
Return R=3 2
10
2. [Increment REAR pointer]
Enqueue (Q, F, R, N=3,Y=5)
R  R + 1
Enqueue (Q, F, R, N=3,Y=20)
3. [Insert element]
Q[R]  Y Enqueue (Q, F, R, N=3,Y=80)
4. [Is front pointer properly set?] Enqueue (Q, F, R, N=3,Y=3)
IF F=0 Queue Overflow
Then F  1
Return
Function: Dequeue (Q, F, R)
 This function deletes & returns an element from front end of the Queue.
 Queue is represented by a vector Q containing N elements.
 F is pointer to the front element of a queue. Case No 1:
F=0, R=0
 R is pointer to the rear element of a queue.
1. [Check for Queue Underflow] Queue Underflow
If F = 0
Then write (‘Queue Underflow’) Case No 2: FR
Return(0) F=3, R=3
2. [Delete element]
Y  Q[F] F=0, R=0 50
3. [Is Queue Empty?]
If F = R
Then F  R  0 Case No 3: F R
Else F  F + 1 F=1, R=3
4. [Return Element]
5 -8 50
Return (Y) F=2, R=3
Example of Queue Insert / Delete
Perform following operations on queue with size 4 & draw queue after each operation
Insert ‘A’ | Insert ‘B’ | Insert ‘C’ | Delete ‘A’ | Delete ‘B’ | Insert ‘D’ | Insert ‘E’

Empty Queue R=3 Insert ‘C’ R=4 Insert ‘D’

F=1 F=3
00 A B C C D

FR F R F R

R=1 Insert ‘A’ R=3 Delete ‘A’ R=4 Insert ‘E’

F=2 F=3
F=1 A A B C C D

FR F R F R

Insert ‘B’ R=3 Delete ‘B’ (R=4) >= (N=4) (Size of Queue)
R=2 F=3 Queue Overflow
F=1 A B B C
Queue Overflow, but space is
there with Queue, this leads to
FR F R the memory wastage
Circular Queue
 A more suitable method of representing simple queue which prevents an excessive use of
memory is to arrange the elements Q[1], Q[2]….,Q[n] in a circular fashion with Q[1] following
Q[n], this is called circular queue.
 In circular queue the last node is connected back to the first node to make a circle.
 Circular queue is a linear data structure. It follows FIFO principle.
 It is also called as “Ring buffer”.

Q[1] Q[2] Q[n]

Procedure: CQINSERT (F, R, Q, N, Y)
 This procedure inserts Y at rear end of the Circular Queue. F R

 Queue is represented by a vector Q containing N elements. 8 15

 F is pointer to the front element of a queue.
 R is pointer to the rear element of a queue. F R

1. [Reset Rear Pointer] 3. [Insert element]

8 15
If R = N Q[R]  Y
Then R  1 4. [Is front pointer
Else R  R + 1 properly set?]
2. [Overflow] IF F=0 F R
If F=R Then F  1
Then Write(‘Overflow’) Return 23 6 8 15
Return
Function: CQDELETE (F, R, Q, N)
 This function deletes & returns an element from front end of the F R

Circular Queue.
6
 Queue is represented by a vector Q containing N elements.
 F is pointer to the front element of a queue. R F

 R is pointer to the rear element of a queue.

2 6 4
1. [Underflow?] 4. Increment Front Pointer]
If F = 0 IF F = N
Then Write(‘Underflow’) Then F  1 F R
Return(0) Else F  F + 1
2. [Delete Element] Return(Y)
Y  Q[F] 6 8 4
3. [Queue Empty?]
If F = R
Then F  R  0
Return(Y)
Example of CQueue Insert / Delete
Perform following operations on Circular queue with size 4 & draw queue after each operation
Insert ‘A’ | Insert ‘B’ | Insert ‘C’ | Delete ‘A’ | Delete ‘B’ | Insert ‘D’ | Insert ‘E’

Empty Queue R=3 Insert ‘C’ R=4 Insert ‘D’

F=1 F=3
00 A B C C D

FR F R F R

R=1 Insert ‘A’ R=3 Delete ‘A’ R=1 Insert ‘E’

F=2 F=3
F=1 A A B C E C D

FR F R F R

Insert ‘B’ R=3 Delete ‘B’

R=2 F=3
F=1 A B B C

FR F R
Priority Queue
 A queue in which we are able to insert & remove items from any position based on some
property (such as priority of the task to be processed) is often referred as priority queue.
 Below fig. represent a priority queue of jobs waiting to use a computer.
 Priorities are attached with each Job
 Priority 1 indicates Real Time Job
 Priority 2 indicates Online Job
 Priority 3 indicates Batch Processing Job

 Therefore if a job is initiated with priority i, it is inserted immediately at the end of list of other
jobs with priorities i.
 Here jobs are always removed from the front of queue.
Priority Queue
 An extension of queue.

 Each element is has priority associated with it, and get served based on the priority.

 Priority Queue
Element Priority
 Ascending Priority Queue
A 7
 Descending Priority Queue
B 6

C 4 E D C B F A

D 2

E 1

F 6 A B F C D E
Priority Queue Cont…
Task R1 R2 … Ri-1 O1 O2 … Oj-1 B1 B2 … Bk-1 …
Priority 1 1 … 1 2 2 … 2 3 3 … 3 …

Ri Oj Bk
Priority Queue viewed as a single queue with insertion allowed at any position

Priority - 1 R1 R2 … Ri-1 Ri

Priority - 2 O1 O2 … Oj-1 Oj

Priority - 3 B1 B2 … Bk-1 Bk

Priority Queue viewed as a Viewed as a set of queue

Comparation
Feature Queue Circular Queue Priority Queue
Linear structure where
Linear data structure; follows Linear structure where the end
Definition elements are dequeued based
FIFO. connects to the front.
on priority.

Insertion Order Strict FIFO. FIFO with cyclic behavior. Based on assigned priority.

Inefficient; unused space is Efficient; reuses empty

Memory Usage Depends on implementation.
wasted. spaces.
Emergency Room Triage, OS
Real-Time Printer Queue, Ticket Counter, Traffic Signal, IoT Circular
Task Scheduling, Autonomous
Examples Call Queue. Buffers, Game Rounds.
Vehicle Path Planning
Simple to implement; fair order Prevents overflow by reusing Ensures critical tasks are
Key Features
processing. space. processed first.

When order of arrival is most When cyclic and memory When priority supersedes
Best Use Case
important. efficiency is needed. order of arrival.
 THANK YOU
chapter-1 is finished
Basic Analysis: Differences among best, expected, and worst case behaviors of an
algorithm, Asymptotic analysis, Big O notation: formal definition and use, big omega and
big theta notation, Time and space trade-offs in algorithms, Recurrence relations, Analysis
of iterative and recursive algorithms.