Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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 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 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