-
Notifications
You must be signed in to change notification settings - Fork 0
/
linked_lists.rb
executable file
·114 lines (101 loc) · 2.15 KB
/
linked_lists.rb
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#!/usr/bin/env ruby
class Node
attr_accessor :value, :next_node
def initialize(value = nil, next_node = nil)
@value = value
@next_node = next_node
end
end
class LinkedList
attr_accessor :head
def initialize(head = nil)
@head = head
end
def append(value)
if @head
current = @head
current = current.next_node until current.next_node.nil?
current.next_node = Node.new(value)
else
@head = Node.new(value) unless @head
end
end
def prepend(value)
@head ? @head = Node.new(value, @head) : append(value)
end
def size
count = 0
current = @head
while current
count += 1
current = current.next_node
end
count
end
def head
@head
end
def tail
current = @head
loop do
return current if current.next_node.nil?
current = current.next_node
end
end
def at(index)
return head if index == 0
current = @head
index.times { current = current.next_node }
current
end
def pop
if size == 1
@head = nil
else
current = self.at(size - 2)
current.next_node = nil
end
end
def contains?(value)
current = head
while current
return true if current.value == value
current = current.next_node
end
false
end
def find(value)
index = 0
current = head
while current
return index if current.value == value
current = current.next_node
index += 1
end
nil
end
def insert_at(index, value)
return append(value) if index >= size
return prepend(value) if index == 0
current_node = head
(index-1).times { current_node = current_node.next_node }
current_node.next_node = Node.new(value, current_node.next_node)
end
def remove_at(index)
return nil if index >= size
temp_left = @head
temp_right = @head
(index-1).times { temp_left = temp_left.next_node}
(index).times { temp_right = temp_right.next_node}
temp_left.next_node = temp_right.next_node
end
def to_s
str = ""
node = @head
until node.nil?
str += "(#{node.value.inspect}) -> "
node = node.next_node
end
str += "nil"
end
end