Unit-1 Notes - Data Structure

Data Structure(KCS-301)
Introduction to Data Structures
By
Puneet Kumar Goyal

Assistant Professor
Department of Information Technology
Ajay Kumar Garg Engineering College, Ghaziabad
OUTLINE
✓What is Data Structure?
✓Why, Data Structure?
✓Classification
✓Operations on Data Structures
✓ADT
What is Data Structures?
Data: It can be defined as value or set of values.
Ex- Name of a Person, Id of an employee, salary etc..
Process
Data
Memory Information
Role of Data
Structures
What is Data Structures?
Data Structures: It is a way of organizing or storing
data into the memory so that operations on the data
can be performed efficiently.
Ex- arrays, stack, queue, Tree, Graph etc..

Need of Data Structures
Organize data has major impact on performance.
✓To understand it, consider some real life examples such as
Queue at a ticket counter.
Dictionary.
Queue in printer.
Arrangement of books in library etc..
✓Programming point of view
Program Algorithm + Data Structures
Therefore choosing an appropriate Data structures
improves the performance of a program or a Software.
Classification of Data Structures
Data Structures
Primitive Data Non-Primitive

Structures Data Structures
int
float
Linear Non-Linear
Char
double
Arrays Stack Queue Linked List Tree Graph
e
Primitive Data Structures:
✓These are Pre-defined, built in Data types.
✓Machine dependent i.e. on 16 bit machine int data type
is 2 bytes in size while on 32bit or 64 bit it is of 4 bytes.
Non-Primitive Data Structures:

✓User Defined Data types.
✓Also called Derived data types as they are derived from
Primitive Data structures.
Operations on Data Structures
✓Insertion: Add an element to the Data Structure. i.e.
insert an element as first element or last element or at
any location.
✓Deletion: Remove an element from Data Structure.
i.e. delete first element, last element or element at
given location.
✓Traversing: Visit the element at least once to perform
some specific operation like find sum, average, count
nodes in list etc.
Operations on Data Structures
✓Searching : To find whether an element is
present or not in the given data structure.
✓Sorting : It is method to arrange the
elements in a particular order either in ascending or in
descending.
✓Merging : It is method which takes two
sorted lists of similar data types as input and produce
combined sorted list as output.
ALGORITHM
• It is a step-by-step procedure to solve a particular problem
statement.
• There are many ways to solve a particular problem, may be more
than one algorithm for a single problem.
• Choose an efficient algorithm among many there is a technique
known as ‘Complexity of Algorithm’.
CRITERIA OF AN
ALGORITHM
• Input
• Output
• Definiteness
• Finiteness
• Effectiveness
COMPLEXITY OF
ALGORITHM
• Time Complexity:-Time complexity of an algorithm is the amount
of time it needs in order to run to completion.
• Space Complexity:-Space Complexity of an algorithm is the
amount of space it needs in order to run to completion.
ASYMPTOTIC NOTATION
•Mathematical notation that allow us to analyse an algorithm's
running time by identifying its behaviour as the input size for the
algorithm increases.
•This is also known as an algorithm's growth rate.
•Big-Oh Notation (O)
•Big-Theta Notation (Θ)
•Big-Omega Notation (Ω)
Big-Oh Notation (O)
• It provides possibly asymptotically tight upper bound for f(n).
• Let f be a nonnegative function and we say that f(n) is Big-O of

g(n), written as f(n) = O(g(n)), iff there are positive constants c and
n0 such that
0 ≤ f(n) ≤ c g(n) for all n ≥ n0
• If f(n) = O(g(n)), we say that g(n) is an upper bound on f(n).

Big-Theta Notation (Θ)
• We say that f(n) is Big-Theta of g(n), written as

f(n) = Θ(g(n)), iff there are positive constants c1,
c2 and n0 such that
0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)

for all n ≥ n0
• Equivalently, f(n) = Θ(g(n)) if and only if f(n) =

O(g(n)) and f(n) = Ω(g(n)). If f(n) = Θ(g(n)), we
say that g(n) is a tight bound on f(n).
Big-Omega Notation (Ω)
•It provides possibly asymptotically tight lower bound for f(n) and it
does not give worst case complexity but can give best case
complexity, f(n) is said to be Big-Omega of g(n), written as f(n) =
Ω(g(n)), iff there are positive constants c and n0 such that
0 ≤ c g(n) ≤ f(n) for all n ≥ n0
• If f(n) = Ω(g(n)), we say that g(n) is a lower bound on f(n).

EXAMPLE OF Θ,Ω,O
Abstract Data Types
Present only the simple view
Abstraction of any object but hide the
implementation details.
Its focuses only on
Ex- TV remote What rather Than
HOW.
To start the TV ,simply press ON button

without knowing its implementation
details.
Abstract Data Types
ADT represent the logical or mathematical model for any
data structure.
It basically describes:
a) Representation of data.
b) Operations that can be performed on these data
without any implementation.
Abstract Data Types
Ex- Stack Abstract Data Type-
a) Stack follows the LIFO concepts.
b) Operations to be performed are :
i) PUSH(data)→ insert an element at the top
ii) POP() → Remove an element from the top
iii) PEEK() → view the element which present at the top
iv) is Empty() → To check, whether stack is empty or not?

By
Puneet Kumar Goyal

Assistant Professor
INDEX: Classification of Data Structures
Data Structures
Primitive Data Non-Primitive

Structures Data Structures
int
float
Linear Non-Linear
Char
double
Arrays Stack Queue Linked List Tree Graph
e
Primitive Data Structures:
✓These are Pre-defined, built in Data types.
✓Machine dependent i.e. on 16 bit machine int data type
is 2 bytes in size while on 32bit or 64 bit it is of 4 bytes.
Non-Primitive Data Structures:

✓User Defined Data types.
✓Also called Derived data types as they are derived from
Primitive Data structures.
Linear Data Structures:
✓Elements are arranged in logical sequential
manner.
E1→E2→E3→………En
✓Except the first and last element, every element is
connected with its predecessor and successor.
✓Easy to implement. Ex-Arrays, Stack, Queue etc.
Arrays Data Structure:
✓An array is collection of same type of elements which
stored contiguously in memory. So it is Linear Data
structure.
Ex- int A[4]
✓Also called Subscripted variable.
✓Applications are searching, sorting, implement matrix etc.
Stack Data Structure:
✓Stack is a linear Data structure.
✓Elements are inserted and deleted from one end, call TOP
of the stack.
POP
PUSH
It follows
LIFO/FILO
order
Stack Data Structure:
✓Stack can be implemented using arrays as well as
using linked list
✓Some real life examples are piles of books, plates
etc.
Applications are
a) Function Call.
b) Infix to Postfix conversion.
c) Evaluation of Postfix expression, In DFS Graph
Algorithm etc..
Queue Data Structure: It follows
FIFO
✓Queue is a linear data structure. order
✓Elements are inserted at one end called Rear and

deleted from other end which is called Front.
• A[0]
Dequeue • A[1] Enqueue
• A[2]
• A[3]
Front End Rear End
Queue Data Structure:
✓Queue can be implemented using arrays as well as using
linked list
✓Some real life examples are queue at ticket counter,
vehicles at Toll-Plaza etc.
Applications are
a) CPU scheduling and Disk Scheduling algorithms in
operating Systems, Interrupt handling.
b) Job queue at printer.
c) BFS Graph Algorithm, Prim’s Algorithm etc.
Linked List Data Structure:
✓Linked list is a linear Data Structures which stored
non-contiguously in memory.
NODE INFO Link
✓It is collection of nodes where each node has two

fields:
a) INFO field: It actually stores value or set of values.
b) Link Field: It actually stores address to the next
node in the list.
Linked List Data Structure:
✓It provides memory utilization when memory is not
available contiguously.
✓It is basically implemented using Dynamic Memory
allocation.
Applications are: Used to implement Stack, Queue, Tree,
Graph.
Polynomial operations, Sparse matrices representation
etc.
Non-Linear Data Structures:
✓Elements are arranged in non- sequential manner.
✓Each element may be connected to two or more
elements.
✓Ex- Tree, Graph.
Tree Data Structure:
✓It is a non-linear ,hierarchical data structure.
✓It follows Parent- Child relationship.
✓Each node in tree can have more than one children but
at most one Parent node.
Root Node
Left Child
Right Child
Leaf Node
Tree Data Structure:
Applications:
a) File system on a computer.
b) Efficient searching using Binary Search Tree.
c) Minimal Spanning Tree implementation.
d) Heap sort using Heap data structure.
e) Used in compilers to show syntax tree.
Graph Data Structure:
✓It is a non-linear , non-hierarchical data structure.
✓It consist of vertices or nodes and edges which connect
these nodes.
G(V, E) Where V→ Set of vertices and E → Set of edges
✓Each node may be connected to two or more elements.
Graph Applications:
a) Used to represent Networks like rail network, road
network, telephone network etc.
b) Social Networks such as Facebook, Whatsapp.
c) Google Map, Navigation tools.
d) Path optimization algorithms.
e) World Wide Web network.
f) Resource Allocation Graph in OS.
Address Calculation in 1D & 2D Array
By
Puneet Kumar Goyal

Assistant Professor
Arrays Data Structure
✓An array is collection of same type of elements which
stored contiguously in memory. So it is Linear Data
structure.
Ex- int A[4]
✓Also called Subscripted variable.
✓Applications are searching, sorting, implement matrix etc.
One Dimensional Array
✓A one Dimensional array is collection of same type of
elements.
✓It is the simplest form of an array.
Declaration Syntax:
Data Type Arrayname[ Size ]
Ex- int A[4]
Memory Representation
.
Base Address: Address of first element in an array is called
base address.
✓As array elements are stored contiguously so there is no
need to keep track of address of each element of array.
✓We only need to know the base address of an array.
Formula to find address of any element A[i] in 1 D array
Address(A[i]) = Base address + i*esize
➢Here esize is size of the data type of array.
➢This is the formula to find address when array index
starts with 0.
Q-1) Calculate the address of an array elements
a) A[3] b) A[2].
Given Data type of array is int. Base address=100.
Array index starts with 0. Size of each element=4 bytes
Number of elements in array=4
Formula to find address of any element A[i] in 1 D
array- (When LB and UB is given and array index can
be start with any number either –ive or +ive or 0.)
Here LB→ Lower bound of an array i.e. lowest index
or starting index of an array.
UB→ Upper bound of an array i.e. highest index or
last index of an array. LB UB
LB UB
No. of elements in array= (UB-LB +1)

Address(A[i]) → First find effective index of that
element (E)→ (i- LB)
Address(A[i]) = BA + (i-LB) x esize
➢Here esize is size of the data type of array.
Ex- Given an array A[-1 : 2]. Here LB=-1 and UB=2.
Data type of array is int. Base address=100.
Find a) No. of elements in array A.
b) Address of A[1] , A[3] and A[-2].
EXAMPLE-1D
Given A [1:15], bytes per cell = 3, base
address = 1000 find the address of A [9].
Solution:
Here, i = 9
eSize= 3
Lower Bound(LB) = 1
Upper Bound(UB) = 15
Address of A [i] = Base Address +eSize*(i-LB) Address of
A [9] = 1000 + 3*(9 - 1) = 1024
EXAMPLE-1D
For A[5:55], Base address= 300, eSize=4
(i)Find the number of elements?
(ii) Total memory allocated.
(iii) Find the address of A[15], A[40] and A[60]?
EXAMPLE-1D
For A[5:55], Base address= 300, eSize=4
Find the number of elements- 51
address of A[15]- 340
A[40]- 440
A[60] exceeded the size of array hence
address does not exist
Two Dimensional Array
✓A two Dimensional array is collection of same type of
elements which are represented in the form on rows and
columns.
✓It is also called matrix.
Declaration Syntax:
Data Type Arrayname[ R] [C]
R → Number of rows. C→ Number of columns
Ex- Int A[2][3]
Memory Representation: a) Row-major Representation
b) Column-major Representation
a) Row-major Representation:
A[0][0] A[0][1] A[0][2]

A[1][0] A[1][1] A[1][2]
A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2]
Row Index-0 Row Index-1
Therefore 2D array is a collection of 1D arrays which is again a

collection of elements.
Ex- Find the address of A[1][2] using row major
representation.
First find the address of an array having row
Index 1 =100 + 1 x 3 x 4 = 112
Now Find the address of an element
A[1][2]= 112 + 2x 4 =120
In generalized Format the formula to Find Address of
an element A[i1] [i2] using Row Major
First find the address of an array having row
Index i1 = BA + i1 x C x esize
A[i1][i2] = BA + i1 x C x esize + i2 x esize
Address(A[i1][i2]) = BA + (i1 x C + i2 ) x esize
In generalized Format the formula to Find Address of an
element A[i1] [i2] using Row Major When LB and UB is given
for Rows and Columns.
[LB1 : UB1 : : LB2 : UB2]
LB1→ Lower bound of Row. UB1→ Upper bound of Row.
LB2→ Lower bound of Column. UB2→ Upper bound of
Column.
✓No. of Rows(R) = (UB1- LB1 +1)
✓No. of Columns(C) = (UB2- LB2 +1)
✓Total No. of Elements (N) = R x C
EXAMPLE
Q . An array X [-15……….10, 15……………40] requires one byte of storage. If beginning location is 1500 determine
the location of X [9][20].
Solution: As you see here the number of rows and columns are not given in the question. So they are calculated
as:
Number or rows say R = (UB1 – LB1) + 1 = [10 – (- 15)] +1 = 26
Number or columns say C = (UB2 – LB2) + 1 = [40 – 15)] +1 = 26
Total Number of elements=RxC=26x26 = 676
(i) Column Major Wise Calculation of above equation
The given values are: BA = 1500, eSize = 1 byte, i1 = 9 i2 = 20, LB1 = -15, LB2 = 15, R = 26
Address of A [ i1 ][ i2 ] = BA + eSize * [ ( i1 – LB1 ) + *R ( i2 – LB2 ) ]
= 1500 + 1 * [(9 – (-15)) + 26 * (20 – 15)] = 1500 + 1 * [24 + 26 * 5] = 1500 + 1 * [154] = 1654 [Ans]
(ii) Row Major Wise Calculation of above equation
The given values are: BA = 1500, eSize = 1 byte, i1 = 15, i2 = 20, LB1 = -15, LB2 = 15, C = 26
Address of A [ i1 ][ i2 ] = BA + eSize * [ C * ( i1 – LB1 ) + ( i2 – LB2 ) ]
= 1500 + 1* [26 * (9 – (-15))) + (20 – 15)] = 1500 + 1 * [26 * 24 + 5] = 1500 + 1 * [624+ 5] = 1500 + 629
= 2129 [Ans]
EXAMPLE-2D
Given A[ 2:5 :: -3:11] B[A]= 200, W=2 bytes
R=5-2+1=4
C=11+3=1=15
total number of elements= 60
Total memory allocated= 120 bytes
Address of A[3][0] = 236
and A[1][5]= Not exist
Effective Row Index (E1)= (i1- LB1)
Effective Column Index (E2)= (i2- LB2)
Address(A[i1][i2]) = BA + ((i1-LB1) x C + (i2-LB2) ) x esize
Ex- Consider the 2D array A[0 :2 : : 0 : 3]. Given BA=100 and
esize =4 bytes.
a) Find Row size and column size.
b) Total number of elements in A.
c) Total memory allocated.
d) Address of A[1][1] and A[-1][1].
Data Structures
Address Calculation in 2D & 3D Array
By
Puneet Kumar Goyal

Assistant Professor
Department of Computer Science & Engineering
ABES Engineering College, Ghaziabad
✓A two Dimensional array is collection of same type of
elements which are represented in the form on rows and
columns.
✓It is also called matrix.
Declaration Syntax:
Data Type Arrayname[ R] [C]
R → Number of rows. C→ Number of columns
Ex- Int A[2][3]
b) Column-major Representation:
A[0][0] A[0][1] A[0][2]

A[1][0] A[1][1] A[1][2]
A[0][0] A[1][0] A[0][1] A[1][1] A[0][2] A[1][2]
Column Index-0 Column Index-1 Column Index-2
Therefore 2D array is a collection of 1D arrays which is again a

collection of elements.
Ex- Find the address of A[1][2] using column major
representation.
First find the address of an array having column
Index 2 =100 + 2 x 2 x 4 = 116
A[1][2]= 116 + 1x 4 =120
an element A[i1] [i2] using Row Major
First find the address of an array having column
Index i2 = BA + i2 x R x esize
A[i1][i2] = BA + i2 x R x esize + i1 x esize
Address(A[i1][i2]) = BA + (i2 x R + i1 ) x esize
In generalized Format the formula to Find Address of an
element A[i1] [i2] using Column Major When LB and UB is
given for Rows and Columns.
[LB1 : UB1 : : LB2 : UB2]
LB2→ Lower bound of Column. UB2→ Upper bound of
Column.
✓No. of Rows(R) = (UB1- LB1 +1)
✓No. of Columns(C) = (UB2- LB2 +1)
✓Total No. of Elements (N) = R x C
Address(A[i1][i2]) = BA + (E2 x R + E1 ) x esize
Ex- Consider the 2D array A[0 :2 : : 0 : 3]. Given BA=100 and
esize =4 bytes.
a) Find Row size and column size.
d) Address of A[1][1] and A[-1][1] using column major.
Three Dimensional Array
✓A three dimensional array is collection of two Dimensional
array which is again a collection of one dimensional array.
✓It is also called array of arrays of arrays.
✓Assuming three dimesons are Plane, Rows and Columns.
Declaration Syntax:
Data Type Arrayname[ D1] [D2] [D3]
D1 → No. of Planes D2→ Number of Rows
D3→ Number of Columns A[0][0] A[0][1]
Ex- Int A[2][2][2] A[1][0] A[0][0]
A[1][1] A[0][1]
A[1][0] A[1][1]
a) Row-major Representation
A[0][0] A[0][1]
A[1][0] A[0][0]
A[1][1] A[0][1]
A[1][0] A[1][1]
an element A[i1] [i2] [i3]using Row Major
➢First find the address of an array having plane
Index i1 = BA + i1 x D2 x D3 x esize
➢find the address of an array having row index i2 in

plane index i1 =
BA + i1 x D2 x D3 x esize + i2 x D3x esize
Now Find the address of an element having column index i3 in
row index i2 and plane index i1
A[i1][i2][i3] = BA + i1 x D2 x D3 x esize + i2 x D3x
esize + i3 x esize
Address(A[i1][i2][i3]) = BA +( i1 x D2 x D3 + i2 x D3 + i3 ) x esize
In generalized Format the formula to Find Address of an element
A[i1] [i2] [i3] using Row Major When LB and UB is given for Plane,
Rows and Columns.
[LB1 : UB1 : : LB2 : UB2 : : LB3 : UB3]
LB1→ Lower bound of Plane. UB1→ Upper bound of Plane.
LB3→ Lower bound of Column. UB3→ Upper bound of Column.
✓No. of Planes(D1) = (UB1- LB1 +1)
✓No. of Rows(D2) = (UB2- LB2 +1)
✓No. of Columns(D3) = (UB3- LB3 +1)
✓Total No. of Elements (N) = D1 x D2 X D3
Effective Plane Index (E1)= (i1- LB1)
Address(A[i1][i2][i3]) = BA +( E1 x D2 x D3 +
E2 x D3 + E3 ) x esize
Ex- Consider the 3D array A[0 :2 : : 0 : 2 : : 0 :2].
Given BA=100 and esize =4 bytes.
a) Find Plane size ,Row size and column size.
d) Address of A[1][1][1] and A[-1][1][1] using row major.
THANK YOU
Data Structure
(KCS-301)
Traverse & Insert Operation in Single
Linked List
By
Puneet Kumar Goyal

Assistant Professor
Single Linked List-Traversing
TRAVERSE_SLL(START) INFO NEXT

Step-1 [First check List is empty or not?]
IF ( START== NULL) THEN
DISPLAY “LIST is Empty”
Goto Step 4
END of IF
Single Linked List-Traversing
Step-2 [Traverse the list]
PTR=START
Step-3 Repeat Steps (a ) and (b) WHILE (PTR !=NULL)
(a) DISPLAY PTR→INFO
(b) PTR = PTR→Next
Step-4 END
Single Linked List-INSERT new node as
First node
First node
INSERT_F_SLL(START,ITEM)
Step-1 First check free memory is available or Not?
Step-2 Allocate new node from the available memory
and assign address into pointer PTR.
Step-3 [Insert ITEM in the DATA field of node.]
PTR→Info= ITEM
Step-4 [Insert new node as first node]
PTR→Next= START
START= PTR
First node(Pseudo Code)
Single Linked List-INSERT node as Last
Node
Case-1 WHEN LIST IS EMPTY
START
NULL
Node
Case-2 WHEN LIST IS NOT EMPTY
Node
INSERT_L_SLL(START, ITEM)
PTR→INFO= ITEM
Step-4-a) When List is empty
[Insert new node as first node]
PTR→Next= START and START= PTR
Go to Step 6
Node
Step-4-b) When List is not empty
[Traverse the list until Last node is reached]
TEMP= START
Repeat Step WHILE (TEMP→Next != NULL)
TEMP= TEMP→Next
Step-5 [Insert new node as last node.]
TEMP→Next = PTR
PTR→Next = NULL
Step-6 END.
Single Linked List-INSERT node at Given
Position
Case-1 IF Pos=1
START
NULL
Position
Case-2 IF POS>1
Position
INSERT_POS_SLL(START,ITEM, POS)
PTR→Info= ITEM
Step-4-a) When POS=1[Insert new node as first node]
IF (POS==1) THEN
PTR→Next= START and START= PTR
Position
Step-4-b) When POS >1
ELSE
TEMP= START and I=1
Repeat Step WHILE I < (POS-1) AND (TEMP !=NULL)
TEMP= TEMP→Next and I=I+1 // end of loop
Step-5 [Insert new node at given position.]
IF (TEMP != NULL) THEN
PTR→Next = TEMP→Next
TEMP→Next = PTR
Step-6 END.
Delete & Search Operation in Single
Linked List
By
Puneet Kumar Goyal

Assistant Professor
Single Linked List-Searching
DATA LINK
SEARCHING_SLL(ITEM, NEXT, START) DATA LINK

Goto Step 4
END of IF
PTR=START
(a) Check Item is present in List or not?
IF(PTR→INFO == ITEM) THEN
Display “ITEM is present in List”
Goto step 5 //end of IF
(b) PTR = PTR→NEXT // End of Loop
Step-4 [IF ITEM is not present in the List]
IF (PTR==NULL) THEN
DISPLAY “ITEM is not present in the List”
Step-5 END
Single Linked List-DELETE FIRST NODE
Case-1 When there is only one node in the List.
START
Case-2 When there are more than one node in the List.
DELETE_F_SLL(START,ITEM)
Step-1 [First check List is empty or Not?]
IF(START==NULL) THEN
DISPLAY “ LIST is empty”
Goto Step-5
END of IF
Step-2 PTR=START and ITEM = PTR→INFO
DISPLAY ITEM
Step-3 [Delete the first node.]
START= START→NEXT
Step-4 [Free the memory, allocated to deleted node.]
FREE(PTR)
Step-5 END.
Single Linked List-DELETE FIRST NODE(Pseudo code)
ALGORITHM DelBeg(START, item)
BEGIN:
IF START = = NULL THEN
WRITE ("Void Deletion”)
RETURN
ELSE
P= START
Item = P → Info
START = START→ Next
Free(P)
RETURN Item
END;
No of address Adjustment = 1 Complexity of
Operation Time Complexity = O(1)
Space Complexity = O(1)
Single Linked List-DELETE Last Node
Case-1 WHEN LIST has only one
node
START
Case-2 WHEN LIST has more than
one node
DELETE_L_SLL(START, ITEM)
Goto Step-5
END of IF
Step-2 PTR=START and TPTR=NULL
Step-3 [Check If there is only one node in the List.]
IF (START→NEXT== NULL) THEN
START=START→NEXT
ELSE //Traverse the List
Repeat Steps (a) and (b)
WHILE (PTR→NEXT != NULL)
a) TPTR=PTR
b) PTR= PTR→NEXT //End of Loop
TPTR→NEXT = NULL //End of IF-ELSE
Step-4 [DISPLAY the Information of Deleted Node.]
DISPLAY PTR→INFO
FREE(PTR)
Step-6 END.
Single Linked List-DELETE Last Node(Pseudo Code)
Single Linked List-DELETE node at Given
Position
IF Position is 1 IF Position is >1 i.e. Pos=3
START
Single Linked List-DELETE node at
Given Position
DELETE_POS_SLL(START, POS)
Goto Step-4
END of IF
Step-2 PTR=START
Given Position
Step-3 [Check If Position is 1.]
IF (POS==1) THEN
START= PTR→NEXT
DISPLAY PTR→INFO and FREE(PTR) //Goto step 4
ELSE
Set i =1
Repeat Steps
WHILE(( i<POS-1) AND PTR!=NULL)
PTR= PTR→NEXT // End of Loop
Given Position
[Check If Position is valid or not?]
IF(PTR ==NULL) THEN
DISPLAY “Position is invalid”
Goto Step 4
ELSE
Set TPTR = PTR→NEXT
PTR→NEXT = TPTR→NEXT
// END of Inner IF-ELSE
Given Position
Step-3a [DISPLAY the Information of Deleted Node.]
DISPLAY TPTR→INFO
Step-3b [Free the memory, allocated to deleted node.]
FREE(TPTR)
// END of Outer IF-ELSE
Step-4 END.
THANK YOU
Traverse & Insert Operation in Circular

Linked List
By
Puneet Kumar Goyal

Assistant Professor
Circular Linked List-INTRODUCTION
✓ A circular linked list is similar to single linked list

except address field of last node contains the
address of first node.
✓ Here LAST pointer contains the address of the last
node.
Circular Linked List-INTRODUCTION
✓ By taking LAST pointer, insert a node as first or

last node takes constant time i.e. O(1) time.
✓ A queue data structure can be implemented
using a circular linked list with single pointer.
There is no need to use two pointers i.e. Front
and Rear.
Circular Linked List-Traversing
TRAVERSING_CLL(LAST)
IF ( LAST== NULL) THEN
Goto Step 5
END of IF
Circular Linked List-Traversing
PTR=LAST→NEXT
Step-3 Repeat Steps (a ) and (b)
WHILE (PTR→NEXT!=LAST)
(b) PTR = PTR→NEXT // End of Loop
Step-4 [PRINT THE ITEM of LAST Node]
DISPLAY PTR→INFO
Step-5 END.
Circular Linked List--INSERT Node as
FIRST NODE
Case-1 When List is empty.
LAST
FIRST NODE
INSERT_F_CLL(LAST,ITEM)
PTR→INFO= ITEM
FIRST NODE
Step-4 [Check, IF LIST is empty or not?]
IF (LAST!=NULL) THEN
PTR→NEXT = LAST→NEXT
LAST→NEXT = PTR
ELSE
PTR→NEXT = PTR
LAST = PTR
// END of IF-ELSE
Step-5 END.
Circular Linked List--INSERT Node as FIRST
NODE(Pseudo Code)
LAST NODE
Case-1 When List is empty.
LAST
LAST NODE
INSERT_L_CLL(LAST, DATA, LINK, PTR, ITEM)
PTR→INFO= ITEM
LAST NODE
IF (LAST!=NULL) THEN
PTR→NEXT = LAST→NEXT
LAST→NEXT = PTR
LAST = PTR
ELSE
PTR→NEXT = PTR
LAST = PTR // END of IF-ELSE
Step-5 END.
Circular Linked List--INSERT Node as LAST
NODE(Pseudo Code)
cSTART=P
Circular Linked List--INSERT Node at
Given Position
Case-1 When POS=1 and List is empty.
LAST
Case-2 When Pos=1 and there are more than one node in the List.
Given Position
Case-3 When POS >1
Given Position
INSERT_POS_CLL(LAST, DATA, LINK, PTR, ITEM)
PTR→INFO= ITEM
Given Position
IF(POS==1) THEN
IF (LAST==NULL) THEN
PTR→NEXT = PTR
LAST = PTR
ELSE
PTR→LINK = LAST→LINK
LAST→LINK = PTR // END of IF-ELSE
THANK YOU
Delete Operation in Circular Linked List
By
Puneet Kumar Goyal

Assistant Professor
Circular Linked List—DELETE FIRST NODE
Case-1 When there is only one node in the list.
DELETE_F_CLL(LAST)
IF(LAST==NULL) THEN
Goto Step-5
END of IF
Step-2 PTR=LAST→NEXT and ITEM= PTR→INFO
DISPLAY ITEM
Step-3 [Check, IF LIST has only one node?]
IF (PTR=LAST) THEN
LAST=NULL
ELSE
LAST→NEXT = PTR→NEXT // END of IF-ELSE
FREE(PTR)
Step-5 END.
Circular Linked List—DELETE FIRST NODE(Pseudo
Code)
P=cSTART→Next
Circular Linked List—DELETE LAST NODE
Case-1 When there is only one node in the list.
DELETE_L_CLL(LAST)
IF(LAST==NULL) THEN
Goto Step-5
END of IF
Step-2 PTR=LAST→NEXT and Q=LAST
Step-3 [Check, IF LIST has only one node?]
IF (PTR==LAST) THEN
LAST=NULL and Goto Step-5
ELSE
Repeat Step WHILE(PTR→NEXT!=LAST)
PTR=PTR→NEXT //end of Loop
Step-4 [Delete Last Node]
PTR→NEXT = LAST→NEXT and LAST=PTR
FREE(Q)
Step-6 END.
Circular Linked List:DELETE LAST NODE(Pseudo Code)
ALGORITHM DelEnd(cSTART)
BEGIN:
IF cSTART==NULL THEN
WRITE(“Void Deletion”)
ELSE
P=cSTART→Next
Q=cSTART
IF(P==cSTART) THEN
cSTART=NULL
ELSE
WHILE P→Next!=LAST DO
P=P→NEXT
P→Next=cSTART→Next
cSTART=P
Item=Q→Info Time Complexity: O(N)
Free(Q)
Traversal of circular Linked List requires O(N) Time.
Return Item
END;
Space Complexity:O(1)
Circular Linked List—DELETE NODE at
Given Position
Case-1 When POS=1 and there is only one node in the list.
Case-2 When POS=1 and there are more than one node in the List.
Given Position
Case-3 When POS>1
Given Position
THANK YOU
Traverse & Insert Operation in Doubly
Linked List
By
Puneet Kumar Goyal

Assistant Professor
Doubly Linked List- Introduction
In Doubly Linked List, each node has three fields:

a) Backward Pointer: It contains the address of previous node.
b) Forward Pointer: It contains the address of next node.
c) INFO Field:It contains the actual value to be stored.
BACKW INFO FORW
node
Doubly Linked List- Introduction
Advantages:
✓ We can traverse in both directions i.e. forward as well
as backward.
✓ From current node, previous node can also be
accessed using backward pointer field.
Disadvantage:
✓ More memory is needed to implement as compare to
single linked list.
Doubly Linked List-Traversing
TRAVERSE_DLL(DATA, LINK, START) BACKW DATA FORW

Goto Step 4
END of IF
Doubly Linked List-Traversing
PTR=START
(b) PTR = PTR→FORW
Step-4 END
Doubly Linked List-INSERT new node as
First node
Case-1 When list is empty
Doubly Linked List-INSERT new node as
First node
Case-2 When list is not empty
Doubly Linked List-INSERT node as Last
Node
Case-1 WHEN LIST IS EMPTY
START
NULL
Doubly Linked List-INSERT node as Last
Node
Case-2 When list is not empty
Delete Operation in Doubly Linked List
By
Puneet Kumar Goyal

Assistant Professor
Doubly Linked List-Delete First node
Case-1 When there is only one
node in the list.
Doubly Linked List-Delete First node
Case-2 When there are more than one node in the list.
Doubly Linked List-Delete Last node
Case-1 When there is only
one node in the list.
Doubly Linked List-Delete Last node
Case-2 When there are more than one node in the list.

Unit-1 Notes - Data Structure

Uploaded by

Copyright:

Available Formats

Unit-1 Notes - Data Structure

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit-1 Notes - Data Structure

Uploaded by

Copyright:

Available Formats

Data Structure(KCS-301)

Introduction to Data Structures

Puneet Kumar Goyal

✓Why, Data Structure?

✓Operations on Data Structures

Ex- arrays, stack, queue, Tree, Graph etc..

Primitive Data Non-Primitive

Non-Primitive Data Structures:

• Let f be a nonnegative function and we say that f(n) is Big-O of

0 ≤ f(n) ≤ c g(n) for all n ≥ n0

• If f(n) = O(g(n)), we say that g(n) is an upper bound on f(n).

• We say that f(n) is Big-Theta of g(n), written as

0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n)

• Equivalently, f(n) = Θ(g(n)) if and only if f(n) =

0 ≤ c g(n) ≤ f(n) for all n ≥ n0

• If f(n) = Ω(g(n)), we say that g(n) is a lower bound on f(n).

To start the TV ,simply press ON button

ii) POP() → Remove an element from the top

iii) PEEK() → view the element which present at the top

iv) is Empty() → To check, whether stack is empty or not?

Puneet Kumar Goyal

Primitive Data Non-Primitive

Non-Primitive Data Structures:

✓Elements are inserted at one end called Rear and

✓It is collection of nodes where each node has two

Puneet Kumar Goyal

No. of elements in array= (UB-LB +1)

A[0][0] A[0][1] A[0][2]

A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2]

Row Index-0 Row Index-1

Therefore 2D array is a collection of 1D arrays which is again a

Address of A [ i1 ][ i2 ] = BA + eSize * [ ( i1 – LB1 ) + *R ( i2 – LB2 ) ]

(ii) Row Major Wise Calculation of above equation

Address of A [ i1 ][ i2 ] = BA + eSize * [ C * ( i1 – LB1 ) + ( i2 – LB2 ) ]

Puneet Kumar Goyal

A[0][0] A[0][1] A[0][2]

A[0][0] A[1][0] A[0][1] A[1][1] A[0][2] A[1][2]

Column Index-0 Column Index-1 Column Index-2

Therefore 2D array is a collection of 1D arrays which is again a

➢find the address of an array having row index i2 in

Puneet Kumar Goyal

TRAVERSE_SLL(START) INFO NEXT

Puneet Kumar Goyal

SEARCHING_SLL(ITEM, NEXT, START) DATA LINK

Step-1 [First check List is empty or not?]

Traverse & Insert Operation in Circular

Puneet Kumar Goyal

✓ A circular linked list is similar to single linked list

✓ By taking LAST pointer, insert a node as first or

Delete Operation in Circular Linked List

Puneet Kumar Goyal

Puneet Kumar Goyal

In Doubly Linked List, each node has three fields:

TRAVERSE_DLL(DATA, LINK, START) BACKW DATA FORW

Puneet Kumar Goyal

You might also like