Create a gist now

Instantly share code, notes, and snippets.

Doubly linked list in Lua
require("list")
local a = { 3 }
local b = { 4 }
local l = list({ 2 }, a, b, { 5 })
l:pop()
l:shift()
l:push({ 6 })
l:unshift({ 7 })
l:remove(a)
l:insert({ 8 }, b)
print("length", l.length)
for v in l:iterate() do print(v[1]) end
list = {}
list.__index = list
setmetatable(list, { __call = function(_, ...)
local t = setmetatable({ length = 0 }, list)
for _, v in ipairs{...} do t:push(v) end
return t
end })
function list:push(t)
if self.last then
self.last._next = t
t._prev = self.last
self.last = t
else
-- this is the first node
self.first = t
self.last = t
end
self.length = self.length + 1
end
function list:unshift(t)
if self.first then
self.first._prev = t
t._next = self.first
self.first = t
else
self.first = t
self.last = t
end
self.length = self.length + 1
end
function list:insert(t, after)
if after then
if after._next then
after._next._prev = t
t._next = after._next
else
self.last = t
end
t._prev = after
after._next = t
self.length = self.length + 1
elseif not self.first then
-- this is the first node
self.first = t
self.last = t
end
end
function list:pop()
if not self.last then return end
local ret = self.last
if ret._prev then
ret._prev._next = nil
self.last = ret._prev
ret._prev = nil
else
-- this was the only node
self.first = nil
self.last = nil
end
self.length = self.length - 1
return ret
end
function list:shift()
if not self.first then return end
local ret = self.first
if ret._next then
ret._next._prev = nil
self.first = ret._next
ret._next = nil
else
self.first = nil
self.last = nil
end
self.length = self.length - 1
return ret
end
function list:remove(t)
if t._next then
if t._prev then
t._next._prev = t._prev
t._prev._next = t._next
else
-- this was the first node
t._next._prev = nil
self._first = t._next
end
elseif t._prev then
-- this was the last node
t._prev._next = nil
self._last = t._prev
else
-- this was the only node
self._first = nil
self._last = nil
end
t._next = nil
t._prev = nil
self.length = self.length - 1
end
local function iterate(self, current)
if not current then
current = self.first
elseif current then
current = current._next
end
return current
end
function list:iterate()
return iterate, self, nil
end
@decuant
decuant commented Apr 28, 2014

I've succesfully compiled this version with lua 5.2, thanks for the explanation

this site lists incorrect code instead (I have multiple errors)

http://www.nova-fusion.com/2012/11/16/linked-lists-in-lua/

@gamepdc
gamepdc commented Jul 1, 2016

There's bug in method remove. self._last, self._first used in remove method. And self.last, self.first used in other methods.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment