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
Here's a basic linked list. Each node has two fields, next (table) and value (string).
--The "head". of the list - start at nil
local head = nil
-- Each entry becomes a new head, with a "next" member pointing to the old head
head = {next = head, value = "d"}
head = {next = head, value = "c"}
head = {next = head, value = "b"}
head = {next = head, value = "a"}
--Pick an entry to start iterating from
local entry = head
-- while there is another node to move to
while entry do
-- print the value of the current node
print(entry.value)
-- move to next node
entry = entry.next
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.
Here's a circularly linked list. It's slightly more complicated.
--Last entry in the list
local tail = {value = "d"}
--Add remaining entries
local head = tail
head = {next = head, value = "c"}
head = {next = head, value = "b"}
head = {next = head, value = "a"}
--Link the last node back to the first node
tail.next = head
--Pick an entry to start iterating from
local entry = head
--Iterate over the list 3 times
for i = 1, 12 do
-- back at the start
if entry == head then
print("Starting at the beginning!")
end
-- print the value of the current node
print(entry.value)
-- move to next node
entry = entry.next
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
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