As an example of creating custom data structures in Lua, I thought I'd give a little demonstration of a linked lists implementation. Note that this isn't going to be an in-depth tutorial or anything; for the most part I'll just be showing pieces of the code.

Linked lists are wonderful data structures, perfect if you need to efficiently add, remove, and iterate through elements. The one trade off is that you can't find an element by an index.

There are a few kinds of linked lists, the two most common are singly and doubly linked lists. Every kind of linked list hold a bunch of nodes which maintain references to each other. A singly linked list holds a reference to the first node, and each node holds a reference to the next node. A doubly linked list holds a reference to the first and last nodes, and each node holds a reference to the next and previous nodes. Take a look at the Wikipedia page if you want more details.

I've decided to implement the doubly linked list. It's not quite as efficient the singly linked list, but it's more versatile as it allows reverse iteration. Let's start with some basic OOP:

``````list = {}
list.__index = list

setmetatable(list, { __call = function(_, ...)
local t = setmetatable({}, list)
for _, v in ipairs{...} do t:push(v) end
end })``````

This allows the user to create new linked lists like this:

``x = list(a, b, c, d)``

Note that all the elements must be tables to support the holding of references.

The first function I'll show is the simple `push` function. It appends an element to the end of the list:

``````function list:push(t)
if self.last then
self.last._next = t
t._prev = self.last
self.last = t
else
-- this is the first node
self.first = t
self.last = t
end

self.length = self.length + 1
end``````

And here's the corresponding `pop` function, which removes the last element from the list and returns it:

``````function list:pop()
if not self.last then return end
local ret = self.last

if ret._prev then
ret._prev._next = nil
self.last = ret._prev
ret._prev = nil
else
-- this was the only node
self.first = nil
self.last = nil
end

self.length = self.length - 1
return ret
end``````

For some more flexibility in where and what we add and remove, here's the `insert` and `remove` functions:

``````function list:insert(t, after)
if after then
if after._next then
after._next._prev = t
t._next = after._next
else
self.last = t
end

t._prev = after
after._next = t
self.length = self.length + 1
elseif not self.first then
-- this is the first node
self.first = t
self.last = t
end
end``````
``````function list:remove(t)
if t._next then
if t._prev then
t._next._prev = t._prev
t._prev._next = t._next
else
-- this was the first node
t._next._prev = nil
self._first = t._next
end
elseif t._prev then
-- this was the last node
t._prev._next = nil
self._last = t._prev
else
-- this was the only node
self._first = nil
self._last = nil
end

t._next = nil
t._prev = nil
self.length = self.length - 1
end``````

`insert` inserts the element into the list after the node specified by `after`. If `after` isn't specified, it will only add the element if no other nodes exist the list. `remove` is capable of removing the first or last element, or anything in between them.

The final thing we'll look at is iterator support:

``````local function iterate(self, current)
if not current then
current = self.first
elseif current then
current = current._next
end

return current
end

function list:iterate()
return iterate, self, nil
end``````

This is forward iteration only, but it isn't hard to implement a reverse iterator.

To cap things off, here's a usage example:

``````require("list")

local a = { 3 }
local b = { 4 }
local l = list({ 2 }, a, b, { 5 })

l:pop()
l:shift()
l:push({ 6 })
l:unshift({ 7 })
l:remove(a)
l:insert({ 8 }, b)
print("length", l.length)
for v in l:iterate() do print(v) end``````

If you'd like the full source, plus some extra functions, check out gist #4084042.