The topic is ways to store sequences of values! A "sequence" means that you have many things, and you care about the order of things: you have a first thing, a second thing, a third thing, etc.

Arrays

An array is a way to store a sequence of values in order so that all of the values are "next to" each other.

If collection is an array, the elements are

• collection[1]
• collection[2]
• collection[3]
• etc

All the values are "next to" each other inside collection.

Lua arrays are simple to make. An array of the first three Greek letters is

alphabetArray = {"alpha", "beta", "gamma"}

This is "shorthand" for the more explicit

alphabetArray = {
    [1] = "alpha",
    [2] = "beta",
    [3] = "gamma",
}

print(alphabetArray[1]) --> alpha
print(alphabetArray[2]) --> beta
print(alphabetArray[3]) --> gamma

ie, you just put the ith element at index [i].

In Lua, you can find out how many elements are in array by using the # operator: #collection is 0 for an empty array, 15 for an array that has values at entries [1], [2], ..., [15], etc.

Linked Lists

A linked list is a way to store a sequence of values in a bunch of different places; each value points to the next value.

If collection is a linked list, the elements could be

• collection.first
• collection.rest.first
• collection.rest.rest.first
• collection.rest.rest.rest.first
• collection.rest.rest.rest.rest.first
• etc

Unlike an array, you cannot immediately know how many elements a linked list has or what value is at any position other than the first! That's because you have to follow .rests n-1 times to get to the nth value.

However, you can represent an empty linked list as false or nil. A linked list with at least one value is a table with a .head, the first value, and a .rest a linked list of the rest of the data.

A linked list of the first three Greek letters is

alphabetLinkedList = {
    first = "alpha",
    rest = {
        first = "beta",
        rest = {
            first = "gamma",
            rest = nil,
        },
    },
}

This is a bit wordy! A function that sticks one element in front of a list is traditionally called cons:

function cons(first, rest)
    return {
        first = first,
        rest = rest,
    }
end

alphabetLinkedList = cons("alpha", cons("beta", cons("gamma", nil)))

print(alphabetLinkedList.first) --> alpha
print(alphabetLinkedList.rest.first) --> beta
print(alphabetLinkedList.rest.rest.first) --> gamma

Linked lists are typically operated on recursively. For example, here is a recursive function that tells you how long a linked list is:

function length(list)
    if not list then
        -- nil is a length-0 linked list
        return 0
    end

    -- This list is one element, then `rest`.
    -- So the length of `list` is one more than the length of `list.rest`
    return 1 + length(list.rest)
end

print(length(alphabetLinkedList)) --> 3

Here's one that lets you get the ith thing from a linked list:

function get(list, i)
    if i == 1 then
        -- We're looking for the first thing!
        assert(list, "list must not be empty")
        return list.first
    end

    -- The ith thing in this list is (i-1)th in the rest
    -- because we are moving past the first element
    return get(list.rest, i - 1)
end

print(get(alphabetLinkedList, 1)) --> alpha
print(get(alphabetLinkedList, 2)) --> beta
print(get(alphabetLinkedList, 3)) --> gamma

Intrusive Linked List

The difference between an "intrusive" data structure and a "non-intrusive" data structure is not important in dynamic languages like Lua.

First, an intrusive data-structure only makes sense when your values are tables (the simple string example above won't work).

For a linked list, it just means getting rid of the .first field -- a (non-empty) list simply has all of the fields you're interested in!

For example, consider this array-of-letter-informations:

local array = {
    {name = "alpha", letter = "a"},
    {name = "beta", letter = "b"},
    {name = "gamma", letter = "c"},
}

As a non-intrusive linked list, it could look like this:

alphabetLinkedList = {
    first = {name = "alpha", letter = "a"},
    rest = {
        first = {name = "beta", letter = "b"},
        rest = {
            first = {name = "gamma", letter = "c"},
            rest = nil,
        },
    },
}

As an intrusive linked list, it would look like this;

alphabetLinkedList = {
    -- data from `first`
    name = "alpha",
    letter = "a",

    -- rest of list
    rest = {
        -- data from `first`
        name = "beta",
        letter = "b",

        -- rest of list
        rest = {
            -- data from `first`
            name = "gamma",
            letter = "c",

            -- rest of list
            rest = nil,
        },
    },
}

The only thing I did was "flatten" the first field into the list.

In Lua, you're probably going to use intrusive linked lists more often -- you create them by just setting .rest or .next to the next thing in the list!

In languages like C++ or Java, intrusive lists are much less common.