Implement Linked List With Ruby

Define Node

1
2
3
4
5
6
7
8
class Node
  attr_accessor :next, :value

  def initialize(value)
    @value = value
    @next  = nil
  end
end

Define Linked List

1
2
3
4
5
6
7
8
class LinkedList
  attr_accessor :head, :length

  def initialize
    @head = nil
    @length = 0
  end
end

Display Linked List

1
2
3
4
5
6
7
8
9
def show_all
  current_node = @head
  puts ":----- Linked List: ----->"

  while(current_node)
    puts "object_id: #{current_node.object_id} - value: #{current_node.value}\n"
    current_node = current_node.next
  end
end

Add New Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def add(value)
  current_node = @head

  if current_node
    while(current_node.next)
      current_node = current_node.next
    end
    current_node.next = Node.new(value)
  else
    @head = Node.new(value)
  end

  @length += 1
end

Delete A Node At Position

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def delete(position)
  return false if(!@head || position > @length)

  prev_node = current_node = @head
  i = 0

  while(current_node)
    if(i == position)
      prev_node.next = current_node.next
      return true
    end

    prev_node = current_node
    current_node = current_node.next
    i += 1
  end

  return false
end

Reverse Linked List

1
2
3
4
5
6
7
8
9
10
11
def reverse
  mid = @length / 2
  i = 1
  current_node = @head

  while(i <= mid)
    swap(current_node, find_nth_from_end_list(i))
    current_node = current_node.next
    i += 1
  end
end

Check Circular Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def is_circular_linked_list?
  return false if !@head
  hash = {}

  current_node = @head
  while(current_node)
    return false if(hash.key?(current_node.object_id))

    hash[current_node.object_id] = true
    current_node = current_node.next
  end

  return false
end

Full Example

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
class Node
  attr_accessor :next, :value

  def initialize(value)
    @value = value
    @next  = nil
  end
end

class LinkedList
  attr_accessor :head, :length

  def initialize
    @head = nil
    @length = 0
  end

  def show_all
    current_node = @head
    puts ":----- Linked List: ----->"

    while(current_node)
      puts "object_id: #{current_node.object_id} - value: #{current_node.value}\n"
      current_node = current_node.next
    end
  end

  def add(value)
    current_node = @head

    if current_node
      while(current_node.next)
        current_node = current_node.next
      end
      current_node.next = Node.new(value)
    else
      @head = Node.new(value)
    end

    @length += 1
  end

  def delete(position)
    return false if(!@head || position > @length)

    prev_node = current_node = @head
    i = 0

    while(current_node)
      if(i == position)
        prev_node.next = current_node.next
        return true
      end

      prev_node = current_node
      current_node = current_node.next
      i += 1
    end

    return false
  end

  # find node nth from the end of linked list
  def find_nth_from_end_list(n)
    return nil if (n < 0 || n > @length || !@head)

    current_node = @head
    i = 0

    while(current_node)
      if(i + n == @length)
        return current_node
      else
        i += 1
        current_node = current_node.next
      end
    end
  end

  # remove duplicate node
  def remove_duplicate
    current_node = @head
    hash = {}
    i = 0
    sum_of_deleted = 0

    while(current_node)
      if(hash.key?(current_node.value))
        # position in the next duplicate  will change after we remove any items
        delete(i - sum_of_deleted)
        sum_of_deleted += 1
      else
        hash[current_node.value] = true
      end

      i += 1
      current_node = current_node.next
    end
  end

  # remove middle node
  def remove_middle_node
    position = @length/2

    i = 0
    prev_node = current_node = @head

    while(current_node)
      if(i == position)
        prev_node.next = current_node.next
        break
      else
        prev_node = current_node
        current_node = current_node.next
        i += 1
      end
    end
  end

  def reverse
    mid = @length / 2
    i = 1
    current_node = @head

    while(i <= mid)
      swap(current_node, find_nth_from_end_list(i))
      current_node = current_node.next
      i += 1
    end
  end

  # plus two linked list
  def plus(l2)
    result = LinkedList.new
    curr1 = @head
    curr2 = l2.head
    remember_number = 0

    while(curr1 || curr2)
      val1 = curr1 ? curr1.value : 0
      val2 = curr2 ? curr2.value : 0

      sum = val1 + val2 + remember_number

      if sum >= 10
        sum %= 10
        remember_number = 1
      end

      result.add(sum)

      curr1 = curr1.next
      curr2 = curr2.next
    end

    result
  end

  def is_circular_linked_list?
    return false if !@head
    hash = {}

    current_node = @head
    while(current_node)
      return false if(hash.key?(current_node.object_id))

      hash[current_node.object_id] = true
      current_node = current_node.next
    end

    return false
  end

  private

  def swap(node1, node2)
    tmp_value = node2.value
    node2.value = node1.value
    node1.value = tmp_value
  end
end

Source

https://github.com/hdchinh/ruby_cracking_code/tree/master/linked_lists