tables in lua

Tables are the most important part in lua..all the data structures are based on tables.

Tables in Lua are not a data structure; they are the data structure. All structures that other languages offer---arrays, records, lists, queues, sets---are represented with tables in Lua. More to the point, tables implement all these structures efficiently.

In traditional languages, such as C and Pascal, we implement most data structures with arrays and lists (where lists = records + pointers). Although we can implement arrays and lists using Lua tables (and sometimes we do that), tables are more powerful than arrays and lists; many algorithms are simplified to the point of triviality with the use of tables. For instance, you seldom write a search in Lua, because tables offer direct access to any type.

It takes a while to learn how to use tables efficiently. Here, we will show how you can implement typical data structures with tables and will provide some examples of their use. We will start with arrays and lists, not because we need them for the other structures, but because most programmers are already familiar with them. We have already seen the basics of this material in our chapters about the language, but I will repeat it here for completeness.

---

We implement arrays in Lua simply by indexing tables with integers. Therefore, arrays do not have a fixed size, but grow as we need. Usually, when we initialize the array we define its size indirectly. For instance, after the following code

    a = {}    -- new array
    for i=1, 1000 do
      a[i] = 0
    end

any attempt to access a field outside the range 1-1000 will return nil, instead of zero.

You can start an array at index 0, 1, or any other value:

    -- creates an array with indices from -5 to 5
    a = {}
    for i=-5, 5 do
      a[i] = 0
    end

However, it is customary in Lua to start arrays with index 1. The Lua libraries adhere to this convention; so, if your arrays also start with 1, you will be able to use their functions directly.

We can use constructors to create and initialize arrays in a single expression:

    squares = {1, 4, 9, 16, 25, 36, 49, 64, 81}

Such constructors can be as large as you need (well, up to a few million elements).

---

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.