We use cookies on this site to enhance your user experience

5 min

A linked list is a type of data structure. Because Articles/Table|tables are dynamic entities, it is easy to implement linked lists in Lua. Each node is represented by a Articles/Table|table and links are simply table fields that contain references to other Articles/Table|tables.

Types of Lists

Basic Singly Linked

Here’s a basic linked list. Each node has two fields, next (Articles/Table|table) and value (Articles/String|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
	-- ...output the value of the current node...
	print(entry.value)

	-- ... then 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

	-- Output the value of the current node
	print(entry.value)

	-- Move to next node
	entry = entry.next
end

Doubly Linked List

Here’s a doubly linked list. It is significantly more complicated than the singly linked list.

local function insert(a)
	return {
		-- Add node 'a' after node 'b', and return 'a' for convenience
		after = function(b)
			if b.next then
				a.next = b.next
				b.next.prev = a
			end
			a.prev = b
			b.next = a
			return a
		end,
		-- Add node 'a' before node 'b', and return 'a' for convenience
		before = function(b)
			if b.prev then
				a.prev = b.prev
				b.prev.next = a
			end
			a.next = b
			b.prev = a
			return a
		end
	}
end

local head = {value = "a"}
local current = head
current = insert({value = "b"}).after(current)
current = insert({value = "c"}).after(current)
current = insert({value = "d"}).after(current)
local tail = current

-- Traverse list
print("Forward iteration")
current = head
repeat
	print(current.value)
	current = current.next
until not current

print("Reverse iteration")
current = tail
repeat
	print(current.value)
	current = current.prev
until not current