3 Data Structures in Python
Data Structures and Algorithms (DSA)
Data Structures and Algorithms (DSA) is a fundamental part of Computer Science that
teaches you how to think and solve complex problems systematically.
Types of Data Structures in DSA
Data structures are mainly classified into two types:
1. Linear Data Structures
• Elements are arranged sequentially (one after another).
• Easy to implement as memory is allocated in a contiguous manner.
• Examples: Array, Linked List, Stack, Queue
2. Non-Linear Data Structures
• Elements are connected in a hierarchical or random manner.
• More complex but efficient in certain operations.
• Examples: Trees, Graphs, Hash Tables
Difference Between Linear and Non-Linear Data Structures
Feature Linear Data Structure Non-Linear Data Structure
Arrangement Sequential (one after another) Hierarchical or interconnected
Memory Usage Contiguous or linked Random or hierarchical
Complexity Simpler to implement More complex to implement
Examples Array, Linked List, Stack, Queue Tree, Graph, Hash Table
Traversal Requires a single pass Requires multiple paths
Operations Easier to manage (insert, delete) Can be more efficient in searching
Usage Suitable for simple data storage Used for complex relationships
---
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
image_path = r"C:\Users\Debarghya Kundu\Desktop\dsa\images\Untitled-
Diagram-183.png"
img = mpimg.imread(image_path)
plt.imshow(img)
plt.axis('off') # Hide axes
plt.show()
3.1.1 ARRAY
Defination
• An array is a collection of elements stored in contiguous memory locations.
• All elements in an array must be of the same data type in low-level programming.
• Python does not have built-in arrays, but lists and NumPy arrays serve the same
purpose.
Operations on Arrays
1. Accessing Elements (Indexing)
🔹 In Python, arrays (lists) are zero-indexed:
arr = [10, 20, 30, 40, 50]
print(arr[0]) # Output: 10
print(arr[3]) # Output: 40
🔹 Negative Indexing allows access from the end:
print(arr[-1]) # Output: 50
print(arr[-3]) # Output: 30
🔹 Looping through an array
for num in arr:
print(num, end=" ")
# Output: 10 20 30 40 50
🔹Accessing elements with index
for i in range(len(arr)):
print(f"Element at index {i}: {arr[i]}")
2. Insertion and Deletion
🔹 Insertion
🔹Appending at the end (O(1)):
arr.append(60)
print(arr) # Output: [10, 20, 30, 40, 50, 60]
🔹Inserting at a specific position (O(N)):
arr.insert(2, 25) # Insert 25 at index 2
print(arr) # Output: [10, 20, 25, 30, 40, 50, 60]
🔹 Deletion
🔹Remove by value (O(N)):
arr.remove(30) # Removes first occurrence of 30
print(arr) # Output: [10, 20, 25, 40, 50, 60]
🔹Remove by index (O(N)):
arr.pop(2) # Removes element at index 2
print(arr) # Output: [10, 20, 40, 50, 60]
3. Searching in Arrays
🔹 Linear Search (O(N)):
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
arr = [10, 20, 30, 40, 50]
print(linear_search(arr, 40)) # Output: 3
🔹 Binary Search (O(log N)) (Only works on sorted arrays)
import bisect
arr = [10, 20, 30, 40, 50]
index = bisect.bisect_left(arr, 40)
print(index) # Output: 3
4. Slicing in Python
Slicing allows extracting parts of an array.
arr = [10, 20, 30, 40, 50, 60, 70]
print(arr[1:4]) # Output: [20, 30, 40]
print(arr[:3]) # Output: [10, 20, 30]
print(arr[3:]) # Output: [40, 50, 60, 70]
print(arr[::2]) # Output: [10, 30, 50, 70] (Step 2)
print(arr[::-1]) # Output: [70, 60, 50, 40, 30, 20, 10] (Reverse)
5. Multi-Dimensional Arrays (2D Arrays, Matrices)
A 2D array (matrix) is a list of lists.
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(matrix[1][2]) # Output: 6
📌 Traversing a 2D array
for row in matrix:
for elem in row:
print(elem, end=" ")
# Output: 1 2 3 4 5 6 7 8 9
6. Python’s List vs NumPy Arrays
Feature Python List NumPy Array
Type Can store multiple data Stores only one data type
Feature Python List NumPy Array
types
Performance Slower Faster (optimized for numerical
operations)
Memory More Less (efficient)
Usage
Operations Limited built-in operations Supports vectorized operations
import numpy as np
arr = np.array([10, 20, 30, 40])
print(arr + 5) # Output: [15 25 35 45] (Vectorized addition)
7. Dynamic Arrays (Using array module)
Python provides the array module for efficient memory usage
import array
arr = array.array('i', [1, 2, 3, 4, 5]) # 'i' means integer array
arr.append(6)
print(arr) # Output: array('i', [1, 2, 3, 4, 5, 6])
📌 Array Type Codes:
'i' → Integer type
'f' → Float type
8. Rotating an Array
def rotate(arr, k):
k = k % len(arr) # Handle cases where k > len(arr)
return arr[-k:] + arr[:-k]
arr = [1, 2, 3, 4, 5]
print(rotate(arr, 2)) # Output: [4, 5, 1, 2, 3]
9. Finding Duplicates
arr = [1, 2, 3, 4, 2, 5, 1]
duplicates = set([x for x in arr if arr.count(x) > 1])
print(duplicates) # Output: {1, 2}
10. Finding the Maximum & Minimum Element
arr = [10, 20, 5, 40, 25]
print("Max:", max(arr)) # Output: Max: 40
print("Min:", min(arr)) # Output: Min: 5
11. Finding the Second Largest Element
arr = [10, 20, 4, 45, 99, 99]
unique_arr = list(set(arr)) # Remove duplicates
unique_arr.sort()
print("Second Largest:", unique_arr[-2]) # Output: 45
12. Sorting an Array
🔹 Using sort() (Modifies original list)
arr = [3, 1, 4, 1, 5, 9, 2]
arr.sort()
print(arr) # Output: [1, 1, 2, 3, 4, 5, 9]
🔹 Using sorted() (Creates a new sorted list)
arr = [3, 1, 4, 1, 5, 9, 2]
sorted_arr = sorted(arr)
print(sorted_arr) # Output: [1, 1, 2, 3, 4, 5, 9]
🔥 Summary of Key Concepts
• ✅ Accessing & Looping Through Arrays
• ✅ Insertion, Deletion, and Searching
• ✅ Sorting, Slicing, and Rotating
• ✅ Multi-Dimensional Arrays & NumPy
• ✅ Finding Max, Min, and Duplicates
• This provides a well-structured and formatted explanation of arrays in Python. 🚀
Method Description
append() Adds an element at the end of the list
clear() Removes all the elements from the list
copy() Returns a copy of the list
Method Description
count() Returns the number of elements with the specified value
extend() Adds the elements of a list (or any iterable) to the end of the current list
index() Returns the index of the first element with the specified value
insert() Adds an element at the specified position
pop() Removes the element at the specified position
remove() Removes the first item with the specified value
reverse() Reverses the order of the list
sort() Sorts the list
---
3.1.2 Linked Lists
A Linked List is a linear data structure consisting of nodes, where each node contains two
parts:
• Data - The value stored in the node.
• Pointer (next/prev) - A reference to the next (or previous) node.
• Unlike arrays, linked lists do not use contiguous memory, making insertions and
deletions efficient.
Types of Linked Lists
1. Singly Linked List (SLL)
• Each node contains data and a pointer to the next node.
• Traversal is only forward.
• The last node’s next pointer is None.
1. Doubly Linked List (DLL)
• Each node contains data, a pointer to the next node, and a pointer to the previous
node.
• Allows both forward and backward traversal.
• Uses more memory due to extra pointer storage.
1. Circular Linked List (CLL)
• The last node points back to the first node.
• Can be singly circular (one direction) or doubly circular (both directions).
• Useful in circular queue implementations.
Operations on Linked Lists
1. Traversal - Visiting each node.
2. Insertion - Adding a node at:
• Beginning
• End
• Specific index
1. Deletion - Removing a node from:
• Head
• Tail
• Specific index
1. Reversal - Changing the order of nodes.
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLL:
def __init__(self):
self.head = None
# 🔹 Insert at the beginning
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
# 🔹 Insert at the end
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
# 🔹 Insert at a specific position
def insert_at_position(self, data, position):
if position < 0:
print("Invalid position!")
return
new_node = Node(data)
if position == 0:
self.insert_at_beginning(data)
return
temp = self.head
# Move to (position - 1)
for _ in range(position - 1):
if temp is None:
print("Position out of range!")
return
temp = temp.next
if temp is None:
print("Position out of range!")
return
# Insert the node
new_node.next = temp.next
temp.next = new_node
# 🔹 Delete a node by value
def delete_node(self, value):
if self.head is None:
print("List is empty!")
return
# If the node to be deleted is the head
if self.head.data == value:
self.head = self.head.next
return
temp = self.head
while temp.next and temp.next.data != value:
temp = temp.next
if temp.next is None:
print("Value not found in the list!")
return
temp.next = temp.next.next # Skip the node to delete
# 🔹 Delete a node by position
def delete_at_position(self, position):
if self.head is None:
print("List is empty!")
return
if position == 0: # Delete the head
self.head = self.head.next
return
temp = self.head
for _ in range(position - 1):
if temp is None or temp.next is None:
print("Position out of range!")
return
temp = temp.next
temp.next = temp.next.next # Skip the node to delete
# 🔹 Traverse & display the list
def display(self):
temp = self.head
if not temp:
print("Empty List")
return
elements = []
while temp:
elements.append(str(temp.data))
temp = temp.next
print(" -> ".join(elements) + " -> None")
# 🔥 **Testing the SLL**
l = SLL()
# Insert elements
l.insert_at_end(10)
l.insert_at_end(20)
l.insert_at_end(30)
l.insert_at_beginning(5)
l.insert_at_position(25, 2)
# Display list
print("Linked List after Insertions:")
l.display()
# Delete by value
l.delete_node(20)
print("\nLinked List after deleting 20:")
l.display()
# Delete by position
l.delete_at_position(2)
print("\nLinked List after deleting at position 2:")
l.display()
Linked List after Insertions:
5 -> 10 -> 25 -> 20 -> 30 -> None
Linked List after deleting 20:
5 -> 10 -> 25 -> 30 -> None
Linked List after deleting at position 2:
5 -> 10 -> 30 -> None
#2. Doubly Linked List (DLL)
class DNode:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
# Insert at the beginning
def insert_at_beginning(self, data):
new_node = DNode(data)
new_node.next = self.head
if self.head:
self.head.prev = new_node
self.head = new_node
# Insert at the end
def insert_at_end(self, data):
new_node = DNode(data)
if not self.head:
self.head = new_node
return
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
# Delete head node
def delete_head(self):
if self.head:
self.head = self.head.next
if self.head:
self.head.prev = None
# Traverse the list
def traverse(self):
temp = self.head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("None")
# Example Usage:
dll = DoublyLinkedList()
dll.insert_at_beginning(10)
dll.insert_at_end(20)
dll.insert_at_end(30)
dll.traverse() # Output: 10 <-> 20 <-> 30 <-> None
dll.delete_head()
dll.traverse() # Output: 20 <-> 30 <-> None
10 <-> 20 <-> 30 <-> None
20 <-> 30 <-> None
# 3. Circular Linked List (CLL)
class CNode:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
# Insert at the end
def insert_at_end(self, data):
new_node = CNode(data)
if not self.head:
self.head = new_node
new_node.next = self.head
return
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
# Delete head node
def delete_head(self):
if not self.head:
return
if self.head.next == self.head:
self.head = None
return
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = self.head.next
self.head = self.head.next
# Traverse the list
def traverse(self):
if not self.head:
return
temp = self.head
while True:
print(temp.data, end=" -> ")
temp = temp.next
if temp == self.head:
break
print("(Back to Head)")
# Example Usage:
cll = CircularLinkedList()
cll.insert_at_end(10)
cll.insert_at_end(20)
cll.insert_at_end(30)
cll.traverse() # Output: 10 -> 20 -> 30 -> (Back to Head)
cll.delete_head()
cll.traverse() # Output: 20 -> 30 -> (Back to Head)
10 -> 20 -> 30 -> (Back to Head)
20 -> 30 -> (Back to Head)
Summary
Operatio Singly Linked Circular Linked
n List Doubly Linked List List
Insertion ✅ Easy ✅ Extra memory (prev pointer) ✅ Forms a loop
Deletion ✅ Efficient ✅ More control ✅ Loop maintained
Traversal ➡️One direction ↔️Two directions 🔁 Loops back
Reversal 🔄 Modify next 🔄 Swap next & prev 🔄 Special handling
Each implementation shows:
• How nodes are structured
• Basic operations like insertion, deletion, and traversal
• How linked lists work with simple Python code
• This should make understanding Linked Lists easier! 🚀
