Comprehensive Python Data Structures Cheat sheet
Table of Contents
- Lists
- Tuples
- Sets
- Dictionaries
- Strings
- Arrays
- Stacks
- Queues
- Linked Lists
- Trees
- Heaps
- Graphs
- Advanced Data Structures
Lists
Lists are ordered, mutable sequences.
Creation
empty_list = []
list_with_items = [1, 2, 3]
list_from_iterable = list("abc")
list_comprehension = [x for x in range(10) if x % 2 == 0]
Common Operations
# Accessing elements
first_item = my_list[0]
last_item = my_list[-1]
# Slicing
subset = my_list[1:4] # Elements 1 to 3
reversed_list = my_list[::-1]
# Adding elements
my_list.append(4) # Add to end
my_list.insert(0, 0) # Insert at specific index
my_list.extend([5, 6, 7]) # Add multiple elements
# Removing elements
removed_item = my_list.pop() # Remove and return last item
my_list.remove(3) # Remove first occurrence of 3
del my_list[0] # Remove item at index 0
# Other operations
length = len(my_list)
index = my_list.index(4) # Find index of first occurrence of 4
count = my_list.count(2) # Count occurrences of 2
my_list.sort() # Sort in place
sorted_list = sorted(my_list) # Return new sorted list
my_list.reverse() # Reverse in place
Advanced Techniques
# List as stack
stack = [1, 2, 3]
stack.append(4) # Push
top_item = stack.pop() # Pop
# List as queue (not efficient, use collections.deque instead)
queue = [1, 2, 3]
queue.append(4) # Enqueue
first_item = queue.pop(0) # Dequeue
# Nested lists
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flattened = [item for sublist in matrix for item in sublist]
# List multiplication
repeated_list = [0] * 5 # [0, 0, 0, 0, 0]
# List unpacking
a, *b, c = [1, 2, 3, 4, 5] # a=1, b=[2, 3, 4], c=5
Tuples
Tuples are ordered, immutable sequences.
Creation
empty_tuple = ()
single_item_tuple = (1,) # Note the comma
tuple_with_items = (1, 2, 3)
tuple_from_iterable = tuple("abc")
Common Operations
# Accessing elements (similar to lists)
first_item = my_tuple[0]
last_item = my_tuple[-1]
# Slicing (similar to lists)
subset = my_tuple[1:4]
# Other operations
length = len(my_tuple)
index = my_tuple.index(2)
count = my_tuple.count(3)
# Tuple unpacking
a, b, c = (1, 2, 3)
Advanced Techniques
# Named tuples
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(11, y=22)
print(p.x, p.y)
# Tuple as dictionary keys (immutable, so allowed)
dict_with_tuple_keys = {(1, 2): 'value'}
Sets
Sets are unordered collections of unique elements.
Creation
empty_set = set()
set_with_items = {1, 2, 3}
set_from_iterable = set([1, 2, 2, 3, 3]) # {1, 2, 3}
set_comprehension = {x for x in range(10) if x % 2 == 0}
Common Operations
# Adding elements
my_set.add(4)
my_set.update([5, 6, 7])
# Removing elements
my_set.remove(3) # Raises KeyError if not found
my_set.discard(3) # No error if not found
popped_item = my_set.pop() # Remove and return an arbitrary element
# Other operations
length = len(my_set)
is_member = 2 in my_set
# Set operations
union = set1 | set2
intersection = set1 & set2
difference = set1 - set2
symmetric_difference = set1 ^ set2
Advanced Techniques
# Frozen sets (immutable)
frozen = frozenset([1, 2, 3])
# Set comparisons
is_subset = set1 <= set2
is_superset = set1 >= set2
is_disjoint = set1.isdisjoint(set2)
# Set of sets (requires frozenset)
set_of_sets = {frozenset([1, 2]), frozenset([3, 4])}
Dictionaries
Dictionaries are mutable mappings of key-value pairs.
Creation
empty_dict = {}
dict_with_items = {'a': 1, 'b': 2, 'c': 3}
dict_from_tuples = dict([('a', 1), ('b', 2), ('c', 3)])
dict_comprehension = {x: x**2 for x in range(5)}
Common Operations
# Accessing elements
value = my_dict['key']
value = my_dict.get('key', default_value)
# Adding/Updating elements
my_dict['new_key'] = value
my_dict.update({'key1': value1, 'key2': value2})
# Removing elements
del my_dict['key']
popped_value = my_dict.pop('key', default_value)
last_item = my_dict.popitem() # Remove and return an arbitrary key-value pair
# Other operations
keys = my_dict.keys()
values = my_dict.values()
items = my_dict.items()
length = len(my_dict)
is_key_present = 'key' in my_dict
Advanced Techniques
# Dictionary unpacking
merged_dict = {**dict1, **dict2}
# Default dictionaries
from collections import defaultdict
dd = defaultdict(list)
dd['key'].append(1) # No KeyError
# Ordered dictionaries (Python 3.7+ dictionaries are ordered by default)
from collections import OrderedDict
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
# Counter
from collections import Counter
c = Counter(['a', 'b', 'c', 'a', 'b', 'b'])
print(c.most_common(2)) # [('b', 3), ('a', 2)]
Strings
Strings are immutable sequences of Unicode characters.
Creation
single_quotes = 'Hello'
double_quotes = "World"
triple_quotes = '''Multiline
string'''
raw_string = r'C:\Users\name'
f_string = f"The answer is {40 + 2}"
Common Operations
# Accessing characters
first_char = my_string[0]
last_char = my_string[-1]
# Slicing (similar to lists)
substring = my_string[1:4]
# String methods
upper_case = my_string.upper()
lower_case = my_string.lower()
stripped = my_string.strip()
split_list = my_string.split(',')
joined = ', '.join(['a', 'b', 'c'])
# Other operations
length = len(my_string)
is_substring = 'sub' in my_string
char_count = my_string.count('a')
Advanced Techniques
# String formatting
formatted = "{} {}".format("Hello", "World")
formatted = "%s %s" % ("Hello", "World")
# Regular expressions
import re
pattern = r'\d+'
matches = re.findall(pattern, my_string)
# Unicode handling
unicode_string = u'\u0061\u0062\u0063'
Arrays
Arrays are compact sequences of numeric values (from the array
module).
Creation and Usage
from array import array
int_array = array('i', [1, 2, 3, 4, 5])
float_array = array('f', (1.0, 1.5, 2.0, 2.5))
# Operations (similar to lists)
int_array.append(6)
int_array.extend([7, 8, 9])
popped_value = int_array.pop()
Stacks
Stacks can be implemented using lists or collections.deque
.
Implementation and Usage
# Using list
stack = []
stack.append(1) # Push
stack.append(2)
top_item = stack.pop() # Pop
# Using deque (more efficient)
from collections import deque
stack = deque()
stack.append(1) # Push
stack.append(2)
top_item = stack.pop() # Pop
Queues
Queues can be implemented using collections.deque
or queue.Queue
.
Implementation and Usage
# Using deque
from collections import deque
queue = deque()
queue.append(1) # Enqueue
queue.append(2)
first_item = queue.popleft() # Dequeue
# Using Queue (thread-safe)
from queue import Queue
q = Queue()
q.put(1) # Enqueue
q.put(2)
first_item = q.get() # Dequeue
Linked Lists
Python doesn't have a built-in linked list, but it can be implemented.
Simple Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, data):
if not self.head:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)
Trees
Trees can be implemented using custom classes.
Simple Binary Tree Implementation
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
self.root = TreeNode(root)
def insert(self, value):
self._insert_recursive(self.root, value)
def _insert_recursive(self, node, value):
if value < node.value:
if node.left is None:
node.left = TreeNode(value)
else:
self._insert_recursive(node.left, value)
else:
if node.right is None:
node.right = TreeNode(value)
else:
self._insert_recursive(node.right, value)
Heaps
Heaps can be implemented using the heapq
module.
Usage
import heapq
# Create a heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
# Pop smallest item
smallest = heapq.heappop(heap)
# Create a heap from a list
my_list = [3, 1, 4, 1, 5, 9]
heapq.heapify(my_list)
Graphs
Graphs can be implemented using dictionaries.
Simple Implementation
class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for neighbor in self.graph.get(vertex, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Advanced Data Structures
Trie
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
Disjoint Set (Union-Find)
class DisjointSet:
def __init__(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}
def find(self, item):
if self.parent[item] != item:
self.parent[item] = self.find(self.parent[item])
return self.parent[item]
def union(self, x, y):
xroot = self.find(x)
yroot = self.find(y)
if self.rank[xroot] < self.rank[yroot]:
self.parent[xroot] = yroot
elif self.rank[xroot] > self.rank[yroot]:
self.parent[yroot] = xroot
else:
self.parent[yroot] = xroot
self.rank[xroot] += 1
This comprehensive cheatsheet covers a wide range of Python data structures, from the basic built-in types to more advanced custom implementations. Each section includes creation methods, common operations, and advanced techniques where applicable.
0
Top comments (0)