A linked list is a type of data structure.
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.
Types of Lists
Basic Singly Linked
Example
Here's a basic linked list. Each node has two fields, next (table) and value (string).
local list = nil -- create entry point
list = {next = list, value = "d"} -- we begin by creating
list = {next = list, value = "c"} -- the last node and
list = {next = list, value = "b"} -- progressively move
list = {next = list, value = "a"} -- towards the first node
local l = list -- current node (first)
while l do -- while there is another node to move to
print(l.value) -- read value from one node in the list
l = l.next -- move to next node
end
Circularly Linked
The circularly linked list is almost identical to the singly linked list, except you include a link from the last node to the first one.
Be careful though, as it is possible to accidentally try to traverse it forever once inside a loop.
Example
Here's a circularly linked list. It's slightly more complicated.
local list, first
first = {value = "d"}
list = first
list = {next = list, value = "c"}
list = {next = list, value = "b"}
list = {next = list, value = "a"}
first.next = list; -- link first created node to the last created node
local l = list -- current node (first)
for i = 1, 12 do -- limit to just 3 times through the list
if (i + 3) % 4 == 0 then -- if i == 1, 5, or 9 then
print("Starting at the beginning!")
end
print(l.value) -- read value from one node in the list
l = l.next -- move to next node
end
Starting at the beginning!
a
b
c
d
Starting at the beginning!
a
b
c
d
Starting at the beginning!
a
b
c
d
Doubly Linked List
Example
Here's a doubly linked list. It is significantly more complicated than the singly linked list.
--
-- Create list
--
local last, current
local function node(val) -- create new node
if last then -- skip if we're starting the list
last.next = val -- add forward reference in last node
end
val.prev = last -- add back reference in new node
last = val -- update last node
return val
end
local function forward()
last = current
current = current.next
return current
end
local function backward()
last = current
current = current.prev
return current
end
local function restore() -- incase we reach the end
current = last
end
current = node {pos = 1} -- anchor list
node {pos = 2}
node {pos = 3}
--
-- Manipulate list
--
print("Countin' Up Cap'n!")
repeat
print(current.pos)
until not forward() -- go forwards through the list
-- when the loop above exited, current became nil
restore() -- restore current
print("Countin' Down Cap'n!")
repeat
print(current.pos)
until not backward() -- go backwards through the list
Countin' Up Cap'n!
1
2
3
Countin' Down Cap'n!
3
2
1
Even More Lists
It is possible to create many other types of linked lists to suit your needs.
However, usually linked lists are not the most efficient data structure. Check the See Also section for other data structures.
See Also
