Elementary Data Structures: Stacks, Queues, Linked Lists, and Trees

Why Elementary Structures Matter

Every advanced data structure covered later in this series — hash tables, balanced trees, graphs — is ultimately built from a small set of elementary structures: arrays, linked lists, and the abstractions layered on top of them. Understanding these fundamentals deeply, including their exact time complexity for each operation, is essential before moving to anything more sophisticated.

Stacks: Last-In, First-Out Access

A Stack is an abstract data type supporting insertion and deletion following a LIFO (Last-In, First-Out) policy: the most recently inserted element is always the first one removed. The two core operations are PUSH (insert) and POP (remove and return the most recent element).

STACK-EMPTY(S):
  return top == 0

PUSH(S, x):
  top = top + 1
  S[top] = x

POP(S):
  if STACK-EMPTY(S):
      error "underflow"
  else:
      top = top - 1
      return S[top + 1]

Implemented with an array and a simple top index, every stack operation runs in O(1) time. Stacks appear throughout computer science: function call management (the call stack), expression evaluation, undo functionality in software, and depth-first search traversal, covered later in this series.

Queues: First-In, First-Out Access

A Queue follows the opposite discipline, FIFO (First-In, First-Out): the earliest inserted element is the first one removed. The two core operations are ENQUEUE (insert at the tail) and DEQUEUE (remove from the head).

Implementing a queue efficiently with a fixed-size array requires a Circular Buffer approach, using separate head and tail indices that wrap around the array's end.

ENQUEUE(Q, x):
  Q[tail] = x
  if tail == Q.length:
      tail = 1
  else:
      tail = tail + 1

DEQUEUE(Q):
  x = Q[head]
  if head == Q.length:
      head = 1
  else:
      head = head + 1
  return x

Like stacks, both queue operations run in O(1) time. Queues are essential for breadth-first search, covered later in this series, task scheduling, and any scenario requiring processing in the exact order items arrive.

Linked Lists: Flexible, Pointer-Based Sequences

Unlike arrays, which require contiguous memory and have a fixed size, a Linked List stores elements in individually allocated nodes connected by pointers, allowing efficient insertion and deletion anywhere in the sequence without shifting other elements.

Singly Linked Lists

Each node in a Singly Linked List stores a value and a pointer to the next node, with the last node's pointer set to a special null value.

Structure of each node:
  key
  next  (pointer to the following node, or NIL if last)

LIST-SEARCH(L, k):
  x = L.head
  while x ≠ NIL and x.key ≠ k:
      x = x.next
  return x

Searching takes O(n) time in the worst case, since it may require traversing the entire list. Insertion at the head takes O(1) time, but insertion at an arbitrary position requires first finding that position, taking O(n) time overall unless a direct pointer to the target location is already available.

Doubly Linked Lists

A Doubly Linked List adds a second pointer to each node, referencing the previous node as well as the next one. This extra pointer makes deletion significantly more efficient when a pointer to the node itself is already available.

Structure of each node:
  key
  next  (pointer to the following node)
  prev  (pointer to the preceding node)

LIST-DELETE(L, x):
  if x.prev ≠ NIL:
      x.prev.next = x.next
  else:
      L.head = x.next
  if x.next ≠ NIL:
      x.next.prev = x.prev

Given a direct pointer to node x, deletion runs in O(1) time, since neither the previous nor next node needs to be located by searching — they are directly accessible through x's own pointers. This is a meaningful advantage over singly linked lists, where deleting a node requires first finding its predecessor by searching from the head.

A Practical Simplification: Sentinels

Many linked list implementations use a Sentinel, a dummy node that does not represent a real element but simplifies boundary conditions by eliminating special-case checks for the head and tail of the list. A circular, doubly linked list with a sentinel allows every insertion and deletion to use exactly the same code, without checking whether the list is empty or whether an operation affects the first or last real element.

Representing Rooted Trees

Trees require more sophisticated pointer structures than linear lists, since each node may have a variable number of children.

Binary Trees: The Simple Case

For a Binary Tree, where every node has at most two children, representation is straightforward: each node stores pointers to its left child, right child, and optionally its parent.

Structure of each node:
  key
  p       (pointer to parent, or NIL for the root)
  left    (pointer to left child, or NIL)
  right   (pointer to right child, or NIL)

This representation is used extensively for binary search trees and other binary tree structures covered later in this series.

Trees with Unbounded Branching: Left-Child, Right-Sibling

For a general tree, where a node might have any number of children, storing a separate pointer for every possible child is impractical, since the number of children is not known in advance and can vary widely between nodes. The elegant Left-Child, Right-Sibling representation solves this using only two pointers per node, regardless of how many children that node actually has.

Structure of each node:
  key
  p              (pointer to parent)
  left-child     (pointer to the node's first/leftmost child)
  right-sibling  (pointer to the node's next sibling to the right)

Each node points to only its leftmost child directly; to reach that child's siblings, the algorithm follows the leftmost child's right-sibling pointer repeatedly, effectively encoding an arbitrary-arity tree as a specific kind of binary tree.

Example: a node with three children A, B, C

Using left-child/right-sibling:
node.left-child → A
A.right-sibling → B
B.right-sibling → C
C.right-sibling → NIL (no more siblings)

To visit all children, start at node.left-child
and repeatedly follow right-sibling pointers

This representation elegantly handles trees of arbitrary and varying branching factor using a constant amount of memory per node, exactly two pointers, regardless of how many actual children each node has.

Why Mastering These Structures Matters

Every data structure discussed later in this series — hash tables using linked lists to handle collisions, binary search trees using the pointer-based node structure introduced here, and even graph representations using adjacency lists — builds directly on these elementary structures and their associated time complexities. A solid, intuitive grasp of exactly how and why each elementary operation achieves its stated running time is the foundation for reasoning correctly about every more advanced structure that follows.