DATA STRUCTURE

Group of data and well defined operations

In Python memory allocation and deallocation method is automatic as the Python
developers created a garbage collector for Python so that the user does not have to
do manual garbage collection.
Memory management in Python involves a private heap containing all Python objects
and data structures. The management of this private heap is ensured internally by
the Python memory manager. The Python memory manager has different
components which deal with various dynamic storage management aspects, like
sharing, segmentation, preallocation or caching.
Garbage Collection
Garbage collection is a process in which the interpreter frees up the memory when
not in use to make it available for other objects.
Assume a case where no reference is pointing to an object in memory i.e. it is not in
use so, the virtual machine has a garbage collector that automatically deletes that
object from the heap memory
There are two parts of memory:
stack memory
heap memory
The methods/method calls and the references are stored in stack memory and all the values
objects are stored in a private heap.
Work of Stack Memory
The allocation happens on contiguous blocks of memory. We call it stack memory allocation
because the allocation happens in the function call stack. The size of memory to be allocated is
known to the compiler and whenever a function is called, its variables get memory allocated on
the stack.
It is the memory that is only needed inside a particular function or method call. When a function
is called, it is added onto the program’s call stack. Any local memory assignments such as variable
initializations inside the particular functions are stored temporarily on the function call stack,
where it is deleted once the function returns, and the call stack moves on to the next task. This
allocation onto a contiguous block of memory is handled by the compiler using predefined
routines, and developers do not need to worry about it.
 WHAT IS DATA STRUCTURE?
Is a named group of data of different data types which is stored in a
specific way and can be processed as a single unit. A data structure has
well-defined operations, behaviour and properties.
Data structures are a way of organizing and storing data so that they
can be accessed and worked with efficiently. They define the
relationship between the data, and the operations that can be
performed on the data. There are many various kinds of data structures
defined that make it easier for the data scientists and the computer
engineers,to concentrate on the main picture of solving larger problems
rather than getting lost in the details of data description and access.
 DATA TYPE VS. DATA STRUCTURE
 DATA TYPE defines the type of values we can store and operations we can
perform. For example in int data type we cannot store decimal values, we
cannot multiply two string type values. It alsospecifies amount of
memory it will take.

 DATA STRUCTURE is physical implementation that clearly defines a way

of storing, accessing and manipulation of data stored in data structure.
Every data structure has a specific way of insertion and deletion like
STACK work on LIFO i.e. all operation will take from one end i.e. TOP
where as QUEUE works on FIFO i.e. item inserted first will be removed
first and new item will always added to the end of QUEUE.
 In python we will use LIST as a data structure.
TYPES OF DATA STRUCTURE
 Data structure can be classified into following two
types: Simple & Complex
 Simple Data structure : these are built from primitive data
types like integer, float, string or Boolean. Example:
Linear List or Array
 Complex Data structure : simple data structure can be combined in
various way to form more complex data structure. It is of two
types:
 Linear : are single level data structure i.e. in linear fashion to form a
sequence. Example : STACK, QUEUE, LINKED LIST
 Non-Linear: are multilevel data structure. Example: TREE and GRAPH.
DIAGRAM TO REPRESENT ALL DATA STRUCTURE
DATA
STRUCTURES

SIMPLE COMPLEX

Array or Linear Linear Non-Linear

List

Stack Queue Linked List Tree Graph

LINEAR LIST ARRAYS
 Refers to named list of finite number of n similar data
elements. Each of the data elements can be accessed by
its unique index/subscript position usually 0,1,2,3,…

 For example if the list mylist contains 10 elements then

first element will be mylist[0], second will be mylist[1]
and so on.
 Array can be Single Dimensional
or Multidimensional. In Python arrays
are
implemented through List data types as Linear
List or through Array module or through NumPy arrays.
STACK
 Allow to insert and delete items from one end only called
TOP.
 Stack works on LIFO principle. It means items added in list
will be removed first.
 Real life Example: Stack of Plates, Books, Bangles

 Computer based examples: Undo Operation, Function Call

etc.
QUEUE
 Allows insertion and deletion from different
end
i.e. insertion from REAR and deletion from
FRONT
 Queue works on FIFO principle i.e. item
added first will be removed first.
 Real life example: Queue of People for ticket

 Computer based example: Keyboard

typing, Printer etc.
OPERATIONS ON DATA STRUCTURE
OPERATIONS DESCRIPTION

INSERTION Addition of new data to data structure

DELETION Removal of data element from data structure

SEARCHING Finding specific data element in data structure

TRAVERSAL Processing all data elements one by one

SORTING
Arranging data elements in ascending or descending

order
MERGING
Combining elements of two similar data structure

to form a new data structure.

LINEAR LIST
 A linear data structure forms a sequence.
 When elements of linear structure are homogenous and are
represented in memory b means of sequential memory location are
called arrays.
 An Array stores a list of finite number(s) of homogenous  data
elements.
 When upper bound and lower bound of linear list are given,
its size can be calculated as :
 Size of List = Upper Bound - Lower Bound + 1

Index 0 1 2 3 4 5 6
values 10 20 30 40 55 70 45

 Size of above list = 6 – 0 + 1 = 7

SEARCHING : LINEAR AND BINARY SEARCHING

 Linear Searching: each element of linear list is compared

with the given item to be searched one by one. This
method traverse the linear list sequentially to located the
given item.
 For Linear Searching item need not be in any order, it
can be performed on random list.
 Linear Searching is suitable for small list only.
 Best Case: when item to be search is at
first position
 Worst Case: when item to be search is at
last position or not present
 Average Case: when item is somewhere in
list other than first or last position.
COMPLETE CODE: LINEAR SEARCH
def linearSearch(mylist,item): n =
len(mylist)
for i in range(n):
if item == mylist[i]:
return i
return None
Arr=[]
n = int(input("Enter how many items in List ")) for i in
range(n):
d = int(input("Enter value :"))
Arr.append(d)
key = int(input("Enter Value to Search :"))
pos = linearSearch(Arr,key) if
pos!=None:
print("Found at position
",pos+1)
else:
print("Not Found")
BINARY SEARCHING : DIVIDE AND RULE

 Data must be SORTED either in ascending or descending

order to search using binary method
 Searching Starts from the middle position. To find middle
position
 Mid = (lower_index + higher_index) / 2
 If middle value is equal to search element “SEARCH
SUCCESSFUL”
 If middle value if larger than search value, searching continues
towards left of middle position otherwise towards right side of
middle position. [ for data arranged in ascending order else vice
versa ]
 Takes less time compare to Linear searching
 Suitable for LARGE list
 Lets Search…
COMPLETE CODE: BINARY SEARCH
INSERTION IN LINEAR LIST
 Insertion of new item can be done by 2 ways:
 In unsorted list we can add item directly at the end of
list
 For sorted array, we have to first find the position where new
items is to be added, then shift all the elements from that
position one place down and create place for new item and
then insert the new item to that place.
 Let us take an example…
INSERTION IN SORTED ARRAY: INSERT 45
10 10 10
20 20 20
Correct
30 30 30
Position
40 40 40
for 45
50 45
60 50 50
70 60 60
70 70

Elements
Shifted down
from that After
position Insertion
INSERTION USING PYTHON APPROACH
 As we can observe Insertion of new item in sorted array
requires shifting of elements to make room and this is very
time consuming when list grows.
 It should be avoided using better approach like bisect,
available in bisect module.
 bisect.insort(list,newItem)
 The insort() function of bisect module inserts an item
in the sorted array, keeping it sorted.
 Bisect module offers another function bisect() which return
the appropriate index where new item can be inserted to keep
the order at it is.
 bisect.bisect(list,element)
 Note: bisect module works only on sequence arranged in
Ascending Order only.
PROGRAM: USING BISECT MODULE
import bisect
marks=[10,20,30,40,50,60,70,80]
print("\nCurrent list is :")
print(marks)
Item = int(input("Enter item to insert:")) pos
= bisect.bisect(marks,Item)
bisect.insort(marks,Item) print("\nItem
Inserted at Index :",pos) print("\nUpdated List
is :") print(marks)
BISECT MODULE
 As we know bisect module works only on Ascending order,
hence to make it for descending order:

 Firstreverse the list arranged in descending in

ascending order using reverse().
 Perform the insert operation
 Again reverse the list.
DELETION FROM SORTED LIST:
TRADITIONAL APPROACH
 To Delete item from sorted list we have to first find the
element position in List using Binary Searching
 Delete the item from list if search successful
 Shift all the items upwards to keep the order of list
undisturbed
 Reduce the List size by 1

 However in Python, we have to just delete the item and

rest of the work is automatically handled by Python i.e.
Shifting, reducing size etc.
 In Python we will use either remove(), del or pop() for
this purpose
DELETION OF AN ELEMENT
ANOTHER METHOD – SIMPLE AND SHORT
TRAVERSAL OF LINEAR LIST
 It involves processing of all elements one by one like:
 Printing of all items
 Searching item one by one
 Double each value of list etc.

 In nutshell, if we are accessing all elements one

by one for any reason, it is traversing.
EXAMPLE – 1 (PROGRAM TO DOUBLE THE LIST ELEMENT)

def DoubleIt(Arr):
for i in range(len(Arr)): #traversing all elements Arr[i]
*= 2
Arr=[10,20,30,40,50]
print("Current List :")
#traversing all elements
for i in Arr:
print(i)
DoubleIt(Arr)
print("After Update List :")
for i in Arr:
print(i)
 FEW FUNCTIONS: TRAVERSAL (FUNCTION TO
FIND SUM OF EVERY ALTERNATE ELEMENTS)
#Function to add alternate elements #Function to add element ending with digit 7

def AddAlternate(Arr):
def AddEnding7(Arr):
sum=0
sum=0
for i in range(len(Arr)): if i
for i in range(len(Arr)):
% 2 == 0:
if Arr[i] % 10
sum+=Arr[i]
== 7:
return sum
su
#Function to count how many even
values in list m
+
def CountEven(Arr): =
count=0 A
for i in rr
range(len(Arr)): [i
if Arr[i] % 2 == 0: ]
count+=1 return sum
return count #Function to swap adjacent elements

def SwapAdjacent(Arr):
SORTING A LINEAR LIST
 Sorting means arranging the list items in Ascending or Descending
order.
 Many Sorting algorithm which we can use for this purpose like:
Bubble, Selection, Insertion, Shell, Quick, Heap, Merge etc.
 In Class XI, we have already studied about 2 sorting methods:
Bubble and Insertion (PDF available in Class XI option of website)
 Bubble Sorting
 Insertion Sorting

 Comparison between Bubble and Insertions

NESTED/TWO DIMENSIONAL LIST IN PYTHON
In Class XI, we have already studied Nested List that a
List can have another list as a value. For e.g.
List1 = [1,2,3]
List2 = [10,20,List1]
print(List2)
Output: [10,20,[1,2,3]]

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

List2 10 20 1 2 3

print(List2) # [10,20,[1,2,3]]
print(List2[0]) # 10
print(List2[2][0]) #1
TWO DIMENSIONAL LIST
 Is a list having all elements as list of same shape for e.g.
 Mylist=[[20,40,60],[5,10,15],[9,18,27]]

20 40 60
5 10 15
9 18 27

 It is a 2 – D List with 3 rows and 3 columns

 First value will be at index [0][0] and last will be [2][2]
mylist = [[1,2,3],[4,5,6],[7,8,9]]
print(len(mylist)) # no. of rows
print(len(mylist[0])) # no. of columns

 Ragged List: sometimes list contains another list of different

shapes for e.g.
mylist = [[20,40,60],[4,5]]
Here first row contains 3 columns and 2 row contains 2 columns
CREATING AND PRINTING OF 2-D LIST
SLICE OF 2-D LIST
mylist=[[20,30,40],[21,22,23],[100,150,200],[19,21,40]]
print(mylist[:2])
print(mylist[2:])
print(mylist[2:][:1])
Matrix
1 2 3 1 2
4 5 6 4 5
7 8 9 7 8

3x3 3x2

1 2 3
4 5 6

2x3
Matrix addition
mat1=[[1,2,3],
[3,4,5]]
mat2=[[1,2,3],
[3,4,5]]
sum1=[[0,0,0],[0,0,0]]

for i in range(2):
for j in range(3):
sum1[i][j]=mat1[i][j]+mat2[i][j]

for i in range(2):
for j in range(3):
print(sum1[i][j], end=' ')
print()
Matrix Subtraction
mat1=[[4,5,6],[3,4,5]]
mat2=[[1,2,3],[3,4,5]]
sum1=[[0,0,0],[0,0,0]]

for i in range(2):
for j in range(3):
sum1[i][j]=mat1[i][j]-mat2[i][j]

for i in range(2):
for j in range(3):
print(sum1[i][j], end=' ')
print()
Matrix Multiplication
A = [[12, 7, 3],
[4, 5, 6],
[7, 8, 9]]
# take a 3x4 matrix
B = [[5, 8, 1],
[6, 7, 3],
[4, 5, 9]]
result = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
# iterating by row of A
for i in range(len(A)):
# iterating by coloum by B
for j in range(len(B[0])):
# iterating by rows of B
for k in range(len(B)):
result[i][j] += A[i][k] * B[k][j]
for r in result:
print(r)
1.question:

def dispdiagonal(l,m,n):
for I in range(m):
for j in range(n):
if (i==j or i+j==m-1 ) and l[i][j]%2!=0:
print(l[i][j], end=‘ ‘)
print()
l=[[1,2,3],[4,5,6],[7,8,9]]
dispdiagonal(l,3,3) 3.question:

def dispdiagonal(l,m):
l1=[[0,0,0],[0,0,0],[0,0,0]]
for I in range(m):
for j in range(n):
if ( i+j<=m-1 ):
l1[i][j]=l[j]
else:
l1[i][j]=0

l=[1,2,3]
dispdiagonal(l,3)
1. WRITE A FUNCTION IN PYTHON TO ACCEPT A NESTED LIST AS ARGUMENT AND
DISPLAY THE DIAGONAL ELEMENTS
EX. IF THE LIST CONTAINS
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
THEN THE OUTPUT SHOULD BE
LEFT DIAGONAL : 1 2 3 4
RIGHT DIAGONAL : 4 3 2 1
2. WRITE A FUNCTION IN PYTHON TO ACCEPT A NESTED LIST AS ARGUMENT AND
DISPLAY THE ODD NUMBERS THAT LIE IN THE DIAGONAL.
3. WRITE A FUNCTION IN PYTHON WHICH ACCEPTS A LIST OF NUMBERS AS
ARGUMENTS AND CONVERT IT INTO A NESTED LIST AS FOLLOWS
IF THE LIST CONTAINS 1,2,3,4
THEN THE NESTED LIST SHOULD BE CREATED AS
1,2,3,4
1,2,3,0
1,2,0,0
1,0,0,0