Anonymous user
Doubly-linked list/Definition: Difference between revisions
→{{header|Lua}}
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 1,864:
1 -> 2 -> 3 -> 4
</pre>
=={{header|Lua}}==
<lang 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")</lang>
{{out}}
<pre>true
true 1
true 1,2
true 1,2,3
true 1,2,3,4
true 1,2,3,33,4
true 1,2,22,3,33,4
true 1,11,2,22,3,33,4
true 1,11,2,22,3,33,4,44
true 1,11,2,22,3,33,4,44,5
true 1,11,2,22,3,33,4,44,444,5
true 1,11,2,22,3,33,4,44,444,5,55
true 0,1,11,2,22,3,33,4,44,444,5,55
true -1,0,1,11,2,22,3,33,4,44,444,5,55
true -1,0,1,11,111,2,22,3,33,4,44,444,5,55
true -1,0,1,11,111,2,22,222,3,33,4,44,444,5,55
true -1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55
true -1,0,1,11,111,2,22,222,3,33,333,4,44,444,5,55,555</pre>
=={{header|M2000 Interpreter}}==
| |||