Doubly-linked list/Definition: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
|||
Line 1,864: | Line 1,864: | ||
1 -> 2 -> 3 -> 4 |
1 -> 2 -> 3 -> 4 |
||
</pre> |
</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}}== |
=={{header|M2000 Interpreter}}== |