Define the data structure for a complete Doubly Linked List.

 The structure should support adding elements to the head, tail and middle of the list. 
 The structure should not allow circular loops


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


-- Doubly Linked List in Lua 6/15/2020 db
-------------------
-- IMPLEMENTATION:
-------------------
 
local function Node(data)
  return { data=data } --implied: return { data=data, prev=nil, next=nil }
end
 
local List = {
  head = nil,
  tail = nil,
  insertHead = function(self, data)
    local node = Node(data)
    if (self.head) then
      self.head.prev = node
      node.next = self.head
      self.head = node
    else
      self.head = node
      self.tail = node
    end
    return node
  end,
  insertTail = function(self, data)
    local node = Node(data)
    if self.tail then
      self.tail.next = node
      node.prev = self.tail
      self.tail = node
    else
      self.head = node
      self.tail = node
    end
    return node
  end,
  insertBefore = function(self,mark,data)
    if (mark) then
      local node = Node(data)
      if (mark == self.head) then
        self.head.next = node
        node.next = self.head
        self.head = node
      else
        mark.prev.next = node
        node.prev = mark.prev
        mark.prev = node
        node.next = mark
      end
      return node
    else
      -- if no mark given, then insertBefore()==insertHead()
      return self:insertHead(data)
    end
  end,
  insertAfter = function(self,mark,data)
    if (mark) then
      local node = Node(data)
      if (mark == self.tail) then
        self.tail.next = node
        node.prev = self.tail
        self.tail = node
      else
        mark.next.prev = node
        node.next = mark.next
        mark.next = node
        node.prev = mark
      end
      return node
    else
      -- if no mark given, then insertAfter()==insertTail()
      return self:insertTail(data)
    end
  end,
  values = function(self)
    local result, node = {}, self.head
    while (node) do result[#result+1], node = node.data, node.next end
    return result
  end,
}
List.__index = List
setmetatable(List, {__call=function(self) return setmetatable({},self) end })
 
---------
-- TEST:
---------
local function validate(list, expected)
  local values = list:values()
  local actual = table.concat(values, ",")
  print(actual==expected, actual)
end
local list = List()                      validate(list, "")
local n1   = list:insertTail(1)          validate(list, "1")
local n2   = list:insertTail(2)          validate(list, "1,2")
local n3   = list:insertTail(3)          validate(list, "1,2,3")
local n4   = list:insertTail(4)          validate(list, "1,2,3,4")
local n33  = list:insertAfter(n3, 33)    validate(list, "1,2,3,33,4")
local n22  = list:insertAfter(n2, 22)    validate(list, "1,2,22,3,33,4")
local n11  = list:insertAfter(n1, 11)    validate(list, "1,11,2,22,3,33,4")
local n44  = list:insertAfter(n4, 44)    validate(list, "1,11,2,22,3,33,4,44")
local n5   = list:insertTail(5)          validate(list, "1,11,2,22,3,33,4,44,5")
local n444 = list:insertBefore(n5, 444)  validate(list, "1,11,2,22,3,33,4,44,444,5")
local n55  = list:insertAfter(nil, 55)   validate(list, "1,11,2,22,3,33,4,44,444,5,55")
local n0   = list:insertHead(0)          validate(list, "0,1,11,2,22,3,33,4,44,444,5,55")
local nm1  = list:insertBefore(nil, -1)  validate(list, "-1,0,1,11,2,22,3,33,4,44,444,5,55")
local n111 = list:insertBefore(n2, 111)  validate(list, "-1,0,1,11,111,2,22,3,33,4,44,444,5,55")
local n222 = list:insertAfter(n22, 222)  validate(list, "-1,0,1,11,111,2,22,222,3,33,4,44,444,5,55")
local n333 = list:insertBefore(n4, 333)  validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55")
local n555 = list:insertAfter(n55, 555)  validate(list, "-1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55,555")