Fundamental Data Structures

TL;DR

Data structures are ways to organize data in a computer so it can be used efficiently, impacting how quickly you can store, retrieve, and process information. Choosing the right data structure is crucial for solving problems effectively and optimizing your code's performance. We'll look at arrays, linked lists, stacks, and queues as core building blocks.

1. The Mental Model

Imagine you have a bunch of items you need to store. Data structures are like different kinds of containers or filing systems for those items, each with its own pros and cons for adding, finding, or removing things.

2. The Core Material

Let's break down some fundamental data structures:

Arrays

An array is like a row of mailboxes, all the same size, lined up one after another. Each mailbox has a number (its index), starting from 0. You can put one item in each mailbox.

• Pros:
  • Very fast to find an item if you know its index (direct access).
  • Data is stored contiguously in memory, which can be efficient.
• Cons:
  • Fixed size: once you create an array, you can't easily change its capacity. If you need more space, you usually have to create a whole new, bigger array and copy everything over.
  • Adding or removing items in the middle can be slow because you might have to shift many other items.

# Python list acts like a dynamic array
my_array = [10, 20, 30, 40]
print(f"Array: {my_array}")
print(f"Element at index 2: {my_array[2]}") # Accessing an element
my_array.append(50) # Adding an element (at the end)
print(f"Array after append: {my_array}")

Linked Lists

Photo by Jakub Zerdzicki on Pexels

A linked list is like a treasure hunt where each clue (a node) tells you where to find the next clue. Each node contains two pieces of information: the actual data, and a reference (or pointer) to the next node in the sequence.

• Pros:
  • Dynamic size: easily grow or shrink as needed, just add or remove nodes.
  • Efficient for inserting or deleting elements anywhere in the list because you only need to change a few pointers, not shift whole blocks of data.
• Cons:
  • Slower to access an element by its position (e.g., the 5th item) because you have to start from the beginning and follow the pointers one by one.
  • Uses more memory than an array for the same number of items because of the extra storage needed for pointers.

Here's a simple visualization of how nodes connect:

graph LR
    A["Node 1 (Data: 'A')"] --> B["Node 2 (Data: 'B')"]
    B --> C["Node 3 (Data: 'C')"]
    C --> D["Node 4 (Data: 'D')"]

Stacks

A stack is a special type of list where you can only add or remove items from one end, called the top. Think of a stack of plates: you can only add a new plate to the top, and you can only take the top plate off. This is known as LIFO (Last-In, First-Out).

• Key operations:
  • Push: Add an item to the top.
  • Pop: Remove the top item.
  • Peek: Look at the top item without removing it.

# Python list can be used as a stack
my_stack = []
my_stack.append("plate1") # Push
my_stack.append("plate2") # Push
my_stack.append("plate3") # Push
print(f"Stack after pushes: {my_stack}")
print(f"Top element (Peek): {my_stack[-1]}") # Peek
removed_item = my_stack.pop() # Pop
print(f"Popped: {removed_item}")
print(f"Stack after pop: {my_stack}")

Queues

A queue is another special list, like a line at a store. You add items to one end (the rear or tail) and remove them from the other end (the front or head). This is FIFO (First-In, First-Out).

• Key operations:
  • Enqueue: Add an item to the rear.
  • Dequeue: Remove the item from the front.

from collections import deque

# deque is efficient for queue operations
my_queue = deque()
my_queue.append("person1") # Enqueue
my_queue.append("person2") # Enqueue
my_queue.append("person3") # Enqueue
print(f"Queue after enqueues: {my_queue}")
served_person = my_queue.popleft() # Dequeue
print(f"Dequeued: {served_person}")
print(f"Queue after dequeue: {my_queue}")

3. Worked Example

Let's say you're building a simple browser history. Every time you visit a page, it's added. When you hit the "back" button, you go to the previous page.

This perfectly describes a stack.

1. Visit google.com: Push "google.com" onto the stack.
   Stack: ["google.com"]
2. Visit wikipedia.org: Push "wikipedia.org" onto the stack.
   Stack: ["google.com", "wikipedia.org"]
3. Visit python.org: Push "python.org" onto the stack.
   Stack: ["google.com", "wikipedia.org", "python.org"]
4. Hit "Back": Pop "python.org". You are now on "wikipedia.org".
   Stack: ["google.com", "wikipedia.org"]
5. Hit "Back" again: Pop "wikipedia.org". You are now on "google.com".
   Stack: ["google.com"]

browser_history = [] # Using a Python list as a stack

def visit_page(page_url):
    browser_history.append(page_url)
    print(f"Visited: {page_url}. Current history: {browser_history}")

def go_back():
    if browser_history:
        current_page = browser_history.pop()
        print(f"Went back from: {current_page}.")
        if browser_history:
            print(f"Now on: {browser_history[-1]}. Current history: {browser_history}")
        else:
            print("No more pages in history.")
    else:
        print("History is empty.")

visit_page("google.com")
visit_page("wikipedia.org")
visit_page("python.org")
go_back()
go_back()
visit_page("bing.com") # A new page after going back
go_back()

4. Key Takeaways

• Arrays offer fast direct access by index but are fixed-size and slow for middle insertions/deletions.
• Linked lists are flexible in size and efficient for insertions/deletions anywhere, but slow for direct access.
• Stacks operate on a LIFO (Last-In, First-Out) principle, like a stack of plates.
• Queues operate on a FIFO (First-In, First-Out) principle, like a waiting line.
• The choice of data structure critically impacts the performance and efficiency of your algorithms.
• Python lists can simulate both arrays (dynamically sized) and stacks easily.
• For efficient queues in Python, collections.deque is preferred over lists.

Common Mistakes to Avoid

Photo by KATRIN BOLOVTSOVA on Pexels

• Trying to change the size of a raw array after it's been created without making a new one and copying data.
• Using a linked list when you frequently need random access to elements by index, as it's slow.
• Confusing LIFO and FIFO: remember stack is LIFO, queue is FIFO.
• Not considering the time complexity of operations (e.g., inserting into the middle of a large array) when choosing a data structure.

5. Now Try It

Imagine you're managing print jobs for a printer. When a job is sent, it's added to a waiting list. The printer processes jobs in the order they were received.
1. Which fundamental data structure would you use to manage these print jobs?
2. Write a small Python snippet that adds three print jobs ("report.pdf", "image.jpg", "essay.docx") and then processes the first two.
3. What does your job list look like after these operations?
Success looks like correctly identifying the data structure and demonstrating its core operations (add/enqueue and process/dequeue).