Class: DoublyLinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/collection_framework/doubly_linked_list/list.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DoublyLinkedList 



8
9
10
11
12
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 8

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

Instance Attribute Details

#head ⇒ Object

Returns the value of attribute head.



6
7
8
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 6

def head
  @head
end

#last ⇒ Object

Returns the value of attribute last.



6
7
8
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 6

def last
  @last
end

#length ⇒ Object

Returns the value of attribute length.



6
7
8
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 6

def length
  @length
end

Instance Method Details

#add_at_head(val) ⇒ nil 



30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 30

def add_at_head(val)
  new_node = DoublyLinkedListNode.new(val, @head, nil)
  if @length.zero?
    @head = new_node
    @last = new_node
  else
    @head.prev = new_node
    @head = new_node
  end
  @length += 1
  nil
end

#add_at_index(index, val) ⇒ nil 



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 60

def add_at_index(index, val)
  return if index > length

  case index
  when length
    add_at_tail(val)
  when 0
    add_at_head(val)
  else
    current_index = 0
    current_pointer = @head
    prev_pointer = nil
    while current_index != index
      current_pointer = current_pointer.next
      prev_pointer = current_pointer.prev
      current_index += 1
    end
    new_node = DoublyLinkedListNode.new(val, current_pointer, prev_pointer)
    current_pointer.prev = new_node
    prev_pointer.next = new_node
    @length += 1
  end
end

#add_at_tail(val) ⇒ nil 



45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 45

def add_at_tail(val)
  new_node = DoublyLinkedListNode.new(val, nil, @last)
  if @length.zero?
    @head = new_node
  else
    @last.next = new_node
  end
  @last = new_node
  @length += 1
  nil
end

#delete_at_index(index) ⇒ nil 



86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 86

def delete_at_index(index)
  return if index >= @length

  case index
  when 0
    @head = @head.next
    @head&.prev = nil
  when @length - 1
    @last = @last.prev
    @last.next = nil
  else
    current_index = 0
    current_pointer = @head
    prev_pointer = nil
    while current_index != index
      current_pointer = current_pointer.next
      prev_pointer = current_pointer.prev
      current_index += 1
    end
    prev_pointer.next = current_pointer.next
    current_pointer.next.prev = prev_pointer
  end
  @length -= 1
end

#get(index) ⇒ Integer 



16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 16

def get(index)
  return -1 if index >= @length

  current_index = 0
  pointer = @head
  while current_index != index
    pointer = pointer.next
    current_index += 1
  end
  pointer&.val
end

#to_s ⇒ String 



112
113
114
115
116
117
118
119
120
121
 
# File 'lib/collection_framework/doubly_linked_list/list.rb', line 112

def to_s
  current_pointer = @head
  str = ''
  until current_pointer.nil?
    str += current_pointer.val.to_s
    current_pointer = current_pointer.next
    str += '->' unless current_pointer.nil?
  end
  str
end