Doubly linked list in Lua

example.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.lua

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

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/

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