Creating linked-lists in lua?

Help and Feedback Scripting Support
#1

Any way to create linked lists in lua? As in similar way you can do it in python with a data type, is there any way do it in lua whole not writing out the nodes yourselves?

#2

This Belongs in #help-and-feedback:scripting-support

#4

There’s no built-in method as far as I’m aware. You’d have to use a library for it, or write your own. It shouldn’t be too hard, though; it just wouldn’t be as efficient as a language’s own actual implementation. Here’s a pretty naive implementation of a singly-linked list that’s as poorly performant—if not worse than—an array. (This is more of a proof of concept than anything intended to be used in production.)

local linkedList = {}

local function linkedListIterFactory(list)
	return function(list, element)
		return element.next
	end, list, {next = list.first}
end

function linkedList:Add(element)
	local element = {value = element}

	if not self.first then
		self.first = element
	else
		self._final.next = element
	end

	self._final = element
	return element
end

function linkedList:Remove(element)
	assert(element.next or element == self._final, "not a member of linked list") -- make sure it's in *a* linked list
	local previous = nil

	for item in linkedListIterFactory(self) do
		if element == item then
			if previous then
				previous.next = element.next
			else
				self.first = element.next
			end

			return
		end

		previous = item
	end

	error("not a member of linked list") -- couldn't find when looping thru
end

-- OPTIONAL OOP STUFF
function linkedList.new()
	local self = {}
	setmetatable(self, {__index = linkedList})

	return self
end

-- QUICK EXAMPLES:
local list = linkedList.new()

local three = list:Add(3)
local four = list:Add(4)
print(three.value, three.next.value)

for i = 5, 15 do
	list:Add(i)
end

print("loop 1:")
for element in linkedListIterFactory(list) do
	print(element.value)
end

local nine = four.next.next.next.next.next
list:Remove(nine)

print("loop 2:")
for element in linkedListIterFactory(list) do
	print(element.value)
end

local _, current = nil, four.next
for i = 1, 3 do
	_, current = list:Remove(current), current.next
end

print("loop 3:")
for element in linkedListIterFactory(list) do
	print(element.value)
end
9 Likes
#5

i recommend watching suphi kaner’s explanation on this. great video and a great explanation.

Otherwise just use his custom module

I know it is around 2 hours, but it is defo worth watching

1 Like