Class: Algoru::SingleLinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/algoru/data_structure/linked_list/single_linked_list.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SingleLinkedList

Returns a new instance of SingleLinkedList.



15
16
17
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 15

def initialize
  @head = nil
end

Instance Method Details

#append(value) ⇒ Object

append a node



20
21
22
23
24
25
26
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 20

def append(value)
  if @head
    find_tail.next = Node.new(value)
  else
    @head = Node.new(value)
  end
end

#append_after(target, value) ⇒ Object

append node after target node



57
58
59
60
61
62
63
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 57

def append_after(target, value)
  node = find(target)

  old_next = node.next
  node.next = Node.new(value)
  node.next.next = old_next
end

#append_before(target, value) ⇒ Object

append node before target node



66
67
68
69
70
71
72
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 66

def append_before(target, value)
  node = find_before(target)

  old_next = node.next
  node.next = Node.new(value)
  node.next.next = old_next
end

#delete(target) ⇒ Object

delete target node



75
76
77
78
79
80
81
82
83
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 75

def delete(target)
  if @head.value == target
    @head = @head.next
    return
  end

  node = find_before(target)
  node.next = node.next.next
end

#find(target) ⇒ Object

find node which value equals target



39
40
41
42
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 39

def find(target)
  node = @head
  return node if node.value == target while (node = node.next)
end

#find_before(target) ⇒ Object

find node before target node



45
46
47
48
49
50
51
52
53
54
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 45

def find_before(target)
  node = @head

  return false if node.next.nil?
  return node if node.next.value == target

  while (node = node.next)
    return node if node.next && node.next.value == target
  end
end

#find_tail ⇒ Object

find tail node



29
30
31
32
33
34
35
36
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 29

def find_tail
  node = @head
  return node if node.next.nil?

  if node.next.nil?
    return node
  end while (node = node.next) # node = node.next means point current node address to the next node address
end

#print ⇒ Object

print node by order



86
87
88
89
90
91
 
# File 'lib/algoru/data_structure/linked_list/single_linked_list.rb', line 86

def print
  node = @head
  puts node

  puts node while (node = node.next)
end