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

TL;DR

Linear data structures arrange data in a sequential manner, allowing you to access elements one after another. Arrays store elements in contiguous memory, while linked lists use pointers to connect elements. Stacks and queues are specialized linear structures that enforce specific access rules (LIFO and FIFO, respectively).

1. The Mental Model

Imagine a single line of people. Each person represents a piece of data. Linear data structures are like different ways of organizing and interacting with that line, whether it's a fixed-size queue, a dynamic chain, or a stack of plates.

2. The Core Material

Linear data structures are fundamental ways to organize data where elements are arranged sequentially, meaning each element has a predecessor and a successor (except for the first and last). This section covers three common types: Arrays, Linked Lists, and Stacks/Queues.

Arrays

An array is a collection of elements of the same data type stored in contiguous memory locations. This means all elements are right next to each other in RAM. Each element has an index, usually starting from 0, which allows for direct and fast access.

• Characteristics:

  • Fixed Size: Once declared, an array's size usually can't change.
  • Contiguous Memory: Elements are stored sequentially.
  • Direct Access (O(1)): You can access any element directly by its index (e.g., myArray[5]).
  • Insertion/Deletion: Can be slow (O(n)) as elements might need to be shifted.

• When to use: When you know the size of your data in advance and need fast access to elements by index.

# Example: Python list acting like a static array for demonstration
my_array = [10, 20, 30, 40, 50]
print(f"Array: {my_array}")
print(f"Element at index 2: {my_array[2]}") # O(1) access

# Attempting to insert in the middle (conceptual shift)
my_array.insert(2, 25) # In Python, this is O(n) because it shifts elements
print(f"Array after insert: {my_array}")

Linked Lists

Photo by Suki Lee on Pexels

A linked list is a collection of nodes where each node contains data and a "pointer" (or reference) to the next node in the sequence. Unlike arrays, linked list elements are not stored in contiguous memory.

• Characteristics:

  • Dynamic Size: Can grow or shrink easily.
  • Non-contiguous Memory: Nodes can be anywhere in memory.
  • Sequential Access (O(n)): To find an element, you might have to traverse from the beginning.
  • Efficient Insertion/Deletion (O(1) after finding position): You only need to update a few pointers, no shifting required.

• When to use: When you don't know the size of your data, or when frequent insertions and deletions are needed, especially in the middle of the structure.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

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

my_list = LinkedList()
my_list.append(10)
my_list.append(20)
my_list.append(30)
print("Linked List:")
my_list.display()

Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Think of a stack of plates: you always add a new plate to the top, and you always remove the top plate first.

• Operations:

  • push(): Adds an element to the top of the stack.
  • pop(): Removes and returns the top element from the stack.
  • peek(): Returns the top element without removing it.
  • isEmpty(): Checks if the stack is empty.

• When to use: Undo/redo functionality, function call stacks, expression evaluation.

Queues

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Think of a line at a store: the first person in line is the first person served.

• Operations:

  • enqueue(): Adds an element to the rear of the queue.
  • dequeue(): Removes and returns the front element from the queue.
  • front(): Returns the front element without removing it.
  • isEmpty(): Checks if the queue is empty.

• When to use: Task scheduling, breadth-first search, managing shared resources (e.g., print queue).

Here's a comparison of their core characteristics:

graph TD
    A["Linear Data Structures"] --> B["Arrays"]
    A --> C["Linked Lists"]
    A --> D["Stacks"]
    A --> E["Queues"]

    B -- "Memory: Contiguous" --> B1["Fast Random Access (O(1))"]
    B -- "Size: Fixed" --> B2["Slow Insert/Delete (O(n))"]

    C -- "Memory: Non-Contiguous" --> C1["Slow Random Access (O(n))"]
    C -- "Size: Dynamic" --> C2["Fast Insert/Delete (O(1) at ends/known position)"]

    D -- "Principle: LIFO (Last In, First Out)" --> D1["push() / pop() at one end (top)"]
    D --> D2["Applications: Undo/Redo, Call Stack"]

    E -- "Principle: FIFO (First In, First Out)" --> E1["enqueue() at rear, dequeue() at front"]
    E --> E2["Applications: Task Scheduling, Print Queue"]

3. Worked Example

Let's trace operations on a stack and a queue using Python's built-in list (which can behave as both).

Scenario: Process a sequence of numbers (10, 20, 30) using a stack and then a queue.

Stack Example (LIFO):

1. Start with an empty stack: []
2. push(10): [10]
3. push(20): [10, 20]
4. push(30): [10, 20, 30] (30 is at the top/end)
5. pop(): Returns 30. Stack is now [10, 20]
6. pop(): Returns 20. Stack is now [10]
7. push(40): [10, 40]
8. pop(): Returns 40. Stack is now [10]

# Stack implementation using Python list (append for push, pop for pop)
stack = []
print(f"Initial Stack: {stack}")

stack.append(10) # Push 10
stack.append(20) # Push 20
stack.append(30) # Push 30
print(f"Stack after pushes: {stack}")

popped_item = stack.pop() # Pop (removes 30)
print(f"Popped item: {popped_item}, Stack: {stack}")

popped_item = stack.pop() # Pop (removes 20)
print(f"Popped item: {popped_item}, Stack: {stack}")

stack.append(40) # Push 40
print(f"Stack after push 40: {stack}")

popped_item = stack.pop() # Pop (removes 40)
print(f"Popped item: {popped_item}, Stack: {stack}")

Queue Example (FIFO):

1. Start with an empty queue: []
2. enqueue(10): [10]
3. enqueue(20): [10, 20]
4. enqueue(30): [10, 20, 30] (10 is at the front)
5. dequeue(): Returns 10. Queue is now [20, 30]
6. dequeue(): Returns 20. Queue is now [30]
7. enqueue(40): [30, 40]
8. dequeue(): Returns 30. Queue is now [40]

from collections import deque # More efficient for queue operations than list

queue = deque() # Use deque for efficient appends and pops from both ends
print(f"\nInitial Queue: {list(queue)}")

queue.append(10) # Enqueue 10
queue.append(20) # Enqueue 20
queue.append(30) # Enqueue 30
print(f"Queue after enqueues: {list(queue)}")

dequeued_item = queue.popleft() # Dequeue (removes 10 from the front)
print(f"Dequeued item: {dequeued_item}, Queue: {list(queue)}")

dequeued_item = queue.popleft() # Dequeue (removes 20)
print(f"Dequeued item: {dequeued_item}, Queue: {list(queue)}")

queue.append(40) # Enqueue 40
print(f"Queue after enqueue 40: {list(queue)}")

dequeued_item = queue.popleft() # Dequeue (removes 30)
print(f"Dequeued item: {dequeued_item}, Queue: {list(queue)}")

4. Key Takeaways

• Arrays provide direct, O(1) access by index but have a fixed size and O(n) insertion/deletion costs.

• Linked Lists offer dynamic resizing and O(1) insertion/deletion (once position is found) but require O(n) traversal for access.