Linked List in Python – DSA Notes
1. What is a Linked List?
• Definition: A linked list is a linear data structure where elements (nodes) are
connected using pointers.
• Each node has:
o data → stores the value
o next → pointer/reference to the next node
• Unlike arrays, linked lists do not store elements in contiguous memory.
Analogy: Think of a chain of train coaches where each coach links to the next one.
2. Why Linked Lists are Important in DSA
• Dynamic size (no fixed length like arrays).
• Efficient insertion and deletion (no shifting like arrays).
• Used in implementing queues, stacks, adjacency lists in graphs.
• Helps in memory management and handling large data dynamically.
3. Types of Linked Lists
• Singly Linked List → Each node points to the next node only.
• Doubly Linked List → Each node has next and prev pointers.
• Circular Linked List → Last node points back to the first node.
4. Basic Linked List Operations
Operation Description Example
Insert at beginning Add new node at start head → newNode → oldHead
Insert at end Add new node at end [Link] = newNode
Delete node Remove node by value Adjust pointers
Operation Description Example
Traverse Go through each node While loop until None
5. Implementing Linked List in Python
# Node class
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
# LinkedList class
class LinkedList:
def __init__(self):
[Link] = None
# Insert at end
def insert(self, data):
new_node = Node(data)
if [Link] is None:
[Link] = new_node
return
temp = [Link]
while [Link]:
temp = [Link]
[Link] = new_node
# Print list
def display(self):
temp = [Link]
while temp:
print([Link], end=" -> ")
temp = [Link]
print("None")
# Example
ll = LinkedList()
[Link](10)
[Link](20)
[Link](30)
[Link]() # Output: 10 -> 20 -> 30 -> None
Hash Table in Python – DSA Notes
1. What is a Hash Table?
• Definition: A hash table is a data structure that stores key–value pairs using a
hash function.
• Hash function → Converts a key into an index in the table.
• Fast average-time operations: O(1) for insertion, deletion, and lookup.
Analogy: Think of a locker system where each locker has a number (hash) and stores
an item (value).
2. Why Hash Tables are Important in DSA
• Very fast data lookup (used in dictionaries).
• Used in database indexing.
• Helps in caching, sets, and unique item storage.
• Basis of many algorithms (counting, mapping, etc.).
3. Common Hash Table Operations
Operation Description Python Example
Insert Add key–value pair table["name"] = "Alice"
Search Find value by key table["name"]
Delete Remove key–value pair del table["name"]
Update Change value table["age"] = 25
4. Implementing Hash Table in Python
Method 1: Using Dictionary (built-in)
# Create hash table using dictionary
hash_table = {}
# Insert
hash_table["name"] = "Alice"
hash_table["age"] = 22
# Access
print(hash_table["name"]) # Alice
# Delete
del hash_table["age"]
print(hash_table) # {'name': 'Alice'}
Method 2: Custom Implementation with Lists
class HashTable:
def __init__(self, size=10):
[Link] = size
[Link] = [[] for _ in range(size)]
def hash_func(self, key):
return hash(key) % [Link]
def insert(self, key, value):
index = self.hash_func(key)
for pair in [Link][index]:
if pair[0] == key:
pair[1] = value
return
[Link][index].append([key, value])
def get(self, key):
index = self.hash_func(key)
for pair in [Link][index]:
if pair[0] == key:
return pair[1]
return None
# Example
ht = HashTable()
[Link]("name", "Bob")
[Link]("age", 25)
print([Link]("name")) # Bob
