What is Data Structures?

A data structures is a way of organizing

and storing data in a computer so that it
can be accessed and used efficiently.

Why need Data Structures?

Data structures are needed to efficiently
organize, store, and manipulate data,
which improves a program's
performance, speed, and memory
utilization.

Types of Data Structures

1. Primitive Vs Non-Primitive Data
Structures
Primitive Data Structures:
These are basics, fundamental data types directly supported by a
programming language. Examples: int , float , string ,
boolean , complex .
Non-Primitive Data Structures:
These are more complex data structures derived from primitive
data structures and used to store collection of data items. They
focus on organizing and managing groups of data. Examples:
Arrays , Linked Lists , Stack , Queues , Trees , Graphs ,
Hash Tables .

2. Linear Vs Non-Linear Data Structures:

Linear Data Structures:
In Linear Data Structures, data elements are arranged in
sequentially or in a linear order, one after another. Examples:
Array , LinkedLists , Stack , Queues .

Non-Linear Data Structures:

In Linear Data Structures, data elements are not arranged in
sequentially. They represents hierarchial or networked
relationships where an elements can be connected to multiple or
other elements. Examples: Trees , Graphs .

3. Static Vs Dynamic Data Structures:

Static Data Structures:
Have a fixed memory size that is allocated at a compile time and
can't be changed during runtime. Examples: Array .

Dynamic Data Structures:

Have a flexible memory size that can be adjusted (increased or
decreased) during runtime. Examples: Linked Lists , Trees ,
Graphs .

4. Homogeneous Vs Non-Homogeneous
Data Structures:
Homogeneous Data Structures:
Store data elements of the same data type. Examples: an array
of integers.

Non-Homogeneous Data Structures:

Can store data elements of different data types. Examples: a
referential array which contains different types of elements.

Application of Data Structures

1. Database Management System (DBMS)
Data structures like B-trees, hash tables, and indexed sequential
access methods (ISAM) are crucial for efficient data storage,
indexing, and retrieval in databases.

2. Operating Systems
Operating systems utilize data structures like queues for process
scheduling, stacks for managing function calls and memory
allocation, and linked lists for managing file systems and free
memory blocks.

3. Compiler Design
Compilers employ data structures such as symbol tables to store
information about variables and functions, abstract syntax trees
(ASTs) to represent the structure of source code, and hash tables
for efficient symbol lookup.

4. Computer Graphics
Data structures like trees (e.g., k-d trees, octrees) and graphs are
used to represent and manipulate geometric objects, manage
spatial data, and optimize rendering processes in computer
graphics applications.

5. Networking
Graphs are extensively used to model network topologies,
represent routing paths, and implement routing algorithms. Queues
are used for managing data packets in network communication.

6. Artificial Intelligence and Machine Learning

Data structures like decision trees are used for classification and
regression tasks. Graphs are used to represent relationships in
knowledge graphs and neural networks. Hash tables are used for
efficient data storage and retrieval in various AI algorithms.

7. Navigation Systems
Graphs are used to represent road networks, and algorithms like
Dijkstra's or A* search, often implemented with priority queues, are
 used to find optimal routes.

8. File Systems
Data structures like trees (e.g., directory trees) and linked lists
(e.g., for file allocation tables) are used to organize and manage
files and directories on storage devices.

What is Array?
Array is a linear data structure where all elements are
arranged sequentially. It is a collection of elements of
same data type stored at contiguous memory locations.

In [12]: from array import array

arr = array('i',[10,20,30,40])

print(arr)

## add element
arr.append(50)
print('After append: ',arr)

## insert at index
arr.insert(1,15)
print('After insert: ',arr)

## update at index
arr[2] = 25
print('after update: ',arr)

## Remove element
arr.remove(15)
 print('After remove 15: ',arr)

## Access and loop

for i in arr:
print(i,end=' ')

array('i', [10, 20, 30, 40])

After append: array('i', [10, 20, 30, 40, 50])
After insert: array('i', [10, 15, 20, 30, 40, 50])
after update: array('i', [10, 15, 25, 30, 40, 50])
After remove 15: array('i', [10, 25, 30, 40, 50])
10 25 30 40 50

Array Vs List In Python

1. List are Dynamic but arrays are fixed size.
2. List are Heterogeneous(store different types of elements) but arrays are
Homogeneous (store same types elements).
3. Arrays are faster comparison than arrays.

What is Dynamic Array?

A Dynamic Array is an array that can automatically grow or shrink
in size at runtime.

What is Referential Array?

A Referential Array is an array that doesn’t store actual data values
directly — instead, it stores references (memory addresses or
pointers) to the real data objects stored elsewhere in memory.

In Python
All Python lists are implemented as dynamic referential
arrays:
The list grows dynamically (Dynamic Array behavior)
Stores references to Python objects (Referential Array concept)

🧩 How Python List Stores Different Types of

Elements
A Python list is a referential array.
It doesn’t store actual values — it stores references (pointers) to objects in
memory.
 Since every element is just a reference, it can point to any data type —
int , str , float , list , etc.

✅ That’s why lists can hold mixed data types.

In [3]: L = [1,'hello',2,'python',3.14,True]

for num in L:
print(num, 'at Address: ',id(num))

1 at Address: 140705501639592
hello at Address: 2880318671584
2 at Address: 140705501639624
python at Address: 2880223635776
3.14 at Address: 2880320665968
True at Address: 140705500754352

⚙️Dynamic Array Behaviour

Python lists are dynamic arrays — they can grow or shrink automatically.
When you append() and the list is full:
A new, larger array is created.
Old references are copied into it.
The new element is added.
The list doesn’t resize every time — it grows by ~1.125x–2x to stay efficient.
-This makes append() operation amortized O(1).

In [33]: L = ['hello','python',10,20,30,3.4,True]

## append: add in a last

L.append(False)

## insert: add in specified position

L.insert(2,'world')

## pop: delete last element

L.pop()

## remove: removed by value

L.remove('python')

## del : remove specified index value

del L[0]

## access and looping

for num in L:
print(num,end = ' ')

## Searching

print(L.index(30))
 ## Sorting

L1 = [10,44,32,11,65,71,17]

L1.sort()

print(L1)

## Indexing

print(L1[0])
print(L1[-1])

## Slicing

## reverse elements
print(L1[::-1])

## using rev method

# L1.reverse()

world 10 20 30 3.4 True 3

[10, 11, 17, 32, 44, 65, 71]
10
71
[71, 65, 44, 32, 17, 11, 10]

List Implementation From Scratch

In [34]: import ctypes

In [198… class List:

def __init__(self):
# capacity of array
self.size = 1
# how many elements are stored in current
self.n = 0
# create ctypes array with self.size
self.A = self.__make_array(self.size)

def __len__(self):
return self.n

def __str__(self):
res = ''
for i in range(self.n):
res = res + str(self.A[i]) + ','
return '[' + res[:-1] + ']'

def append(self,item):
# first check array is full or not
if self.size == self.n:
# full h - resize array
self.__resize_array(self.size*2)
 # jagah h
self.A[self.n] = item
self.n += 1

def pop(self):
if self.n == 0:
return 'List Empty'
print(self.A[self.n-1])
self.n -= 1

def __getitem__(self,index):

## slicing
if isinstance(index,slice):
start,stop,step=index.indices(self.n)
result = [self.A[i] for i in range(start,stop,step)]
return result

# for negative indexing

if index<0:
index += self.n

if 0<= index < self.n:

return self.A[index]
return 'Index not Found'

def __delitem__(self,pos):
if 0 <= pos< self.n:
## delete
for i in range(pos,self.n-1):
# shifting
self.A[i] = self.A[i+1]
self.n -= 1

# searching
def index(self,value):
for i in range(self.n):
if self.A[i]==value:
return i
return 'Not Found'

# sorting
def sort(self):
for i in range(self.n):
for j in range(0,self.n-i-1):
if self.A[j]>self.A[j+1]:
self.A[j],self.A[j+1] = self.A[j+1],self.A[j]

# insert
def insert(self,pos,value):
if self.size==self.n:
self.__resize_array(self.size*2)
## agar jagah h
for i in range(self.n,pos,-1):
# shifting
 self.A[i] = self.A[i-1]

self.A[pos]=value
self.n +=1

# remove
def remove(self,value):
# find index position
pos = self.index(value)

if type(pos)==int:
# if index found
self.__delitem__(pos)
else:
# index not found
return pos

# extend
def extend(self,iterable):
for item in iterable:
if self.n == self.size:
self.__resize_array(self.size*2)
self.A[self.n] = item
self.n += 1

# merge
def merge(self,other):
merged = List()
# all elements from list 1
for i in range(self.n):
merged.append(self.A[i])
# all elements from list2
for i in range(len(other)):
merged.append(other[i])
return merged

# reverse
def reverse(self):
start = 0
end = self.n - 1
while start<end:
self.A[start],self.A[end] = self.A[end],self.A[start]
start += 1
end -= 1
return self

# min elements
def min(self):
min_val = self.A[0]
for i in range(self.n):
if self.A[i]<min_val:
min_val = self.A[i]
return min_val

# max elements
def max(self):
 max_val = self.A[0]
for i in range(self.n):
if self.A[i]>max_val:
max_val = self.A[i]
return max_val

# sum of elements
def sum(self):
sum = 0
for i in range(self.n):
sum += self.A[i]
return sum

## advanced function
## 1.count elements frequency

def count(self,item):
count = 0
for i in range(self.n):
if self.A[i]==item:
count+=1
return count

# 2.remove duplicates elements

def remove_duplicates(self):
seen = set()
i = 0
while i<self.n:
if self.A[i] in seen:
for j in range(i,self.n-1):
# shift elements
self.A[j] = self.A[j+1]
self.n -= 1
else:
seen.add(self.A[i])
i+=1

def __make_array(self,capacity):
# create ctypes array with capacity
return (capacity*ctypes.py_object)()

def __resize_array(self,new_capacity):
# create an new array with double size
B = self.__make_array(new_capacity)
# update capacity
self.size = new_capacity

# copies all elements to new array

for i in range(self.n):
B[i] = self.A[i]

# re-assign B to A
self.A = B
In [199… L = List()

## append elements
L.append(71)
L.append(12)
L.append(33)
L.append(46)
L.append(25)

print('List: ',L)
print('Length: ',len(L))
print('Index of 4: ',L.index(4))
print('First Element: ',L[0])
print('Last Element: ',L[-1])
L.sort()
print('Sorted Array: ',L)

## insert element at index

L.insert(1,91)
L.insert(3,44)
print('after insert: ',L)

# delete item at index

del L[0]
print('after delete: ',L)

## remove
L.remove(44)
print('after remove: ',L)

## extend list
L.extend([115,116])
print('after extend: ',L)

## merged list
merged_array = L.merge([44,55,66])
print('merged array: ',merged_array)

## reverse list
print('reverse array: ',L.reverse())

# min, max and sum functions

print('Min Elements: ',L.min())
print('Max Elements: ',L.max())
print('Sum of Elements: ',L.sum())

# add some duploicates for counting

L.append(116)
L.append(115)
L.append(71)
L.append(71)

print('Count 71: ',L.count(71))

print('Count 115: ',L.count(115))
print('Count 1158: ',L.count(1158))
 print('Duplicate Array: ', L)

L.remove_duplicates()
print('After Remove Duplicated: ',L)

## binary search
print('Binary Search element-116 : ',L.binary_search(115))

List: [71,12,33,46,25]
Length: 5
Index of 4: Not Found
First Element: 71
Last Element: 25
Sorted Array: [12,25,33,46,71]
after insert: [12,91,25,44,33,46,71]
after delete: [91,25,44,33,46,71]
after remove: [91,25,33,46,71]
after extend: [91,25,33,46,71,115,116]
merged array: [91,25,33,46,71,115,116,44,55,66]
reverse array: [116,115,71,46,33,25,91]
Min Elements: 25
Max Elements: 116
Sum of Elements: 497
Count 71: 3
Count 115: 2
Count 1158: 0
Duplicate Array: [116,115,71,46,33,25,91,116,115,71,71]
After Remove Duplicated: [116,115,71,46,33,25,91]
after sorted: <__main__.py_object_Array_16 object at 0x0000029EA1A35550>
Binary Search element-116 : 5

Searching & Sorting

1. Linear Search
In [1]: def linear_search(arr,item):
for i in range(len(arr)):
if arr[i]==item:
return i
return 'Item not found'

linear_search([2,5,7,11,19,15],15)

Out[1]: 5

2.Binary Search
In [6]: def binary_search(arr,item):
low=0
high = len(arr)-1
 while low<=high:
mid=(low+high)//2
if arr[mid]==item:
return mid
if arr[mid]<item:
low = mid+1
else:
high = mid-1
return -1

binary_search([2,3,5,7,11],7)

Out[6]: 3

Sorting
1. Bubble Sort
Bubble Sort is the simplest sorting algorithm that works
by repeatedly swapping the adjacent elements if they
are in the wrong order. This algorithm is not suitable for
large data sets as its average and worst-case time
complexity are quite high.
Compare the first two values and swap if necessary. Then compare
the next pair of values and swap if necessary. This process is
repeated n-1 times, where n is the number of values being sorted.
 The example above sorts 4 numbers into ascending numerical
order. As you can see, this requires 3 (n-1) passes to achieve since
there are 4 items of data. The bigger numbers can be seen to
bubble (or ripple) to the top

Complexity Analysis of Bubble Sort:

Time Complexity: O(n2)

Auxiliary Space: O(1)

In [8]: def bubble_sort(arr):

for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j]>arr[j+1]:
arr[j],arr[j+1]=arr[j+1],arr[j]
return arr

bubble_sort([21,81,12,78,89,97])

Out[8]: [12, 21, 78, 81, 89, 97]

Advantages of Bubble Sort:

Bubble sort is easy to understand and implement.
It does not require any additional memory space.
It is a stable sorting algorithm, meaning that elements with the same key
value maintain their relative order in the sorted output.

Disadvantages of Bubble Sort:

Bubble sort has a time complexity of O(n2) which makes it very slow for
large data sets.
Bubble sort has almost no or limited real world applications. It is mostly used
in academics to teach different ways of sorting.

2. Selection Sort
Selection Sort is a comparison-based sorting algorithm.
It sorts an array by repeatedly selecting the smallest (or
largest) element from the unsorted portion and
swapping it with the first unsorted element. This
process continues until the entire array is sorted.

Complexity Analysis of Selection Sort

Time Complexity: O(n2) ,as there are two nested loops:
 One loop to select an element of Array one by one = O(n)
Another loop to compare that element with every other Array element =
O(n)
Therefore overall complexity = O(n) * O(n) = O(n*n) = O(n2)

Auxiliary Space: O(1) as the only extra memory used is for

temporary variables.

Advantages of Selection Sort

Easy to understand and implement.
Requires only a constant O(1) extra memory space.
It requires less number of swaps (or memory writes) compared to many
other standard algorithms. Only cycle sort beats it in terms of memory
writes. Therefore it can be simple algorithm choice when memory writes are
costly.

Disadvantages of the Selection Sort

Selection sort has a time complexity of O(n^2) makes it slower compared to
algorithms like Quick Sort or Merge Sort.
Does not maintain the relative order of equal elements which means it is not
stable.

Applications of Selection Sort

Perfect for teaching fundamental sorting mechanisms and algorithm design.
Suitable for small lists where the overhead of more complex algorithms isn't
justified and memory writing is costly as it requires less memory writes
compared to other standard sorting algorithms.
Heap Sort algorithm is based on Selection Sort.

In [12]: def selection_sort(arr):

for i in range(len(arr)-1):
min = i
for j in range(i+1,len(arr)):
if arr[j]<arr[min]:
min = j
arr[i],arr[min] = arr[min],arr[i]
return arr

selection_sort([34,12,21,65,11])

Out[12]: [11, 12, 21, 34, 65]

 3. Merge Sort
Merge sort is a popular sorting algorithm known for its
efficiency and stability. It follows the Divide and
Conquer approach. It works by recursively dividing the
input array into two halves, recursively sorting the two
halves and finally merging them back together to obtain
the sorted array.

Here's a step-by-step explanation of how merge sort

works:
Divide: Divide the list or array recursively into two halves until it can no
more be divided.
Conquer: Each subarray is sorted individually using the merge sort
algorithm.
Merge: The sorted subarrays are merged back together in sorted order. The
process continues until all elements from both subarrays have been merged.

In [19]: def merge_sorted_arrays(arr1,arr2,arr):

i=j=k=0
while i<len(arr1) and j<len(arr2):
if arr1[i]<arr2[j]:
arr[k] = arr1[i]
i+=1
k+=1
else:
arr[k]=arr2[j]
j+=1
k+=1
# extend remainin g elements
while i<len(arr1):
 arr[k]=arr1[i]
i+=1
k+=1
while j<len(arr2):
arr[k]=arr2[j]
j+=1
k+=1

return

def merge_sort(arr):

if len(arr)==1:
return arr

mid = len(arr)//2

left = arr[:mid]
right = arr[mid:]

merge_sort(left)
merge_sort(right)

merge_sorted_arrays(left,right,arr)

return arr

merge_sort([89,14,55,61,34])

Out[19]: [14, 34, 55, 61, 89]

Complexity Analysis of Merge Sort

Time Complexity:
Best Case: O(n log n), When the array is already sorted or nearly sorted.
Average Case: O(n log n), When the array is randomly ordered.
Worst Case: O(n log n), When the array is sorted in reverse order.

Auxiliary Space: O(n), Additional space is required for

the temporary array used during merging.

Applications of Merge Sort:

Sorting large datasets
External sorting (when the dataset is too large to fit in memory)
Used to solve problems like Inversion counting, Count Smaller on Right &
Surpasser Count
 Merge Sort and its variations are used in library methods of programming
languages. Its variation TimSort is used in Python, Java Android and Swift.

Advantages and Disadvantages of Merge Sort

Advantages
Stability : Merge sort is a stable sorting algorithm, which means it
maintains the relative order of equal elements in the input array.
Guaranteed worst-case performance: Merge sort has a worst-case time
complexity of O(N logN) , which means it performs well even on large
datasets.
Simple to implement: The divide-and-conquer approach is straightforward.
Naturally Parallel : We independently merge subarrays that makes it
suitable for parallel processing.

Disadvantages
Space complexity: Merge sort requires additional memory to store the
merged sub-arrays during the sorting process.
Not in-place: Merge sort is not an in-place sorting algorithm, which means
it requires additional memory to store the sorted data. This can be a
disadvantage in applications where memory usage is a concern.
Merge Sort is Slower than QuickSort in general as QuickSort is more cache
friendly because it works in-place.

4. Quick Sort
QuickSort is a sorting algorithm based on the Divide and
Conquer that picks an element as a pivot and partitions
the given array around the picked pivot by placing the
pivot in its correct position in the sorted array.
In [20]: def quick_sort(arr):
if len(arr)<1:
return arr

pivot = arr[len(arr)//2]

left = [x for x in arr if x<pivot]

middle = [x for x in arr if x==pivot]
right = [x for x in arr if x>pivot]

# recursive sort and combine

return quick_sort(left) + middle + quick_sort(right)
 quick_sort([44,11,33,12,7,90])

Out[20]: [7, 11, 12, 33, 44, 90]

Complexity Analysis of Quick Sort

Time Complexity:
Best Case: (Ω(n log n)), Occurs when the pivot element divides the array into
two equal halves.
Average Case (θ(n log n)), On average, the pivot divides the array into two
parts, but not necessarily equal.
Worst Case: (O(n²)), Occurs when the smallest or largest element is always
chosen as the pivot (e.g., sorted arrays).

Auxiliary Space:
Worst-case scenario: O(n) due to unbalanced partitioning leading to a
skewed recursion tree requiring a call stack of size O(n).
Best-case scenario: O(log n) as a result of balanced partitioning leading to a
balanced recursion tree with a call stack of size O(log n

Advantages of Quick Sort

It is a divide-and-conquer algorithm that makes it easier to solve problems.
It is efficient on large data sets.
It has a low overhead, as it only requires a small amount of memory to
function.
It is Cache Friendly as we work on the same array to sort and do not copy
data to any auxiliary array.
Fastest general purpose algorithm for large data when stability is not
required.
It is tail recursive and hence all the tail call optimization can be done.

Disadvantages of Quick Sort

It has a worst-case time complexity of O(n2), which occurs when the pivot is
chosen poorly.
It is not a good choice for small data sets.
It is not a stable sort, meaning that if two elements have the same key, their
relative order will not be preserved in the sorted output in case of quick sort,
because here we are swapping elements according to the pivot's position
(without considering their original positions).
 Applications of Quick Sort
Sorting large datasets efficiently in memory.
Used in library sort functions (like C++ std::sort and Java Arrays.sort for
primitives).
Arranging records in databases for faster searching.
Preprocessing step in algorithms requiring sorted input (e.g., binary search,
two-pointer techniques).
Finding the kth smallest/largest element using Quickselect (a variant of
quicksort).
Sorting arrays of objects based on multiple keys (custom comparators).
Data compression algorithms (like Huffman coding preprocessing).
Graphics and computational geometry (e.g., convex hull algorithms).

LinkedList
A linked list is a type of linear data structure similar to arrays. It is a
collection of nodes that are linked with each other. A node contains
two things first is data and second is a link that connects it with
another node. Below is an example of a linked list with four nodes
and each node contains character data and a link to another node.
Our first node is where head points and we can access all the
elements of the linked list using the head.

Creating a Node Class

In [1]: class Node:
def __init__(self,value):
self.data=value
self.next=None

Implementation of Simple LinkedList

In [2]: # create Nodes
node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)

# Link Nodes
node1.next = node2
node2.next = node3
node3.next = node4

# head points to the first node

head = node1

# traverse and print linkedlist

current = head

while current:
print(current.data,end='->')
current = current.next

print('None')

10->20->30->40->None

Types Of LinkedList
1. Singly LinkedList
A singly linked list is a fundamental data structure, it consists of
nodes where each node contains a data field and a reference to the
next node in the linked list. The next of the last node is null,
indicating the end of the list. Linked Lists support efficient insertion
and deletion operations.

2. Dobly LinkedList
A doubly linked list is a more complex data structure than a singly
linked list, but it offers several advantages. The main advantage of
a doubly linked list is that it allows for efficient traversal of the list
in both directions. This is because each node in the list contains a
pointer to the previous node and a pointer to the next node. This
allows for quick and easy insertion and deletion of nodes from the
list, as well as efficient traversal of the list in both directions.
3. Circular LinkedList
A circular linked list is a data structure where the last node points
back to the first node, forming a closed loop.
Structure: All nodes are connected in a circle, enabling continuous traversal
without encountering NULL.
Difference from Regular Linked List: In a regular linked list, the last node
points to NULL, whereas in a circular linked list, it points to the first node.
Uses: Ideal for tasks like scheduling and managing playlists, where smooth
and repeated.

Types of Circular LinkedLists

We can create a circular linkedlists from both singly linked

lists and doubly linked lists . So, circular linked lists are
basically two types:

1. Circular Singly LinkedLists

In Circular Singly Linked List, each node has just one pointer called
the "next" pointer. The next pointer of the last node points back to
the first node and this results in forming a circle. In this type of
Linked list, we can only move through the list in one direction.

2. Circular Doubly Linked Lists

In circular doubly linked list, each node has two pointers prev and
next, similar to doubly linked list. The prev pointer points to the
previous node and the next points to the next node. Here, in
addition to the last node storing the address of the first node, the
first node will also store the address of the last node.
 Advantages
Efficient Traversal
No Null Pointers/References
Useful for Repetitive Tasks
Insertion at Beginning or End is O(1)
Uniform Traversal
Efficient Memory Utilization

Disadvantages
Complex Implementation
Infinite Loop Risk
Harder to debug
Deletion Complexity
Memory Overhead (for Doubly Circular LL)
Not cache friendly

Implementation Of Doubly LinkedList

In [5]: class Node:
def __init__(self,value):
self.data = value
self.prev = None
self.next = None

# create Nodes
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
n4 = Node(40)

# link Nodes
n1.prev = None
n1.next = n2
n2.prev = n1
n2.next = n3
n3.prev = n2
n3.next = n4
n4.prev = n3
n4.next = None

head = n1
 current = head

while current:
print(current.data, end= '->')
current = current.next

print('None')

10->20->30->40->None

Implementation of Circular LinkedList

1. Circular Singly LinkedList
In [6]: class Node:
def __init__(self,value):
self.data = value
self.next = None

# create Nodes
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
n4 = Node(40)

# LinkedNodes
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n1

# traverse
head = n1
current = head

while True:
print(current.data,end='->')
current = current.next
if current== head:
break
print('None')

10->20->30->40->None

3. Circular Doubly Linked List

In [9]: class Node:
def __init__(self,value):
self.data = value
self.prev = None
self.next = None

# create Nodes
 n1 = Node(10)
n2= Node(20)
n3= Node(30)
n4 = Node(40)

# LinkedNodes
n1.prev = n4
n1.next = n2
n2.prev = n1
n2.next = n3
n3.prev = n2
n3.next = n4
n4.prev = n3
n4.next = n1

# traverse
head = n1
current = head

while True:
print(current.data,end='->')
current = current.next
if current==head:
break

print('None')

10->20->30->40->None

Implement LinkedList class

In [38]: class Node:
def __init__(self,value):
self.data = value
self.next = None

class LinkedList:
def __init__(self):
self.head = None
self.n = 0

def __len__(self):
return self.n

def __str__(self):
curr = self.head
res = ''
while curr:
res += str(curr.data) + ' -> '
curr = curr.next
return res + 'None'

def insert_head(self,item):
# create an Node
 new_node = Node(item)

new_node.next = self.head
self.head = new_node
self.n += 1

def append(self,item):
new_node = Node(item)
curr = self.head

while curr.next != None:

curr = curr.next
curr.next = new_node
self.n += 1

def insert_after(self,after,item):
new_node = Node(item)
curr = self.head

while curr.next!=None:
if curr.data == after:
break
curr = curr.next

new_node.next = curr.next
curr.next = new_node
self.n += 1

def delete_head(self):
if self.head == None:
return 'Empty LL'
self.head = self.head.next
self.n -= 1

def pop(self):
if self.head==None:
return 'Empty LL'
curr = self.head
while curr.next.next!=None:
curr = curr.next
curr.next = None
self.n -= 1

def remove(self,value):
if self.head.data == value:
self.delete_head()
return
curr = self.head
while curr.next!=None:
if curr.next.data == value:
break
curr = curr.next

if curr.next!=None:
curr.next = curr.next.next
self.n -= 1
 else:
return 'Not found'

def search(self,value):
curr = self.head
pos = 0

while curr!=None:
if curr.data == value:
return pos
curr = curr.next
pos += 1

def reverse(self):
prev = None
curr = self.head
while curr!=None:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
self.head=prev

def min(self):
curr = self.head
min_val = self.head.data
while curr!=None:
if curr.data<min_val:
min_val = curr.data
curr = curr.next
return min_val

def max(self):
curr = self.head
max_val = self.head.data
while curr!=None:
if curr.data>max_val:
max_val = curr.data
curr = curr.next
return max_val

def __getitem__(self,index):
curr = self.head
pos = 0
while curr!=None:
if pos==index:
return curr.data
curr = curr.next
pos += 1

l = LinkedList()
l.insert_head(1)
l.append(2)
l.append(3)
 l.append(4)
l.append(5)
print(l)
l.pop()
print(l)
l.delete_head()
print(l)
l.remove(4)
print(l)
# search
print(l.search(3))
# get index
print(l[0])
l.append(12)
l.append(43)
l.append(40)
print(l)
l.reverse()
print(l)
print('Min: ',l.min())
print('Max: ',l.max())
print('Length: ',len(l))

1 -> 2 -> 3 -> 4 -> 5 -> None

1 -> 2 -> 3 -> 4 -> None
2 -> 3 -> 4 -> None
2 -> 3 -> None
1
2
2 -> 3 -> 12 -> 43 -> 40 -> None
40 -> 43 -> 12 -> 3 -> 2 -> None
Min: 2
Max: 43
Length: 5

Stack
A stack is a linear data structure that follows the Last-In/First-Out
(LIFO) principle, also known as First-In/Last-Out (FILO). This means
that the last element added is the first one to be removed. In a
stack, both insertion and deletion happen at the same end, which is
called the top of the stack.
 Stack Operations
Stacks support a small set of basic operations, all of which run in O
(1) time:
empty (): checks if the stack is empty
size (): returns the number of elements in the stack
top () / peek (): shows the top element without removing it
push(a): adds an element a at the top
pop (): removes the top element

Implement Stack Using LinkedList

In [67]: class Node:
def __init__(self,value):
self.data = value
self.next = None

class LStack:
def __init__(self):
self.top = None

def is_empty(self):
return self.top==None

def peek(self):
if (self.is_empty()):
return 'Empty Stack'
return self.top.data

def push(self,value):
new_node = Node(value)
new_node.next = self.top
self.top = new_node
 def pop(self):
if (self.is_empty()):
return 'Empty Stack'
else:
data = self.top.data
self.top = self.top.next
return data

def traverse(self):
temp = self.top
while (temp!=None):
print(temp.data)
temp = temp.next

def size(self):
temp = self.top
counter = 0
while temp!=None:
counter+=1
temp=temp.next
return counter

In [68]: s = LStack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
s.traverse()
s.pop()
s.pop()
print('*'*20)
s.traverse()
print('peek:',s.peek())
print('size: ',s.size())
print('check empty: ',s.is_empty())

4
3
2
1
********************
2
1
peek: 2
size: 2
check empty: False

Stack Array Implementation

In [65]: class AStack:
def __init__(self,size):
self.size = size
self.stack = [None]*self.size
 self.top = -1

def is_empty(self):
return self.top == -1

def push(self,value):
if self.top == self.size -1:
return 'overflow'
else:
self.top += 1
self.stack[self.top]=value

def pop(self):
if self.top == -1:
return 'empty stack'
else:
data = self.stack[self.top]
self.top -= 1
return data

def peek(self):
if self.top == -1:
return 'empty stack'
return self.stack[self.top]

def traverse(self):
for i in range(self.top+1):
print(self.stack[i])

def __len__(self):
counter = 0
for i in range(self.top+1):
counter+=1
return counter

In [66]: s = AStack(3)
s.push(1)
s.push(2)
s.push(3)
s.traverse()
s.pop()
print('*'*20)
s.traverse()
print('peek:',s.peek())
print('size: ',len(s))
print('check empty: ',s.is_empty())

1
2
3
********************
1
2
peek: 2
size: 2
check empty: False
Stack Programs

🔹 Problem Statement: Reverse a String using

Stack
Given a string text , your task is to reverse the string using a stack data
structure.

You should use a stack to store characters of the string.

Pop characters from the stack to form the reversed string.

Function Signature
def reverse_string(text: str) -> str:

Examples
Example 1:

Input: text = "hello"

Output: "olleh"

Example 2:

Input: text = "DSA"

Output: "ASD"

Explanation: An empty string reversed is still an empty string.

Constraints
0 <= len(text) <= 10^5
text consists of printable ASCII characters.

Hint
Use a stack to push each character of the string.
Pop each character from the stack and append it to a new string.
The popped sequence will form the reversed string.
In [69]: def rev_string(text):
s = LStack()

for i in text:
s.push(i)

res = ''
while (not s.is_empty()):
res = res + s.pop()
return res

rev_string('hello moto')

Out[69]: 'otom olleh'

Text Editor Problem

🧠 Problem Statement: Text Editor Undo/Redo

Simulation
You are tasked with implementing a simplified text editor that supports two
operations — Undo ( u ) and Redo ( r ).
The editor uses two stacks to manage the state of the text, similar to how real
text editors maintain an undo-redo history.

📝 Description
Initially, the editor is given a string text .
You are also given a sequence of operations pattern , where each character
in the pattern can be:
'u' → Undo the last action (move one character from the undo stack to
the redo stack)
'r' → Redo the last undone action (move one character from the redo
stack back to the undo stack)

After performing all operations, return the final text present in the undo stack.

🔹 Function Signature
def text_editor(text: str, pattern: str) -> str:

⚙️Example
Input:
 text = "abcd"
pattern = "uur"

Process & Constraints

Process:

Start with the initial string text .

For each character in pattern :
If 'u' : perform Undo → remove the last character from the undo stack
and push it to the redo stack.
If 'r' : perform Redo → remove the top character from the redo stack
and push it back to the undo stack.
After all operations, the remaining characters in the undo stack represent the
final text.

Constraints

1 <= len(text) <= 10^4

0 <= len(pattern) <= 10^4
All operations in pattern are either 'u' or 'r' .
If an invalid undo/redo is attempted (for example, undo on empty text),
ignore that operation.

🧩 Hint

Use two stacks:

One stack ( u ) to keep track of the current text.

Another stack ( r ) to store characters that were undone. Perform push()
and pop() operations according to each symbol in the pattern .

In [72]: def text_editor(text,pattern):

u = LStack()
r = LStack()

for i in text:
u.push(i)

for i in pattern:
if i == 'u':
data = u.pop()
r.push(data)
elif i == 'r':
data = r.pop()
u.push(data)

res = ''
while (not u.is_empty()):
res = u.pop() + res
 return res

text_editor('hello moto','uuurrru')

Out[72]: 'hello mot'

🎯 DSA Problem: Find the Celebrity

You are given a party of n people. A celebrity is someone who:

1. Is known by everyone.
2. Knows no one.

You are given a square matrix L of size n x n :

L[i][j] = 1 → person i knows person j

L[i][j] = 0 → person i does NOT know person j

Your task: Identify the celebrity (return their index) or state that no celebrity
exists.

Function Signature
def find_celeb(L: list[list[int]]) -> None:

Examples, Constraints & Hint

Example 1:

python
L = [
[0, 1, 1],
[0, 0, 1],
[0, 0, 0]
]

Output: The celebrity is 2

Constraints & Hint

Constraints:

1 <= n <= 1000

L[i][j] ∈ {0, 1}
L[i][i] = 0 for all i

Hint:
 Use a stack to efficiently find the celebrity:
1. Push all indices (0 to n-1) onto the stack.
2. Pop two indices i and j :
If i knows j , i cannot be celebrity → push j back
Else, j cannot be celebrity → push i back
3. The last remaining person is a potential celebrity.
4. Verify:
They know no one
Everyone else knows them
Time Complexity reduces from O(n²) to O(n).

In [82]: def find_celeb(L):

s = LStack()

for i in range(len(L)):
s.push(i)

while s.size()>=2:
i = s.pop()
j = s.pop()

if L[i][j]==0:
# means - i not knows j - j not celebirity
s.push(i)
else:
# means j not knows i - i not celibrity
s.push(j)

celeb = s.pop()
for i in range(len(L)):
if i!=celeb:
if L[i][celeb] == 0 or L[celeb][i]==1:
print('No one is celebrity')
return

print('the celibrity is ',celeb)

L1 = [
[0, 1, 1],
[0, 0, 1],
[0, 0, 0]
]

find_celeb(L1)

L2 = [
[0, 1, 0],
[0, 0, 1],
[1, 0, 0]
]

find_celeb(L2)
the celibrity is 2
No one is celebrity

🔹 Problem Statement: Valid Parentheses

Given a string text consisting of characters '(' , ')' , '{' , '}' , '[' , and
']' , determine if the parentheses are valid.

A string of parentheses is considered valid if:

1. Every opening bracket has a corresponding closing bracket of the same

type.
2. Brackets are closed in the correct order.

Function Signature
def valid_parenthesis(text: str) -> bool:

Examples
Example 1:

Input: text = "()[]{}"

Output: True

Explanation: All opening brackets are closed properly in the correct order.

Example 2:

Input: text = "([)]"

Output: False

Explanation: Brackets are not closed in the correct order.

Example 3:

Input: text = "{[]}"

Output: True

Explanation: Properly nested and closed brackets.

Constraints
1 <= len(text) <= 10^4
 text consists only of '(' , ')' , '{' , '}' , '[' , ']' .

Hint
Use a stack to track opening brackets.
For every closing bracket, check if it matches the top of the stack.
If it matches, pop the stack; otherwise, the string is invalid.
After processing all characters, the stack should be empty for a valid string.

In [86]: def valid_parenthesis(text):

s = LStack()
mappings = {
'}':'{',
']':'[',
')':'('
}

for char in text:

if char in mappings:
if not s or s.pop()!=mappings[char]:
return False
else:
s.push(char)
return s.size()==0

print(valid_parenthesis("()[]{}"))
print(valid_parenthesis("([)])"))
print(valid_parenthesis("{[]}"))

True
False
True

Queue in Python
Queue is a linear data structure that stores items in a
First In First Out (FIFO) manner. The item that is added
first will be removed first. Queues are widely used in
real-life scenarios, like ticket booking, or CPU task
scheduling, where first-come, first-served rule is
followed.
 Operations associated with queue are:
Enqueue: Adds an item to the queue. If queue is full, it is said to be an
Overflow condition – Time Complexity : O(1)
Dequeue: Removes an item from the queue. If the queue is empty, it is said
to be an Underflow condition – Time Complexity : O(1)
Front: Get front item from queue – Time Complexity : O(1)
Rear: Get last item from queue – Time Complexity : O(1)

Implement a Queue Using LinkedList

In [89]: class Node:
def __init__(self,value):
self.data = value
self.next = None

class Queue:
def __init__(self):
self.front = None
self.rear = None

def enqueue(self,value):
new_node = Node(value)

if self.rear == None:
self.front = new_node
self.rear = self.front
else:
self.rear.next = new_node
self.rear = new_node

def dequeue(self):
if self.front == None:
 return 'Empty Queue'
else:
self.front = self.front.next

def traverse(self):
temp = self.front
while temp!=None:
print(temp.data,end=' ')
temp = temp.next
print()

def front_item(self):
if self.front == None:
return 'Empty Queue'
return self.front.data

def rear_item(self):
if self.rear == None:
self.rear = self.front
return self.rear.data

def size(self):
counter = 0
temp = self.front
while temp!=None:
counter+=1
temp = temp.next
return counter

In [97]: q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.traverse()
q.dequeue()
q.dequeue()
print('*'*20)
q.traverse()
print('Front: ',q.front_item())
print('rear: ',q.rear_item())
print('Size: ',q.size())

1 2 3 4
********************
3 4
Front: 3
rear: 4
Size: 2

Hash Map in Python

A hash map is a data structure that stores data as
unique key-value pairs, using a hash function to quickly
find the corresponding value for a given key.

A hash function creates a mapping from an input key to

an index in hash table.

A collision occurs when two distinct inputs are run

through the same hash function and result in the exact
same hash value.
Common techniques to handle collisions in a hash table
include chaining, open addressing, and double hashing.

Separate chaining, or open hashing, resolves hash

collisions by storing elements that hash to the same
index in a linked list at that index.

Avoid O(n) complexity we use:

Rehashing
B-Tree

Rehashing is the process of increasing the size of a hashmap and

redistributing the elements to new buckets based on their new
hash values. It is done to improve the performance of the hashmap
and to prevent collisions caused by a high load factor.
Open addressing (or closed hashing) resolves hash table
collisions by storing all elements directly within the
hash table array itself, using a probing sequence to find
an alternative slot when a collision occurs.
1. Linear Probing : In linear probing, the hash table is searched
sequentially that starts from the original location of the hash. If in
case the location that we get is already occupied, then we check
for the next location.
Algorithm:

1. Calculate the hash key. i.e. key = data % size

2. Check, if hashTable[key] is empty
store the value directly by hashTable[key] = data
3. If the hash index already has some value then
check for next index using key = (key+1) % size
4. Check, if the next index is available hashTable[key] then
store the value. Otherwise try for next index.
5. Do the above process till we find the space.

2. Quadratic Probing: Quadratic probing is an open addressing

scheme in computer programming for resolving hash collisions in
hash tables. Quadratic probing operates by taking the original hash
index and adding successive values of an arbitrary quadratic
polynomial until an open slot is found.
 An example sequence using quadratic probing is:

H + 1 , H + 4 , H + 9 , H + 16
...................... H + k 2

This method is also known as the mid-square method because in this method we
look for i2-th probe (slot) in i-th iteration and the value of i = 0, 1, . . . n – 1.

If the slot hash(x) % n is full, then we try (hash(x) + 1 2

) % n.
If (hash(x) + 1 2 ) % n is also full, then we try (hash(x)
+ 2 2 ) % n.
If (hash(x) + 2 2 ) % n is also full, then we try (hash(x)
+ 3 2 ) % n.
This process will be repeated for all the values of i
until an empty slot is found

Implement Dictionary In Python

In [55]: class Dictionary:
def __init__(self,size):
self.size=size
self.slots = [None]* self.size
self.data = [None]* self.size

def put(self,key,value):
## we find index using hash fn
hash_value = self.hash_function(key)
## for quadratic probing
i=0
if self.slots[hash_value]==None:
self.slots[hash_value]=key
self.data[hash_value]=value
else:
if self.slots[hash_value]==key:
self.data[hash_value]=value
else:
while self.slots[hash_value]!=None and self.slots[hash_value
new_hash_value = self.rehash(hash_value)
i+=1

if self.slots[new_hash_value]==None:
self.slots[new_hash_value]=key
self.data[new_hash_value]=value
else:
self.data[new_hash_value]=value

def get(self,key):
# calculate hash
start_position = self.hash_function(key)

current_position = start_position
 while self.slots[current_position]!=None:
if self.slots[current_position]==key:
return self.data[current_position]
current_position = self.rehash(current_position)

if current_position == start_position:
return 'Item Not Found'
return 'Not Found'

def __setitem__(self,key,value):
return self.put(key,value)

def __getitem__(self,key):
return self.get(key)

def __str__(self):
for i in range(len(self.slots)):
print(self.slots[i],':',self.data[i])
return ''

def __len__(self):
return len(self.slots)

def hash_function(self,key):
return abs(hash(key)) % self.size

def rehash(self,old_hash):
return (old_hash + 1) % self.size

In [56]: d1 = Dictionary(3)
d1.put('python',100)
d1.put('java',200)
d1['php'] = 300

In [57]: print(d1.slots)
print(d1.data)

['php', 'python', 'java']

[300, 100, 200]

In [58]: d1.get('python')

Out[58]: 100

In [59]: d1.get('java')

Out[59]: 200

In [60]: d1.get('c++')

Out[60]: 'Not Found'

In [61]: print(d1)
 php : 300
python : 100
java : 200

In [62]: print(len(d1))

Implement Dictionary Via Chaining (LinkedList)

In [147… class Node:
def __init__(self,key,value):
self.key = key
self.value = value
self.next = None

class LL:
def __init__(self):
self.head = None

def add(self,key,value):
new_node = Node(key,value)
if self.head == None:
self.head = new_node
else:
temp = self.head
while temp.next!=None:
temp=temp.next
temp.next = new_node

def delete_head(self):
if self.head == None:
return 'Empty'
self.head = self.head.next

def remove(self,key):
if self.head.key == key:
self.delete_head()
return
if self.head == None:
return 'Empty'
temp = self.head
while temp!=None:
if temp.next.key == key:
break
temp = temp.next

temp.next = temp.next.next

def traverse(self):
temp = self.head
while temp!=None:
print(temp.key,':',temp.value)
temp=temp.next
 def search(self,key):
temp = self.head
pos = 0
while temp!=None:
if temp.key==key:
return pos
temp=temp.next
pos += 1
return -1

def size(self):
temp = self.head
counter = 0
while temp!=None:
counter += 1
temp = temp.next
return counter

def get_node_at_index(self,index):
temp=self.head
counter=0
while temp!=None:
if counter==index:
return temp
temp= temp.next
counter += 1

class Dict:

def __init__(self, capacity):

self.capacity = capacity
self.size = 0
# create array of LL
self.buckets = self.make_array(self.capacity)

def make_array(self,capacity):

L = []
for i in range(capacity):
L.append(LL())
return L

def __setitem__(self,key,value):
self.put(key,value)

def __getitem__(self,key):
return self.get(key)

def __delitem__(self,key):

bucket_index = self.hash_function(key)

self.buckets[bucket_index].remove(key)
def __str__(self):

for i in self.buckets:
i.traverse()

return ""

def __len__(self):
return self.size

def get(self,key):

bucket_index = self.hash_function(key)

res = self.buckets[bucket_index].search(key)

if res == -1:
return "Not Present"
else:
node = self.buckets[bucket_index].get_node_at_index(res)
return node.value

def put(self, key, value):

bucket_index = self.hash_function(key)

node_index = self.get_node_index(bucket_index, key)

if node_index == -1:
# insert
self.buckets[bucket_index].add(key,value)
self.size+=1

load_factor = self.size/self.capacity

if (load_factor >= 2):

self.rehash()
else:
# update
node = self.buckets[bucket_index].get_node_at_index(node_index)
node.value = value

def rehash(self):
self.capacity = self.capacity * 2
old_buckets = self.buckets
self.size = 0
self.buckets = self.make_array(self.capacity)

for i in old_buckets:
for j in range(i.size()):
node = i.get_node_at_index(j)
key_item = node.key
 value_item = node.value
self.put(key_item,value_item)

def get_node_index(self,bucket_index, key):

node_index = self.buckets[bucket_index].search(key)

return node_index

def hash_function(self,key):
return abs(hash(key)) % self.capacity

In [148… d1 = Dict(3)
d1.put('python',1)
d1.put('java',2)
d1.put('php',3)
d1.put('go',4)
d1.put('html',5)
d1.put('css',6)

In [149… d1['python']=100

In [150… print(d1)

php : 3
python : 100
go : 4
java : 2
html : 5
css : 6

In [151… d1['matlab']=300

In [152… print(d1)

php : 3
python : 100
go : 4
matlab : 300
java : 2
html : 5
css : 6

In [153… del d1['matlab']

In [155… print(d1)
php : 3
python : 100
go : 4
java : 2
html : 5
css : 6