Comprehensive Python Data Structures Cheat sheet

Comprehensive Python Data Structures Cheat sheet

Table of Contents

1. Lists
2. Tuples
3. Sets
4. Dictionaries
5. Strings
6. Arrays
7. Stacks
8. Queues
9. Linked Lists
10. Trees
11. Heaps
12. Graphs
13. 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