Linked lists

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

a b c

d

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

• Arrays
• Stack
• 11.3 - Linked Lists