Data Structures in Lua

Lua uses one general-purpose structure—the table—to represent arrays, records, sets, linked lists, matrices, queues, and graphs. The best representation depends on access patterns rather than on a special declaration.

Arrays and records

local colors = { "red", "green", "blue" }
for index, value in ipairs(colors) do
    print(index, value)
end

local user = { name = "Ada", active = true }
print(user.name)

Dense arrays conventionally begin at 1. The length operator is reliable only when there are no unexpected holes; keep an explicit count for sparse collections.

Sets and multisets

local set = { apple = true, orange = true }
if set.apple then print("present") end

local counts = {}
for _, word in ipairs({ "a", "b", "a" }) do
    counts[word] = (counts[word] or 0) + 1
end

Remove a set member by assigning nil, not false, if iteration should omit it.

Matrices

A matrix can be a table of rows:

local matrix = {
    { 1, 2, 3 },
    { 4, 5, 6 }
}
print(matrix[2][3]) -- 6

For a large sparse matrix, store only populated coordinates, using nested tables or a serialized (row, column) key. A flat dense array may improve locality: index (row - 1) * columns + column.

Lists and queues

local node = { value = "first", next = nil }
node.next = { value = "second", next = nil }

local Queue = {}
Queue.__index = Queue
function Queue.new() return setmetatable({ first = 0, last = -1 }, Queue) end
function Queue:push(value)
    self.last = self.last + 1
    self[self.last] = value
end
function Queue:pop()
    assert(self.first <= self.last, "empty queue")
    local value = self[self.first]
    self[self.first] = nil
    self.first = self.first + 1
    return value
end

Removing index 1 from an array repeatedly shifts every remaining element, so a first/last index queue is more efficient.

Graphs can map each node to a set or list of neighbors. Tables make all these models possible; document invariants such as indexing, ownership, ordering, and whether missing values differ from false.