DATA S T R U C T U R E

Group of data and well defined operations

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.
D ATA T Y P E VS . DATA S T RU C T U R E
 DATA T Y P E 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 also specifies
amount of memory it will take.
 DATA S T R U C T U R E 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 S TAC K work on L I F O i.e. all operation
will take from one end i.e. TOP where as Q U E U E
works on F I F O 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 L I S T as a data structure.
TYPES OF DATA STRUCTURE
 Data structure can be classified into following
two types:
⚫ 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 : STAC K , Q U E U E , L I N K E D
LIST
 Non-Linear: are multilevel data structure. Example: T RE E

and G R AP H .
D I A G R A M TO R E P R E S E N T A L L DATA S T R U C T U R E

DATA
S T RU C T U R E S

S I M PLE 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 NumPy arrays.
STACK
 Allow to insert and delete items from one end
only called TOP.
 Stack works on L I F O 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 REA R and deletion from
F RO N T
 Queue works on F I FO 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.
LI NKE D LIST
 It is dynamic data structure i.e. size of Linked
List is not pre-known before the execution of
program. It takes memory as per requirement
during runtime and every item allocated
dynamically will be known as N O D E .
 N O D E contains 2 parts: (1) I N F O part stores the
actual data to store like roll no. name, marks etc.
and (2) L I N K holds the address of next allocated
node in memory creating chain of linked items
 Singly Linked List hold the address of next node
and last Node will point to N U L L whereas
Doubly Linked List holds the address of next as
well as previous node allows both forward and
backward movement.
TREES
 Are multilevel data structure having hierarchical
relationship among its elements called nodes.
 Topmost node is called the root of tree
and bottommost nodes are called leaves of tree.
 Each of the node holds the address of nodes below

it.
 It will never contains a closed loop
OPERATIONS ON DATA STRUCTURE
O P E R AT I O N S DESCRIPTION

I N SERT I O N Addition of new data to data structure

DELETION Removal of data element from data structure

S E A RC H I N G Finding specific data element in data structure

TRAV ERSAL Processing all data elements one by one

S O RT I N G Arranging data elements in ascending or

descending order

M E RG I N G 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

S E A RC H I N G : L I N E A R AND BINARY
S E A RC H I N G
 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.
LINEAR SEARCH FUNCTION
def LSearch(Arr,Item):
for i in range(len(Arr)):
if Item == Arr[i]:
return True
return False
CO MP L ETE I N EA R SEARC
CODE: L
def linearSearch(mylist,item):
H
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")
B I NA RY S E A R C H I N G : D I V I D E AND RULE

 Data must be S O R T E D 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 L A R G E list
 Lets S e a rc h …
BINARY S EA RC H FUNCTION
def BSearch(mylist,item):
low = 0
high = len(mylist)-1
while(low<=high):
mid = (low+high)//2 if
mylist[mid]==item:
return mid
elif mylist[mid]>item:
high = mid - 1
else:
low = mid + 1
return -1
C O M P L E T E C O D E : B I NARY
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 Correct 20 20
30 Position 30 30
for 45
40 40 40
50 45
60 50 50
70 60 60
70 70

Elements
Shifted down
from that After
position Insertion
INSERTION U S I N G 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: U S I N G 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:
⚫ First reverse the list arranged in
descending in ascending order using
reverse()
⚫ Perform the insert operation
⚫ Again reverse the list.
DELETION FROM SORTED
LIST:
TRADITIONAL A P P ROAC H
 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
D E L E T I O N O F A N E L E M E NT
LI ST : S O RT E D
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.
EXA MP L E – 1 (PROGRAM TO D O U B L E THE
LIST
ELEM ENT )
def DoubleIt(Arr):
for i in range(len(Arr)): #traversing all
elements Arr[i] *= 2

Arr=[10,20,30,40,50]
print("Current List :")
for i in Arr: #traversing all elements
print(i)

DoubleIt(Arr)
print("After Update List :")
for i in Arr:
print(i)
 FEW FUNCTIONS: TRAVERSAL (FUNCTION TO
F I N D S U M O F E V E RY A LT E R NAT E E L E M E N T S )
#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)): for i in
if i % 2 == 0: range(len(Arr)):
sum+=Arr[i] if Arr[i]
return sum % 10 ==
#Function to count how many
7:
even values in list s
u
def CountEven(Arr): m
count=0 +
for i in =
range(len(Arr)): A
if Arr[i] % 2 == 0: r
count+=1 r
return count [
i
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

LIST
COMPREHENSIONS
 We have already studied how to create a list i.e.
either by assigning comma separated values in
square bracket to list variable or by using
append() in loop.
e.g. mylist = [4,8,12,16,20] Or by loop
 There is another method of creating list called

list comprehensions.
 A list comprehension is a shorthand for list

creating for loop in the form of single statement.

 Example 1: to create list using
list comprehension:
mylist = [i*4 for i in range(1,6)]
print(mylist)
EXAMPLE - 2
mylist = [i for i in range(1,101) if i%2==0]
print(mylist)

EXAMPLE -
3
lst2 = [i if i%2==0 else '@' for i in range(1,101) ]
print(lst2)

EXAMPLE – 4 : FOR
CLARITY
lst2 = [(i if i%2==0 else '@‘) for i in range(1,101) ]
print(lst2)
LIST COMPREHENSION FOR NESTED FOR
LOOP
Example: Nested Loop
Arr = [ ]
for i in [10,20,30]:
for j in [5,10,15]:
Arr.appen
d(i+j)
print(Arr)

Example : using List

Comprehension
Arr = [ i + j for i in
[10,20,30] for j in
ADVANTAGES OF LIST COMPREHENSIONS
 Code reduction : A code of 3 or more lines gets
reduced to single line.
 Faster code procession : list comprehensions are

executed faster than their equivalent for loops

because:
⚫ Python will allocate the list’s memory before adding
the elements to it, instead of having to resize on
runtime
⚫ Also call to append() function gets avoided thus
reducing the function overheads.
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]]
List2 [0] [1] [2][0] [2][1] [2][2]
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
TWO DIMENSIONAL LIST
 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
S L I C E 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])