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.