Data Structures
➢ A Data Structure is a way of giving Structure to the Data.
➢ Organizing the data in the memory location in different ways are
called Data Structure.
➢ A Data Structure is a Particular way (format) of storing,
organizing, transforming and retrieving data.
➢ Data Structure are building blocks (or) raw material for any
software programs.
➢ Data items is a unit of data stored in a field.
➢ Raw data is a data that has not been processed for use.
E.g.:
Student Marks(Total) → Data item.
(tamil, eng, maths, social, science ,computer science) → raw data
Structure of DS
➢ Lists, Tuples, Dictionaries, Sets are built in Linear Data Structures.
➢ In Primitive data structure single memory location which hold
the single value. E.g.
➢ In Non-Primitive data structure group of data(values)that stored
in a memory location with a unique control common variable
name.
➢ Linear Data Structures: It’s a single level Data Structures. Here
the data is in the form of sequential manner.
E.g. Array, List, Tuple, Dictionaries, Stack, Queue, Linked List.
➢ Non-Linear Data Structures: It’s a multi level Data Structures.
Here the data is in the form of random manner(hierarchical
manner).
E.g. Trees, Graphs. number=237
Linear Data Structures
Array/Linear List:
➢ An array is a collection of similar data items, that are stored under a
common variable name in sequential manner.
Eg:
arr=[‘ram’, ‘rakesh’, ‘ravi’, ‘ramesh’, ‘rahul’]
arr2=(2,4,6,8,10,12,14,16,18)
arr3=[3.3,5.5,7.7,9.9,11.11,13.13,’RAM’,100]
➢ Array can be one dimensional, two dimensional and multi dimensional.
arr2[0]=2,arr2[5]=12,arr2[8]=18
Operation in Array/Linear List:
→Insertion
→Deletion
→Search
→Traversal
→Sorting
→Updating
Stack:
➢ Ordered collection of Homogeneous(similar) data elements.
➢ Last In First Out (LIFO) or First In Last Out Technique is used
here.
➢ Both Insertions and Deletions take place only at one end called
“TOP”.
Operation in Stack:
→Insertion/Push
→Deletion/Pop
→Display
Queue:
➢ Ordered Collection of Homogeneous(similar) data elements.
➢ First in First Out (FIFO) technique is used here.
➢ Insertions take place at the Rear end and Deletions take place at the
Front end.
Operation in Queue:
→Insertion/Enqueue
→Deletion/Dequeue
→Display
Linked Lists:
➢ Linked lists are special lists a data elements linked with one another
data elements.
➢ The elements are denoted by Nodes.
➢ Nodes has 2 fields[data(information)filed & address(reference/link)]filed
Types of Linked Lists:
→Singly Linked List
→Doubly Linked list
Singly Linked List:
➢ Single Linked List, the individual element is called as "Node".
Every "Node" contains two fields, data field, and the address field.
➢ The data field is used to store actual value of the node and address
field is used to store the address of next node in the sequence.
➢ In SLL we can Access LL Only Single Direction.
Doubly Linked List:
➢ Double Linked List, the individual element is called as "Node".
Every "Node" contains three fields, 1 data field and 2 address field.
➢ The data field is used to store actual value of the node and address
field is used to store the address of next node in the sequence.
➢ In DLL we can Access LL in Both Single Direction.
Non-Linear Data Structures:
Trees:
➢ Tree is a hierarchical data structure which stores the information
naturally in the form of hierarchy style.
➢ It represents the nodes connected by edges.
Non-Linear Data Structures:
Graphs:
➢ A Graph consists of a finite set of vertices(or nodes) and set of
Edges which connect a pair of nodes.
Linear List Insert :
arr=[8,17,18,19,22,25,30]
def LL(ar,item): # arr,27
print("Original List is:",arr)
size=len(ar) #7
item=int(input("Enter the Insert Element:"))
if item<ar[0]: # 27<8
pos=LL(arr,item) # 27
return 0
shift(arr,pos)
else:
arr[pos]=item #27
pos=-1
print("The New List After
for i in range(size-1): #5,6
Insertion:",item,"is:",arr)
if(ar[i]<=item and item<ar[i+1]): #25<=27 and 27<30
Output:
pos=i+1 #6
8 17 18 19 22 25 ___ 30
break
0 1 2 3 4 5 6 7
if(pos==-1 and i<=size-1):
pos=size
return pos
def shift(ar,pos): #arr,6
[Link](None) #add empty element at the end
size=len(ar) #8
i=size-1 #7
while i>pos: #6>6
ar[i]=ar[i-1] #ar[7]=ar[6]
i=i-1
Linear List Insert : Output:
def insert(list, n):
index = len(list)
for i in range(len(list)):
if list[i] > n:
index = i
break
if index == len(list):
list = list[:index] + [n]
else:
list = list[:index] + [n] + list[index:]
return list
list=eval(input("Enter an Ordered Linear List with Integer Elements: "))
n =int(input("Enter the Insert Element:"))
print(insert(list, n))
Linear List Insertion using Bisect
import bisect
mylist=[10,20,30,40,50,60,70]
print('The List in the Sorted Order is:')
print(mylist)
ITEM=int(input('Enter the New Element to be Inserted:'))
ind=[Link](mylist,ITEM) # 4 # [Link](existing arr,new element)
[Link](mylist,ITEM) # [Link](45)
print(ITEM,'Inserted at the Index',ind)
print('The List after the Inserting the New Element is:')
print(mylist)
Output:
Linear List Delete:
def LLD(ar,item): #arr,32
beg=0 Output:
last=len(ar)-1 # 8
while(beg<=last): # 5<=8
mid=int((beg+last)/2) #6
if arr[mid]==item:
return mid #32==32
elif arr[mid]<item:
beg=mid+1 # 24<32
else:
last=mid-1
else:
return false
arr=[12,15,18,21,24,27,32,40,45]
print("Original List:",arr)
item=int(input("Enter Element to be Deleted:"))
pos=LLD(arr,item) # 6
if pos:
del arr[pos] # del arr[6]
print("The List After Deleting",item,"is:",arr)
else:
print("Sorry!",item,"Not Found in Array Arr.")
Linear List Traversal:
def traverse(ar):
size=len(ar)
for i in range(size):
print(ar[i],end=" ")
arr=[12,15,18,21,24,27,32,40,45]
print("Original List:",arr)
traverse(arr)
Output:
Linear List/Array
Linear Search:
def LSearch(ar,item):
i=0
for i in range(len(ar)):
if ar[i]==item:
return i
return -1
ar=[6,3,8,7,9,12,45,11,22,2,1,5]
print("Elements in the List AR :",ar)
item=int(input("Enter the Element to Search:"))
Result=LSearch(ar,item)
if Result==-1:
print("Given ! Element Not Found")
else:
print("Element",item,"Found at Index:",(Result),"&at Position:",Result+1)
Binary Search:
arr=eval(input("Enter an Ordered Linear List with Integer Elements: "))
search=int(input("Enter the Search Element: "))
low,high=0,len(arr)-1
while high>=low:
mid=int((low+high)/2)
if arr[mid]==search:
print("Element Found at Index:",mid,“ & at Position:",mid+1)
break
elif arr[mid]>search:
high=mid-1
else:
low=mid+1
else:
print("Element Not Found at the Linear List")
Outputs:
Binary Search:
def BinarySearch(arr,low,high,x):
if low>high: Outputs:
return -999
mid=int((low+high)/2)
if arr[mid]==x:
return mid
elif arr[mid]>x:
high=mid-1
return BinarySearch(arr,low,high,x)
else:
low=mid+1
return BinarySearch(arr,low,high,x)
arr=[12,15,18,21,24,27,32,40,45]
search=int(input("Enter the Search Element:"))
result=BinarySearch(arr,0,len(arr)-1,search)
if result>-1:
print(search,"Found at the Index:",result)
else:
print("Sorry!",search,"Not Found in Array Arr.")
Linear List Sort
l=eval(input("Enter a Linear List: "))
print("Original List: ",l)
for k in range(0,len(l)-1):
for i in range(0,len(l)-k-1):
if (l[i]>l[i+1]):
l[i],l[i+1]=l[i+1],l[i]
print(l)
Output:
Linear List Insertion Sort Output:
list=[15,3,17,5,6,2,55,18]
print("Original List is :",list)
for i in range(1,len(list)):
key=list[i]
j=i-1
while j>=0 and key<list[j]:
list[j+1]=list[j]
j=j-1
else:
list[j+1]=key
print("List After Insertion Sorting: ",list)
LIST
list=[8,30,18,25,30,17,19,2,26,22]
print("Original List is:",list,"\n")
print("List Index, Indexing Value '18' :",[Link](18),"\n")
print("List Append, Appending Value[2020]:"), [Link](2020),"\n")
exd=[1999,2000,2001]
print("List Extend, Extending Values[1999,2000,2001]:",[Link](exd),"\n")
print("List Insert, Insertion Value '1991' :",[Link](5,1991),"\n")
list[7]=10
print("List Updation, Updating Value list[7]= 10 :",list,"\n")
print("List Count,Find Position of Value '1999':",[Link](1999),"\n")
print("List Length,Find Length of List'list':",len(list),"\n")
print("Updated List1 is:",list,"\n")
print("List Index Base Deletion, Pop a Value[11]:",[Link](11),"\n")
print("List Value Base Deletion, Romove a Value[2001]:",[Link](2001),"\n")
print("Updated List2 is:",list,"\n")
print("List Slicing,List [3:-3] : ",list[3:-3],"\n")
O=list[2:5]
print("List Slicing ,List [2:5] : ",O,"\n")
print("List Slicing,List [2:10:2] : ",list[2:10:2],"\n")
print("List Replication, [O*2] : ",O*2,"\n")
J=O+exd
print("List Joining [O+exd]",J,"\n")
print("List Sort [list]",[Link](),"\n",J)
print("Updated List3 is:",list,"\n")
print("List Clear[list]:",[Link]())
print("Updated List4 is:",list,"\n")
(Output)
Stack
Input Values: 2,5,7,1,21 (LIFO Technique)
Stack: PUSH & POP
def isEmpty(stk):[8,30,18,25] def push(stk,item): #[8,30,18],25
if stk==[]: [Link](item)
return True top=len(stk)-1 #3
else: def Pop(stk):[8,30,18,25]
return False if isEmpty(stk):
def Display(stk):[8,30,18,25] return "UnderFlow"
if isEmpty(stk):[8,30,18,25] else:
print("Stack is Empty") item=[Link]()
else: if len(stk)==0:
top=len(stk)-1 top=None
print(stk[top],"<---Top") else:
for a in range(top-1,-1,-1): top=len(stk)-1
print(stk[a]) return item
Stack: PUSH & POP
Stack=[] elif ch==2:
top=None item=Pop(Stack)
while True: if item=="UnderFlow":
print("Stack Operations") print("UnderFlow!
print("[Link]") Stack is Empty!")
print("[Link]") else:
print("[Link]") print("Popped Item is :",
item)
print("[Link]")
elif ch==3:
ch=int(input
Display(Stack)
("Enter Your Choice(1-4):"))
elif ch==4:
if ch==1:
break
item=int(input
else:
("Enter the Item:"))
print("Invalid Choice!!!")
push(Stack,item)
Output Push:
Output Pop:
Application of Stack:
➢ Expression Evolution
➢ Expression Conversion
Expression Conversion:
❑ Infix Expression = A+B(Operator is B/W Two Operands)
❑ Postfix Expression = AB+(Operator Follows the 2 Operands)
❑ Prefix Expression = +AB(Operator Precodes the 2 Operands)
Hierarchy/Precedence Operator:
▪ ()[]
▪ $,^
▪ *,/,%
▪ +,
Left→Right
Expression Evolution:
Infix to Postfix:
Infix to Prefix:
Queue
Input Values: 18,30,17,19 (FIFO Technique)
Queue: Enqueue,Dequeue
def isEmpty(Qu):
if Qu==[]: def Enqueue(Qu,item): # [18,30],17
return True [Link](item) #[18,30,17]
else: if len(Qu)==1:
return False front=rear=0
def Display(Qu): else:
if isEmpty(Qu): rear=len(Qu)-1 #3
print("Queue is Empty") def Dequeue(Qu):
elif len(Qu)==1:
if isEmpty(Qu):
print(Qu[0],"<---Front,Rear")
return"UnderFlow"
else:
else:
front=0
rear=len(Qu)-1 item=[Link](0)
print(Qu[front],"<---Front") if len(Qu)==0: #SingleEleinQU
for a in range(1,rear): front=rear=None
print(Qu[a]) return item
print(Qu[rear],"<---Rear")
Queue: Enqueue,Dequeue
Queue=[] elif ch==2:
front=None item=Dequeue(Queue)
while True: if item=="UnderFlow":
print(“Queue Operations") print("UnderFlow!Queue
print("[Link]") is Empty!")
print("[Link]") else:
print("[Link]") print("DeQueue-ed Item
print("[Link]") is :",item)
ch=int(input("Enter Your elif ch==3:
Choice(1-4):")) Display(Queue)
if ch==1: elif ch==4:
item=int(input("Enter the break
Item:"))
else:
Enqueue(Queue,item)
print("Invalid Choice!!!")
Output Enqueue:
Output Dequeue:
Circular Queue:
❑ Circular queues are the queues implemented in circular form rather
than a straight line.
❑ These are used in programming languages that allow the use of
fixed size linear structures(such as C/C++ etc.)as queues.
❑ Circular queue avoids the wastage of space in a regular queue
implementation using arrays.
❑ Infixed size linear queues after some insertion & deletion, some
unutilized space lies in the “beginning" of the queue. To overcome
such a problems, circular queues are used that overcome the
problem of unutilized space in fixed size linear queues.
❑ Python lists are dynamic structure that can grow and shirk when
needed, thus you don’t need circular queues generally when you are
implementing queues through python lists.
DeQueue:
❑ Dequeue are refined queues in which elements can be
added/removed at either(both)end but not in the middle.
❑ Input Restricted Deque:
❑ Its allows insertions at only one end but it allow deletions in both
ends of the lists.
❑ Output Restricted Deque :
❑ Its allows insertions at both ends of the lists and deletion at only one
end of the lists.