110 lines
3.5 KiB
Lua
110 lines
3.5 KiB
Lua
-- 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")
|