Lecture Notes: Data Structures in Python (CSC701-
Algorithm and Data Structures)
1. Introduction to Data Structures
Data structures are ways to organize and store data efficiently. Python provides built-in data
structures and allows the creation of custom ones. Understanding them is crucial for writing
optimized code.
Why Use Data Structures?
• Efficiency: Faster data access and manipulation.
• Organization: Logical structuring of data.
• Problem-Solving: Essential for algorithms and real-world applications.
2. Built-in Data Structures in Python
Python has four primary built-in data structures:
A. Lists (list)
• Ordered, mutable, allows duplicates.
• Syntax: my_list = [1, 2, "hello"]
• Common Operations:
Python code:
my_list.append(3) # Add element
my_list.remove(2) # Remove element
my_list[0] = 10 # Modify element
B. Tuples (tuple)
• Ordered, immutable, allows duplicates.
• Syntax: my_tuple = (1, 2, "hello")
• Common Operations:
Python code:
print(my_tuple[0]) # Access element
# my_tuple[0] = 10 # Error: Immutable!
C. Dictionaries (dict)
• Key-value pairs, unordered, mutable, keys must be unique.
• Syntax: my_dict = {"name": "Alice", "age": 25}
• Common Operations:
Python code:
my_dict["age"] = 26 # Update value
my_dict["city"] = "NY" # Add new key-value
del my_dict["name"] # Delete key
D. Sets (set)
• Unordered, mutable, no duplicates.
• Syntax: my_set = {1, 2, 3}
• Common Operations:
Python code:
my_set.add(4) # Add element
my_set.remove(2) # Remove element
3. Advanced Data Structures in Python
Beyond built-in structures, Python supports more complex ones via modules or custom
implementation.
A. Stacks (LIFO)
• Last In, First Out (e.g., browser back button).
• Implementation (using lists):
Python code:
stack = []
stack.append(1) # Push
stack.pop() # Pop
B. Queues (FIFO)
• First In, First Out (e.g., print queue).
• Implementation (using collections.deque):
python
Copy
Download
from collections import deque
queue = deque()
queue.append(1) # Enqueue
queue.popleft() # Dequeue
C. Linked Lists
• Nodes connected via pointers.
• Implementation:
python
Copy
Download
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
D. Trees (Binary Search Tree)
• Hierarchical structure with nodes.
• Implementation:
python
Copy
Download
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
E. Graphs
• Nodes + edges (directed/undirected).
• Implementation (using adjacency list):
python
Copy
Download
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["E"],
"D": [],
"E": []
}
4. Choosing the Right Data Structure
Use Case Best Data Structure
Fast lookups by key dict
Ordered, mutable collection list
Unique elements set
Immutable data tuple
LIFO operations stack (list)
FIFO operations queue (deque)
Hierarchical data tree
Network connections graph
5. Time Complexity Cheat Sheet
Data Structure Access Search Insert Delete
List O(1) O(n) O(1)* O(n)
Dictionary O(1) O(1) O(1) O(1)
Set - O(1) O(1) O(1)
Stack (list) O(1) O(n) O(1) O(1)
Data Structure Access Search Insert Delete
Queue (deque) O(1) O(n) O(1) O(1)
Linked List O(n) O(n) O(1) O(1)
BST O(log n) O(log n) O(log n) O(log n)
*Amortized for dynamic lists.
6. Summary & Key Takeaways
Lists → Mutable, ordered collections.
Tuples → Immutable, ordered collections.
Dictionaries → Key-value pairs for fast lookups.
Sets → Unique elements, fast membership tests.
Stacks & Queues → LIFO & FIFO structures.
Linked Lists, Trees, Graphs → Advanced structures for complex problems.
Next Steps
• Practice implementing each structure.
• Solve problems on LeetCode/HackerRank.
• Explore libraries like heapq for priority queues.
