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.

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

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

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

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.

©2014-2018 Roblox Corporation. All rights reserved.

Roblox logos, names, and all related indicia are trademarks of Roblox Corporation.