Basic Data
Structures in Python
Lecture Overview
Lists basics
Strings basics
Tuples basics
Sets basics
Dictionaries & Counters
Choosing the right structure: patterns, & trade-offs
Part 1
WHAT ARE DATA STRUCTURES?
Organized ways to store and manage data in memory
Time and space complexity vary by operation type
Choosing the right structure impacts algorithm efficiency
Foundation for solving competitive programming and system
design challenges
DATA STRUCTURES OVERVIEW
Lists - Ordered, mutable sequences
Strings - Immutable sequences of characters
Tuples - Ordered, immutable sequences
Sets - Unordered collections of unique elements
Dictionaries - Key-value mappings (including Counter)
LISTS
Definition: Ordered, mutable collection of elements
Creation: my_list = [1, 2, 3, 4, 5]
Indexing: 0-based, supports negative indexing (-1 = last element)
Mutability: Can add, remove, modify elements at any position
Heterogeneous: Can store mixed data types
Memory: Dynamic, grows as needed
LISTS - Common Operations
LIST Comprehension
Basic syntax: [expression for item in iterable if condition]
LISTS - Time Complexity
Operation Time Notes
Access by index O(1) Direct memory access
Search (unsorted) O(n) Linear scan
Insert at end O(1) amortized Constant amortized time
Insert at position O(n) Requires shifting elements
Delete by index O(n) Requires shifting remaining elements
Sort O(n log n) Uses Timsort algorithm
Slice O(k) k = slice length
STRINGS
Definition: Sequence of Unicode characters, immutable
Creation: my_string = "Hello World" or my_string = 'Hello'
Indexing: 0-based, like lists, supports slicing
Immutability: Cannot change individual characters after creation
Escaping: \n (newline), \t (tab), \\ (backslash), \" (quote)
Methods: Many built-in string methods (no modification needed)
STRINGS - Common Operations
STRINGS - Common Operations
STRINGS - Time Complexity
Operation Time Notes
Access character O(1) Direct index access
Slice O(k) k = slice length
Concatenation O(n+m) Creates new string
Search (find) O(n) Linear search
Split O(n) Scans entire string
Replace O(n) Scans entire string
Join O(n) n = total chars being joined
Tuples
Definition: Ordered, immutable collection
Creation: my_tuple = (1, 2, 3) or my_tuple = 1, 2, 3
Single element: single = (42,) - comma is required!
Indexing: 0-based, supports slicing (like lists)
Immutability: Cannot modify after creation
Hash-able: Can be used as dictionary keys or in sets
Performance: Faster than lists, used for returning multiple values
Tuples - Operations
Tuples Vs Lists
Feature Tuples Lists
Mutable ❌ No ✅ Yes
Hash-able ✅ Yes ❌ No
Dict key ✅ Yes ❌ No
Performance Faster Slower
Memory Less More
Use case Fixed data Dynamic data
Syntax (1, 2, 3)
Problems
List Comprehension
Runner-up Score
Nested Lists
Lists
Part 2
Set
Definition: An unordered, unindexed collection of unique
elements.
Creation: using {} or set(), Note: To create an empty set, you must
use set(). e.g. empty_set = set(), numbers_set = set([1, 2, 3, 4, 5]), or
numbers_set = {1, 2, 3, 4, 5}
Uniqueness: Automatically enforces that all elements are unique
(duplicates are discarded upon creation).
Set
Immutability of Elements: Elements must be hashable (e.g.,
numbers, strings, tuples) but cannot be mutable objects like lists
or dictionaries.
Indexing: Elements cannot be accessed by index since they are
unordered.
Use Case: Fast membership testing (O(1) average time complexity)
and eliminating duplicates.
Set - Operations
Set - Operations
Dictionaries
Definition: An unordered collection of key-value pairs.
Creation: my_dict = {'a': 1, 'b': 2, 'c': 3} or my_dict = dict(a=1, b=2).
Keys: Must be unique and hashable (like strings, numbers, or
tuples).
Values: Can be any data type (mutable or immutable).
Access/Modification: Access and insert/modify operations are very
fast (average O(1)).
Dictionaries - Common Operations
Dictionaries - Common Operations
Counters (from collections module)
Definition: A subclass of dict designed for counting hashable
objects.
Functionality: Stores elements as dictionary keys and their counts
as dictionary values.
Creation: Imported from the collections module.
Use Case: Easily count the frequency of items in a list or string.
Dictionaries - Common Operations
Choosing the Right Structure: Patterns &
Trade-offs
Choosing the optimal data structure is critical for performance2. The
decision depends on the required operations and their acceptable
time complexity.
Common Patterns and Best Fits
Need an Ordered, Flexible Sequence? (Dynamic Data)
Choice: List.
Trade-off: Fast access/insertion at the end (O(1) amortized).
Slow insertion/deletion in the middle (O(n)).
Choosing the Right Structure: Patterns & Trade-offs
Need Fixed, Grouped Data? (Immutable Sequence)
Choice: Tuple.
Trade-off: Faster and uses less memory than lists. Essential
when the data needs to be used as a dictionary key
(hashable).
Need Fast Lookups/Membership Testing? (Unique Elements)
Choice: Set.
Trade-off: Membership checks are O(1) on average. Cannot
contain duplicates or mutable elements
Choosing the Right Structure: Patterns & Trade-offs
Need Key-Value Mapping? (Fast Retrieval by Identifier)
Choice: Dictionary.
Trade-off: Insertion and retrieval are O(1) on average. Keys
must be immutable (hashable).
Need to Count Frequencies?
Choice: Counter (a Dictionary sub-class).
Trade-off: Specialized for counting, providing easy frequency
analysis.
Common - Pitfalls
Key Errors:- Accessing a key that doesn't exist raises a KeyError
dict[key]. So be sure to use [Link](key, default).
Mutable Keys:-Set elements and Dictionary keys must be
immutable (e.g., lists can't be keys, but tuples can if they contain
only immutable elements).
Trying to access Indexes out of range
Problems
Find Players With Zero or One Losses - LeetCode
Missing Number - LeetCode
Day 8: Dictionaries and Maps | HackerRank
Quote of the Day
“Simplicity is prerequisite for reliability.”
- Edsger W. Dijkstra