Built-in Data Structures in Python
Duc-Minh Vu
FDA - SLSCM Lab
National Economics University
August 25, 2025
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 1 / 14
Learning Objectives
After this lecture, students can:
Describe the properties of core structures: list, set, dict.
Identify supported operations and their time complexity (including
amortized).
Apply deque, heapq, and Counter to practical tasks.
Select the right structure for a given Business/AI/DS scenario and
justify the choice.
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 2 / 14
Introduction
Python provides several built-in data structures optimized for
common tasks.
Choosing the right structure improves:
Performance
Scalability
Code readability
This lecture focuses on:
Core: list, set, dict
Libraries: [Link], heapq, [Link]
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 3 / 14
Built-in Structures: Overview
Core structures
list: ordered, mutable, allows duplicates
set: unordered, unique elements
dict: mapping key → value, unique keys
Additional commonly used
[Link]: double-ended queue
heapq: priority queue (min-heap)
[Link]: frequency counter
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 4 / 14
List
Definition: Ordered, mutable, allows duplicates.
Complexity:
Indexing: O(1)
Append: O(1) amortized
Insert/Delete in the middle: O(n)
Membership test: O(n)
fruits = ["apple", "banana", "cherry"]
[Link]("orange") # O(1) amortized
[Link]("banana") # O(n)
print(fruits[0]) # O(1)
print("apple" in fruits) # O(n)
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 5 / 14
Set
Definition: Unordered collection of unique elements.
Complexity:
Add / Remove: O(1) average
Membership test: O(1) average
Union / Intersection: O(n + m)
numbers = {1, 2, 3}
[Link](4) # O(1)
print(3 in numbers) # O(1)
print([Link]({5, 6})) # O(n+m)
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 6 / 14
Dictionary
Definition: Mapping key → value with unique keys.
Complexity:
Get/Set by key: O(1) average
Delete by key: O(1) average
Membership test on keys: O(1) average
Iteration: O(n)
student = {"id":"S001", "name":"Alice", "grade":"A"}
print(student["name"]) # O(1)
student["grade"] = "A+" # O(1)
del student["id"] # O(1)
for k, v in [Link](): # O(n)
print(k, v)
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 7 / 14
Deque ([Link])
Definition: Double-ended queue, efficient at both ends.
Complexity:
append / appendleft: O(1)
pop / popleft: O(1)
Insert/Delete in the middle: O(n)
from collections import deque
dq = deque([1, 2, 3])
[Link](0) # O(1)
[Link](4) # O(1)
print(dq) # deque([0, 1, 2, 3, 4])
[Link]() # O(1)
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 8 / 14
Priority Queue (heapq)
Definition: Min-heap implementation for priority queues.
Complexity:
heappush: O(log n)
heappop: O(log n)
heap[0] (peek min): O(1)
heapify: O(n)
import heapq
tasks = []
[Link](tasks, (1, "high"))
[Link](tasks, (3, "low"))
[Link](tasks, (2, "medium"))
print(tasks[0]) # peek min: (1, "high")
print([Link](tasks)) # (1, "high")
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 9 / 14
Counter ([Link])
Definition: Specialized dictionary for counting.
Complexity:
Count update: O(1) per element
most common(k): O(n log n)
from collections import Counter
text = "data science data ai"
cnt = Counter([Link]())
print(cnt.most_common(2)) # [(’data’, 2), (’science’, 1)]
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 10 / 14
Dynamic Array & Amortized Analysis
Python list is a dynamic array: capacity doubles when full.
Append can sometimes cost O(n) (due to resizing).
However, total cost over n appends is O(n).
Hence, average cost per append = O(1) amortized.
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 11 / 14
Quick Comparison (Cheat Sheet)
Structure Best for Key ops (avg.)
list append/index append O(1)∗ , index O(1), insert mid O(
set membership unique add/mem O(1), union O(n+m)
dict key → value get/set/del O(1), iterate O(n)
deque both ends append/appendleft/pop/popleft O(1)
heapq priority push/pop O(log n), peek O(1)
Counter frequency update O(1)/elem, most common O(n lo
∗
amortized
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 12 / 14
Exercises (Quick)
1 Deduplicate SKUs + fast membership test: set or list? Why?
2 Customer tickets with priority: list+sort or heapq?
3 Streaming logs needing enqueue/dequeue at both ends: list or
deque?
4 Word frequency + top-10: dict or Counter?
5 Lookup student records by unique ID: list or dict?
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 13 / 14
Conclusion
Choosing the right data structure improves performance and simplifies
logic.
Understanding complexity helps in making informed choices.
Practice: try replacing different structures in the same task and
measure performance.
Duc-Minh Vu FDA - SLSCM Lab National Economics
Built-in
University
Data Structures in Python August 25, 2025 14 / 14