blob: 99a23501858ab5212e1e464e959aeb2d247e1f96 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
local LinkedList = {}
LinkedList.__index = LinkedList
function LinkedList.new()
local list = {elements = {}}
setmetatable(list, LinkedList)
return list
end
function LinkedList:addback(payload)
if payload == nil then
error("Need a payload!", 2)
end
local element = { payload = payload }
if self.head then
local tail = self.head.prev
self.head.prev = element
tail.next = element
element.next = self.head
element.prev = tail
else
self.head = element
element.next = element
element.prev = element
end
self.elements[element] = true
return element
end
function LinkedList:addfront(payload)
self.head = self:addback(payload)
return self.head
end
function LinkedList:remove(element)
if self.elements[element] == nil then
error("Element not in list!", 2)
end
if self.head == element then
if element.next == element then
self.head = nil
else
self.head = element.next
end
end
element.prev.next = element.next
element.next.prev = element.prev
self.elements[element] = nil
end
function LinkedList:popfirst()
if self.head == nil then
return nil
end
local element = self.head
if element.next == element then
self.head = nil
else
self.head = element.next
element.next.prev = element.prev
element.prev.next = element.next
end
self.elements[element] = nil
return element.payload
end
function LinkedList:poplast()
if self.head == nil then
return nil
end
self.head = self.head.prev
return self:popfirst()
end
function LinkedList:first()
return self.head and self.head.payload
end
function LinkedList:last()
return self.head and self.head.prev.payload
end
function LinkedList:empty()
return self.head == nil
end
return LinkedList
|