Programming in Lua : 11.3

This first edition was written for Lua 5.0. While still largely relevant for later versions, there are some differences.
The fourth edition targets Lua 5.3 and is available at Amazon and other bookstores.
By buying the book, you also help to support the Lua project.

Programming in Lua

Part II. Tables and Objects Chapter 11. Data Structures

11.3 – Linked Lists

Because tables are dynamic entities, it is easy to implement linked lists in Lua. Each node is represented by a table and links are simply table fields that contain references to other tables. For instance, to implement a basic list, where each node has two fields, next and value, we need a variable to be the list root:

    list = nil

To insert an element at the beginning of the list, with a value v, we do

    list = {next = list, value = v}

To traverse the list, we write:

    local l = list
    while l do
      print(l.value)
      l = l.next
    end

Other kinds of lists, such as double-linked lists or circular lists, are also implemented easily. However, you seldom need those structures in Lua, because usually there is a simpler way to represent your data without using lists. For instance, we can represent a stack with an (unbounded) array, with a field n pointing to the top.