The encoding: how complex structures hide in simple ones

Here is a confusion you meet in a serious codebase: you open an HTML parser and the DOM “tree” is not a tree of objects with children. It is a flat array, and a node is a bundle of indices into that array. You open a priority queue and the “tree” is an array where index arithmetic is the parent-child relationship. You read about a graph and find a list of lists, a map of lists, or a two-dimensional array. All of them are called “the graph.”

These are encodings: deliberate choices for representing a structure in the primitives your language provides. A data structure is a concept; a representation is a choice. This article covers the small catalogue of ways arrays, objects, tables, and tuples stand in for trees, lists, queues, tries, and graphs. The useful skill is seeing the encoding underneath the code you read.

The raw material: why arrays are the substrate

Start with the primitive. An array is the one structure every language agrees on, and the reference texts are unusually precise about why it can play so many roles. The advanced data-structures reference states the physical fact that makes arrays special: “An array is stored as a contiguous block of memory, and each element’s address can be obtained by adding its index within the array to the offset of the first element.”

That sentence explains the rest. An array’s index is not a label; it is an address calculation. Reading array[i] is offset + i, one step, regardless of the array’s size - this is the $O(1)$ random access the What O(n) article teaches. Contiguity also gives locality: the elements sit next to each other in memory, so walking a few of them costs a few cache lines, not a pointer chase across the heap. Random access and locality explain why so many structures get encoded into arrays instead of being built as pointer-connected nodes. The hash table makes the move explicit. The self-taught programmer’s guide asks: “What if, for an arbitrary object, we had a function that takes that object’s key and converts it to an array index, so we know exactly where the object should be stored? This is how hash tables work.” A hash table is a map encoded in an array by agreement on a function. The hash tables article explains the cost of that agreement; this article applies the same principle more broadly.

The encodings

Here is the catalogue. Each entry makes the same move: take a structure you imagine as boxes and arrows, then store it in an array, object, or tuple.

Tree in an array: the binary heap. The site’s binary trees article mentions “the heap that puts a tree back inside an array” - this is that sentence, unpacked. Store the heap’s nodes in level order, root at index 0. Then the children of the node at index $i$ are at $2i + 1$ and $2i + 2$, and its parent is at $(i - 1) / 2$. There are no pointers. The index arithmetic is the tree structure. A heap with five elements is the array [2, 5, 7, 9, 8] - node 1 (value 5) has children at indices 3 and 4 (values 9 and 8), and the array order is exactly the level order of the tree. That is why the Dijkstra article could call the priority queue “the heap that made the algorithm famous” without drawing it: the tree lives in the array, and the array’s index math is what sift and percolate manipulate.

Linked list in an array: the next index. A linked list is defined by its “next” pointer. When you cannot afford a pointer per node - or the nodes must not move - make that pointer an index. Each slot stores a value and the index of the next slot, and a special index (often -1) means “end.” Allocators use this shape: a free list threaded through the slots of an array of fixed-size blocks. The list of free blocks costs no extra memory beyond the blocks themselves. The index is a pointer; it just happens to be a number.

Queue in an array: the ring. A queue has two ends: one for arrival and one for departure. Encode it in an array with two indices that move forward and wrap around at the end - the circular buffer. The stacks-queues article quotes the Lua reference on the extreme version: “with 64-bit integers, such a queue can run for thirty thousand years, doing ten million insertions per second, before it has problems with overflows.” Two numbers and one array. That is the whole structure.

Stack-encoded queue: the transfer. The site’s Queue with Two Stacks exercise turns the encoding principle into a puzzle: a queue is not a primitive in the language, so represent it as two stacks and move elements between them exactly when needed. Do the exercise alongside this article. It makes the claim concrete: the structure (queue) and the representation (two stacks) are different things, and the gap between them is where the algorithm lives.

Trie in an array: children as indices. Your HTML parser. A trie is a tree of nodes, each with a fixed set of children (the alphabet). Encode the nodes in an array and give each node a starting index, with the children at consecutive positions - the child for character c is at start + c. A 26-letter trie becomes one array, a few index calculations, and no pointers. That is the shape a parser uses when it wants the whole structure in one contiguous block. The “node” is not an object; it is a range of indices.

Graph as adjacency: lists, tables, maps. The graph article’s “model the problem as a graph” is an encoding instruction, and each language has its idiomatic spelling. JavaScript stores adjacency as an array of arrays or an object of arrays; Lua, with only tables, stores it as a table of tables; Elixir, with terms, stores it as a map from node to list of neighbors - which is precisely what the Dijkstra article’s graph variable is: %{a: [{:b, 4}, {:c, 2}], ...}. Same graph, three spellings, one concept.

Record as tuple. Elixir’s tuples are fixed-width records, and a two-child tree has a canonical spelling: {value, left, right}, with nil for a missing child. The next section shows this encoding in three languages at once.

Three languages, one tree

Here is the same binary tree - value 5, left child 3, right child 8 - encoded in the primitives of each language on the site. All three programs compute the same sum, 16, and all three were executed to prove it.

In JavaScript, a tree is an object whose fields are more objects:

const t = {
  value: 5,
  left: { value: 3, left: null, right: null },
  right: { value: 8, left: null, right: null }
};

function sum(n) {
  return n === null ? 0 : n.value + sum(n.left) + sum(n.right);
}
// sum(t) === 16

In Lua, the same shape, because the table is the only structure: a tree is a table whose fields are more tables.

local t = {value = 5, left = {value = 3, left = nil, right = nil},
           right = {value = 8, left = nil, right = nil}}

local function sum(n)
  if n == nil then return 0 end
  return n.value + sum(n.left) + sum(n.right)
end
-- sum(t) == 16

In Elixir, a tree is a tuple - a fixed-width record - with the same recursive spelling:

defmodule Tree do
  # {value, left, right}, with nil for a missing child
  def sum(nil), do: 0
  def sum({v, l, r}), do: v + sum(l) + sum(r)
end

tree = {5, {3, nil, nil}, {8, nil, nil}}
# Tree.sum(tree) == 16

Three languages, one structure, three representations. Each representation is the language’s answer to the encoding question. JavaScript’s primitives are the array and the object, so the tree is objects all the way down. Lua’s primitive is the table, and the Lua introduction’s “one structure, three jobs” is this principle in the language’s terms: the table is array, map, object, and record, and a tree is a table of tables because there is nothing else. Elixir’s primitives are terms - lists, tuples, maps - and the tuple-tree is the encoding the language’s own designers reach for. Pattern matching (sum({v, l, r})) makes the encoding legible: matching on the shape is the same move as the algorithm.

Immutability changes the trade-offs. JavaScript and Lua encode with mutable objects; a “node” is an object, and editing the tree mutates it in place. Elixir’s tuples are immutable, so the same tree is copied on change - this is the price the reading Elixir article describes as the language’s model. It is also why Elixir’s tree encodings tend toward immutable structural sharing of maps and tuples rather than the mutate-the-child-object style a JS programmer reaches for first.

The skill: read the encoding first

The useful question is simple: what is the encoding? When you read a parser and see a flat array of nodes, the structure is not missing. It is encoded, and the encoding is the interesting part. When you read [2, 5, 7, 9, 8] and are told it is a heap, the tree is not invisible; it is the index math. The algorithms-past-the-interview article names this move as the heart of the interview’s structure-selection question; this article gives you the vocabulary for the representation half. “Which structure?” and “encoded in what?” are two questions. The second is where the language’s primitives - and the constraints of contiguity, immutability, and index-as-pointer - decide the answer.

Where to go next

• Queue with Two Stacks - the encoding principle as an exercise: a queue, represented as two stacks.
• Binary trees: where the log in O(log n) lives
  • the tree that started it, and the heap that encodes it in an array.
• Hash tables: the O(1) that has fine print
  • the archetype: a map encoded in an array by a function, and what the encoding costs.
• Dijkstra’s algorithm: when every hop costs something
  • a graph as a map of lists, and the heap that makes the frontier cheap.
• Stacks, queues, and associative arrays
  • the three shapes, and the Lua “one structure, three jobs” twist.
• Reading Elixir as a JS developer
  • the primitives side of the question, in the two languages this site teaches most.

A data structure is a concept, and a representation is a choice - which primitive encodes the concept, and how. The same tree is three objects, three tables, or one tuple. The same graph is a list of lists, a table of tables, or a map of lists. The same queue is a ring of indices, two stacks, or a pair of pointers. None of these is the “real” structure. The structure is the concept; the encoding is how the concept gets a runtime. Ask “what is the encoding?” Then the flat array in the HTML parser stops being a confusing implementation detail. It becomes the answer to a question you can name.