Linked list

(Redirected from 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[edit]

Basic Singly Linked[edit]

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[edit]

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[edit]

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
Forward iteration
a
b
c
d
Reverse iteration
d
c
b
a

Even More Lists[edit]

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[edit]