Linear Data Structures: Arrays, Linked Lists, Stacks, Queues

TL;DR

You'll learn about arrays, linked lists, stacks, and queues—fundamental ways to organize data. Each structure stores data linearly but offers different trade-offs in terms of performance and flexibility. Understanding them is key to picking the right tool for your data management challenges.

1. The Mental Model

Imagine you need to store a list of items, like your grocery list or a queue at the bank. How you arrange those items impacts how easily you can add new ones, find existing ones, or remove old ones. Linear data structures are simply different ways of organizing data items sequentially, one after another, each with its own advantages and disadvantages. The core idea is about managing ordered collections efficiently.

2. The Core Material

When we talk about linear data structures, we're focusing on how data elements are arranged in a sequence. The key differences come down to how they're stored in memory and the operations they support efficiently.

Arrays: Contiguous Blocks of Memory

Photo by Maxim Landolfi on Pexels

An array is like a row of mailboxes, all perfectly lined up, right next to each other. Each mailbox has a number (its index), starting from 0.

The key characteristic of an array is that its elements are stored in contiguous memory locations. This means if you know where the first element is, you can calculate the exact memory address of any other element just by knowing its index and the size of each element. This makes accessing elements incredibly fast, what we call O(1) time complexity.

However, this contiguity comes with a cost: fixed size. When you create an array, you typically specify its size upfront. If you need to add more elements than the array can hold, you have to create a new, larger array and copy all the old elements over—a potentially expensive operation (O(N) time complexity, where N is the number of elements). Also, inserting or deleting an element in the middle requires shifting all subsequent elements, which is also O(N).

Here's how you'd typically work with arrays in Python (though Python lists are more dynamic than traditional arrays, they behave like dynamic arrays under the hood):

# Creating an array (Python list behaves like a dynamic array)
my_array = [10, 20, 30, 40, 50]
print(f"Original array: {my_array}")

# Accessing elements (O(1) operation)
first_element = my_array[0]
print(f"First element: {first_element}")

# Modifying an element (O(1) operation)
my_array[2] = 35
print(f"Array after modification: {my_array}")

# Adding an element (O(1) on average for dynamic arrays, O(N) worst case)
my_array.append(60)
print(f"Array after appending: {my_array}")

# Inserting an element (O(N) operation - elements need to shift)
my_array.insert(1, 15) # Insert 15 at index 1
print(f"Array after inserting: {my_array}")

# Deleting an element (O(N) operation - elements need to shift)
del my_array[3] # Delete element at index 3 (which was 35)
print(f"Array after deleting: {my_array}")

Linked Lists: Nodes Connected by Pointers

Photo by Santhosh Kanthala on Pexels

Imagine a scavenger hunt where each clue tells you where to find the next clue. That's a linked list. Instead of being stored next to each other in memory, elements (called nodes) in a linked list are scattered around. Each node contains two things: the actual data, and a "pointer" (or reference) to the next node in the sequence. The last node's pointer points to None.

The first node is called the head, and it's how you access the entire list.

graph LR
    A[Head] --> B{Node 1 | Data: A | Next: Node 2}
    B --> C{Node 2 | Data: B | Next: Node 3}
    C --> D{Node 3 | Data: C | Next: None}

This structure makes insertions and deletions incredibly efficient (O(1)) if you already have a reference to the node before the insertion/deletion point. You just update a couple of pointers. For example, to insert a new node between Node 1 and Node 2, you'd make Node 1 point to the new node, and the new node point to Node 2. No shifting required!

The downside is access time. If you want the 5th element, you can't just jump straight to it. You have to start at the head and traverse (follow the pointers) one by one until you reach the 5th node. This makes access O(N).

Here's a basic Python implementation of a singly linked list:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None # Pointer to the next node

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        elements = []
        while current:
            elements.append(current.data)
            current = current.next
        print(" -> ".join(map(str, elements)))

# Example usage
my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
print("Linked List:")
my_list.display() # Output: 10 -> 20 -> 30

Stacks: Last-In, First-Out (LIFO)

Photo by Shawn Stutzman on Pexels

Think of a stack of plates. You can only add a new plate to the top, and you can only take a plate from the top. The last plate you put on is the first one you'll take off. This is the LIFO (Last-In, First-Out) principle.

The main operations are:
* Push: Add an element to the top of the stack.
* Pop: Remove and return the top element from the stack.
* Peek/Top: Look at the top element without removing it.
* isEmpty: Check if the stack has any elements.

Stacks are often implemented using either arrays (Python lists are great for this) or linked lists. Array-based stacks are efficient if you always add/remove from the end.

# Stack implementation using a Python list
class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item) # Add to the end of the list

    def pop(self):
        if not self.is_empty():
            return self._items.pop() # Remove from the end of the list
        else:
            raise IndexError("pop from empty stack")

    def peek(self):
        if not self.is_empty():
            return self._items[-1] # Look at the last element
        else:
            raise IndexError("peek from empty stack")

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

# Example usage
my_stack = Stack()
my_stack.push(1)
my_stack.push(2)
my_stack.push(3)
print(f"Stack size: {my_stack.size()}") # Output: Stack size: 3
print(f"Top element: {my_stack.peek()}") # Output: Top element: 3
print(f"Popped: {my_stack.pop()}") # Output: Popped: 3
print(f"Stack size after pop: {my_stack.size()}") # Output: Stack size after pop: 2

Queues: First-In, First-Out (FIFO)

Photo by Yan Krukau on Pexels

Now think about a queue at a grocery store. The first person to join the queue is the first person to be served. This is the FIFO (First-In, First-Out) principle.

The main operations are:
* Enqueue: Add an element to the rear of the queue.
* Dequeue: Remove and return the front element from the queue.
* Front/Peek: Look at the front element without removing it.
* isEmpty: Check if the queue has any elements.

Queues can also be implemented with arrays or linked lists. For efficiency, particularly with frequent dequeues, a collections.deque (double-ended queue) in Python is ideal because it allows O(1) additions and removals from both ends. Using a standard list for a queue can be inefficient for dequeue if you pop from the front (O(N) for shifting).

from collections import deque

# Queue implementation using collections.deque
class Queue:
    def __init__(self):
        self._items = deque() # Use deque for efficient O(1) operations

    def enqueue(self, item):
        self._items.append(item) # Add to the right end (rear)

    def dequeue(self):
        if not self.is_empty():
            return self._items.popleft() # Remove from the left end (front)
        else:
            raise IndexError("dequeue from empty queue")

    def front(self):
        if not self.is_empty():
            return self._items[0] # Look at the first element
        else:
            raise IndexError("front from empty queue")

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

# Example usage
my_queue = Queue()
my_queue.enqueue("Alice")
my_queue.enqueue("Bob")
my_queue.enqueue("Charlie")
print(f"Queue size: {my_queue.size()}") # Output: Queue size: 3
print(f"Front element: {my_queue.front()}") # Output: Front element: Alice
print(f"Dequeued: {my_queue.dequeue()}") # Output: Dequeued: Alice
print(f"Queue size after dequeue: {my_queue.size()}") # Output: Queue size after dequeue: 2

3. Worked Example

Let's trace the operations of a stack and a queue with a sequence of actions.

Scenario: We start with an empty stack and an empty queue. We'll perform a mix of additions and removals and see how the contents change.

Stack Operations:

1. Push 10
2. Push 20
3. Push 30
4. Pop
5. Push 40
6. Pop
7. Peek

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)
        print(f"Push {item} -> Stack: {self._items}")

    def pop(self):
        if not self.is_empty():
            popped_item = self._items.pop()
            print(f"Pop {popped_item} -> Stack: {self._items}")
            return popped_item
        else:
            print("Stack is empty, cannot pop.")
            return None

    def peek(self):
        if not self.is_empty():
            peeked_item = self._items[-1]
            print(f"Peek {peeked_item} -> Stack: {self._items}")
            return peeked_item
        else:
            print("Stack is empty, cannot peek.")
            return None

    def is_empty(self):
        return len(self._items) == 0

print("--- Stack Trace ---")
my_stack_example = Stack()
my_stack_example.push(10) # Stack: [10]
my_stack_example.push(20) # Stack: [10, 20]
my_stack_example.push(30) # Stack: [10, 20, 30]
my_stack_example.pop()    # Popped 30. Stack: [10, 20]
my_stack_example.push(40) # Stack: [10, 20, 40]
my_stack_example.pop()    # Popped 40. Stack: [10, 20]
my_stack_example.peek()   # Peeked 20. Stack: [10, 20]

Expected Output Trace:

--- Stack Trace ---
Push 10 -> Stack: [10]
Push 20 -> Stack: [10, 20]
Push 30 -> Stack: [10, 20, 30]
Pop 30 -> Stack: [10, 20]
Push 40 -> Stack: [10, 20, 40]
Pop 40 -> Stack: [10, 20]
Peek 20 -> Stack: [10, 20]

Queue Operations:

1. Enqueue "A"
2. Enqueue "B"
3. Dequeue
4. Enqueue "C"
5. Dequeue
6. Front

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)
        print(f"Enqueue {item} -> Queue: {list(self._items)}")

    def dequeue(self):
        if not self.is_empty():
            dequeued_item = self._items.popleft()
            print(f"Dequeue {dequeued_item} -> Queue: {list(self._items)}")
            return dequeued_item
        else:
            print("Queue is empty, cannot dequeue.")
            return None

    def front(self):
        if not self.is_empty():
            front_item = self._items[0]
            print(f"Front {front_item} -> Queue: {list(self._items)}")
            return front_item
        else:
            print("Queue is empty, cannot peek.")
            return None

    def is_empty(self):
        return len(self._items) == 0

print("\n--- Queue Trace ---")
my_queue_example = Queue()
my_queue_example.enqueue("A") # Queue: ['A']
my_queue_example.enqueue("B") # Queue: ['A', 'B']
my_queue_example.dequeue()    # Dequeued 'A'. Queue: ['B']
my_queue_example.enqueue("C") # Queue: ['B', 'C']
my_queue_example.dequeue()    # Dequeued 'B'. Queue: ['C']
my_queue_example.front()      # Front 'C'. Queue: ['C']

Expected Output Trace:

--- Queue Trace ---
Enqueue A -> Queue: ['A']
Enqueue B -> Queue: ['A', 'B']
Dequeue A -> Queue: ['B']
Enqueue C -> Queue: ['B', 'C']
Dequeue B -> Queue: ['C']
Front C -> Queue: ['C']

4. Production Pitfalls & Best Practices

4.1 Real-World Best Practices

• Use Python's built-in list for dynamic arrays: For most array-like needs where size isn't fixed, Python's list is highly optimized and offers excellent performance for appends/pops from the end (amortized O(1)).
• Leverage collections.deque for queues: For true O(1) enqueue and dequeue operations, deque is the go-to. Don't implement a queue with a standard list where pop(0) is used, as this is O(N) and very slow for large queues.
• Choose list for simple stacks: For stacks, Python's list.append() and list.pop() are O(1) and perfectly suitable. There's usually no need for a custom stack class unless you're adding extra validation or methods.
• Consider linked lists for frequent middle insertions/deletions: If your problem involves a lot of insertions or deletions in the middle of a very large sequence, and random access isn't critical, a custom linked list implementation might outperform a dynamic array (list).
• Be explicit with operations: When using a list as a stack, name your variables and comments clearly (e.g., stack.append(item) as push, stack.pop() as pop) to communicate intent.

4.2 Common Bugs & Anti-Patterns

• Inefficient Queue Implementation:
  BAD:
  python my_bad_queue = [] my_bad_queue.append("task1") # Enqueue my_bad_queue.append("task2") task = my_bad_queue.pop(0) # Dequeue - O(N)! # All elements shift left after pop(0)
  FIXED:
  python from collections import deque my_good_queue = deque() my_good_queue.append("task1") # Enqueue - O(1) my_good_queue.append("task2") task = my_good_queue.popleft() # Dequeue - O(1)

• Modifying a List While Iterating (Index-based deletion):
  BAD:
  python my_list = [1, 2, 3, 4, 5] for i in range(len(my_list)): if my_list[i] % 2 == 0: my_list.pop(i) # This will skip elements or cause IndexError # e.g., if 2 is removed at index 1, 3 moves to index 1, but loop increments to 2, skipping 3
  FIXED (using list comprehension or iterating backwards):
  ```python
  # Option 1: List comprehension (creates a new list)
  my_list = [1, 2, 3, 4, 5]
  my_list = [x for x in my_list if x % 2 != 0] # Filters out even numbers
  print(f"Fixed list (comprehension): {my_list}") # Output: [1, 3, 5]

  Option 2: Iterate backwards (modifies in place safely)

  my_list_2 = [1, 2, 3, 4, 5]
  for i in range(len(my_list_2) - 1, -1, -1):
  if my_list_2[i] % 2 == 0:
  my_list_2.pop(i)
  print(f"Fixed list (backwards iteration): {my_list_2}") # Output: [1, 3, 5]
  ```

4.3 When to Use What (Decision Matrix)

5. Now Try It

Implement a function reverse_string(s) that takes a string s as input and returns the reversed string using a stack. You should only use the push and pop operations of a stack (you can use a Python list as your stack).

For example, reverse_string("hello") should return "olleh".

Success looks like: Your function correctly reverses the string by pushing characters onto the stack and then popping them off into a new string.