Tables all the way down: learning algorithms without standard library magic

Lua is famous for its minimalism. While Python, Java, and C++ ship extensive standard libraries with specialized collections - vectors, hash maps, treemaps, queues, double-ended queues, sets, priority queues, and records - Lua intentionally ships almost none of them. The language provides a single, general data structure: the table.

When you write algorithms in Lua, you cannot lean on standard library magic. There is no import collections or java.util.PriorityQueue. Every abstract data type (ADT) you need must be assembled directly from tables. This design can feel bare at first, but it is one of the most effective ways to understand how data structures actually work. When you build stacks, queues, hash sets, and min-heaps from raw tables, you are forced to reason about memory layout, indexing arithmetic, and algorithmic cost from first principles.

The single data structure: tables as everything

Under the hood, a Lua table is an associative array that pairs keys with values. Both keys and values can be any valid Lua value except nil. Because of this flexibility, a single table can play many different roles depending on how you structure its keys.

Associative arrays (hash maps)

When keys are strings or arbitrary identifiers, tables behave like dictionaries or hash maps:

local counts = {}
local word = "algorithm"

counts[word] = (counts[word] or 0) + 1

Dot syntax is syntactic sugar for string keys: counts.algorithm is identical to counts["algorithm"].

Sequences (arrays)

When keys are positive consecutive integers starting at 1, a table behaves as a sequence (an array or list):

local primes = {2, 3, 5, 7, 11}

print(primes[1]) -- 2
print(#primes)   -- 5

Sets

Lua has no built-in Set type. To create a set, use the elements as table keys and map each to true:

local visited = {}

local function add(set, item)
  set[item] = true
end

local function contains(set, item)
  return set[item] == true
end

add(visited, "node_a")
print(contains(visited, "node_a")) -- true
print(contains(visited, "node_b")) -- false

Membership testing is an $O(1)$ hash table lookup.

Records and objects

Tables can hold both state and functions. By convention, functions can be assigned as fields or declared using colon syntax:

local Point = {}

function Point.new(x, y)
  return {x = x, y = y}
end

function Point.distance(self, other)
  local dx = self.x - other.x
  local dy = self.y - other.y
  return math.sqrt(dx * dx + dy * dy)
end

local p1 = Point.new(0, 0)
local p2 = Point.new(3, 4)
print(Point.distance(p1, p2)) -- 5.0

The 1-based indexing mental model

The most famous quirk of Lua is that sequences are indexed starting from 1 rather than 0.

local items = {"alpha", "beta", "gamma"}
print(items[1]) -- "alpha"
print(items[0]) -- nil (not an error!)

This choice matches mathematical notation and natural language (“the first item is at index 1”), but it requires care when translating algorithms originally described in 0-based languages.

The length operator (#) and the hole hazard

The length operator #t returns the size of a sequence. In Lua, a sequence is defined as a table where the positive integer keys form a contiguous range from 1 to $n$ with no nil values in between.

If a table has “holes” - nil values between positive integer keys - the behavior of #t is formally undefined in the Lua specification. It may return any index $k$ such that t[k] ~= nil and t[k + 1] == nil.

local sparse = {10, 20, nil, 40, 50}
-- Warning: #sparse is not guaranteed to return 5! It may return 2 or 5.

When using tables as arrays in algorithm implementations:

• Always append with table.insert(t, val) or t[#t + 1] = val.
• Never insert nil into an array unless you are deliberately shortening it from the tail with t[#t] = nil.
• If an algorithm requires sparse keys (such as a coordinate map or a disjoint set), treat the table as an associative map and do not rely on #t.

Building ADTs from bare tables

Because Lua lacks container libraries, algorithm problems frequently require writing small, tailored ADTs.

Stacks (LIFO)

A stack is the simplest ADT in Lua. Because Lua arrays can be appended and truncated at the end in $O(1)$ amortized time, a plain table serves as an efficient stack:

local Stack = {}
Stack.__index = Stack

function Stack.new()
  return setmetatable({items = {}}, Stack)
end

function Stack:push(value)
  self.items[#self.items + 1] = value
end

function Stack:pop()
  local n = #self.items
  if n == 0 then return nil end
  local val = self.items[n]
  self.items[n] = nil -- clear slot for garbage collection
  return val
end

function Stack:peek()
  return self.items[#self.items]
end

function Stack:is_empty()
  return #self.items == 0
end

Using metatables with __index = Stack enables object-oriented invocation: local s = Stack.new(); s:push(10).

Queues (FIFO) with offset buffers

A common mistake in Lua is implementing a FIFO queue by calling table.remove(t, 1) to dequeue. table.remove(t, 1) shifts every subsequent element left by one slot, turning a dequeue operation into an $O(n)$ disaster.

To build an $O(1)$ queue, track two indices: first and last. Elements are appended at last and read from first without shifting elements:

local Queue = {}
Queue.__index = Queue

function Queue.new()
  return setmetatable({first = 1, last = 0, data = {}}, Queue)
end

function Queue:push(value)
  self.last = self.last + 1
  self.data[self.last] = value
end

function Queue:pop()
  if self:is_empty() then return nil end
  local val = self.data[self.first]
  self.data[self.first] = nil -- prevent memory leaks
  self.first = self.first + 1
  return val
end

function Queue:is_empty()
  return self.first > self.last
end

function Queue:size()
  return self.last - self.first + 1
end

Because 64-bit integers do not realistically overflow during a program’s execution, the first and last pointers can increment indefinitely while maintaining strict $O(1)$ performance per operation.

Min-heaps (priority queues)

Tree-based algorithms like Dijkstra’s shortest path, A* search, or finding the $k$th largest element require a priority queue. A binary heap can be packed flat into a table using 1-based arithmetic:

• For a node at index $i$:
  • Left child: $2i$
  • Right child: $2i + 1$
  • Parent: $\lfloor i / 2 \rfloor$

local MinHeap = {}
MinHeap.__index = MinHeap

function MinHeap.new()
  return setmetatable({data = {}}, MinHeap)
end

function MinHeap:push(val)
  local data = self.data
  data[#data + 1] = val
  self:_sift_up(#data)
end

function MinHeap:pop()
  local data = self.data
  local n = #data
  if n == 0 then return nil end
  local root = data[1]
  data[1] = data[n]
  data[n] = nil
  if n > 1 then
    self:_sift_down(1)
  end
  return root
end

function MinHeap:peek()
  return self.data[1]
end

function MinHeap:size()
  return #self.data
end

function MinHeap:_sift_up(idx)
  local data = self.data
  local parent = math.floor(idx / 2)
  while idx > 1 and data[idx] < data[parent] do
    data[idx], data[parent] = data[parent], data[idx]
    idx = parent
    parent = math.floor(idx / 2)
  end
end

function MinHeap:_sift_down(idx)
  local data = self.data
  local n = #data
  while true do
    local left = 2 * idx
    local right = 2 * idx + 1
    local smallest = idx

    if left <= n and data[left] < data[smallest] then
      smallest = left
    end
    if right <= n and data[right] < data[smallest] then
      smallest = right
    end

    if smallest ~= idx then
      data[idx], data[smallest] = data[smallest], data[idx]
      idx = smallest
    else
      break
    end
  end
end

Notice how clean the parent and child index calculations are: because Lua is 1-based, the left child is simply 2 * idx and parent is math.floor(idx / 2). In 0-based languages, these formulas require offsets (2 * idx + 1 and math.floor((idx - 1) / 2)).

Contrast with functional lists: Lua tables vs. Elixir data structures

Comparing Lua to a functional language like Elixir highlights two very different worldviews on data representation.

Feature	Lua Tables	Elixir Lists and Maps
Mutability	Mutable in place (t[k] = v).	Immutable. Updates produce a new data structure sharing memory.
Primary List Type	Array packed into a hash table ($O(1)$ random access).	Singly linked list ($O(1)$ prepend/head access, $O(n)$ random index access).
Indexing	1-based by default.	0-based when using Enum.at/2 (though index lookups are discouraged).
Memory Reuse	In-place mutation modifies the existing reference directly.	Structural sharing allows new immutable terms to share identical subtrees.
Identity / Equality	Tables compare by reference identity (t1 == t2 is true only if they are the same table).	Values compare by structural equality ([1, 2] == [1, 2] is true).

In Lua, an algorithm like depth-first search can pass a single visited table through recursive calls, mutating it directly:

local function dfs(graph, node, visited)
  if visited[node] then return end
  visited[node] = true
  for _, neighbor in ipairs(graph[node] or {}) do
    dfs(graph, neighbor, visited)
  end
end

In Elixir, state cannot be mutated in place. You either accumulate a MapSet explicitly through function returns or pass it via recursion:

def dfs(graph, node, visited) do
  if MapSet.member?(visited, node) do
    visited
  else
    visited = MapSet.put(visited, node)
    neighbors = Map.get(graph, node, [])

    Enum.reduce(neighbors, visited, fn neighbor, acc ->
      dfs(graph, neighbor, acc)
    end)
  end
end

Understanding both paradigms makes you a stronger algorithm designer. Lua teaches you how data structures live in flat, mutable memory, while Elixir teaches you how data structures transform cleanly over immutable streams.

Exercise connections

Put these concepts into practice across the site’s problems and interactive lessons:

• Reading Lua as a JS developer - A quick translation guide covering Lua syntax, truthiness, and operators.
• Lua Introduction - Step-by-step interactive drills covering table manipulation, 1-based loops, and language mechanics.
• Two Sum - Use a Lua table as an associative array to store and look up complement values in $O(1)$ time.
• Valid Parentheses - Implement a LIFO stack on a table to match opening and closing delimiters.
• Kth Largest Element in an Array - Build a min-heap from scratch using 1-based child/parent formulas.
• Stacks, queues, and associative arrays - The conceptual companion covering how these shapes function across multiple programming paradigms.