Class: RubyDataStructures::DoublyLinkedList

Inherits:
SinglyLinkedList show all
Defined in:
lib/RubyDataStructures/doubly_linked_list.rb

Defined Under Namespace

Classes: Element

Instance Method Summary collapse

Methods inherited from SinglyLinkedList

#empty?, #head, #search

Constructor Details

#initialize ⇒ DoublyLinkedList

Overrides the initialize method in SinglyLinkedList Initializes the DoublyLinkedList



5
6
7
8
 
# File 'lib/RubyDataStructures/doubly_linked_list.rb', line 5

def initialize
  @sentinel = RubyDataStructures::DoublyLinkedList::Element.new(self, nil)
  self.reset
end

Instance Method Details

#delete(key) ⇒ Object

Overrides the delete method in SinglyLinkedList to optimize the implementation.



34
35
36
37
38
39
40
41
42
43
 
# File 'lib/RubyDataStructures/doubly_linked_list.rb', line 34

def delete(key)
  element = search(key)
  
  if element == @sentinel
    raise "Argument Error - No element with the key found"
  else
    element.previous.next = element.next
    element.next.previous = element.previous
  end
end

#insert(item) ⇒ Object

Overrides the insert method in SinglyLinkedList to also set/update

+previous+ attributes to the elements



24
25
26
27
28
29
30
 
# File 'lib/RubyDataStructures/doubly_linked_list.rb', line 24

def insert(item)
  element = RubyDataStructures::DoublyLinkedList::Element.new(self, item)
  element.next = @sentinel.next
  @sentinel.next = element
  element.next.previous = element
  element.previous = @sentinel
end

#reset ⇒ Object

Extends the reset method in SinglyLinkedList to also set previous attribute to the sentinel



12
13
14
15
 
# File 'lib/RubyDataStructures/doubly_linked_list.rb', line 12

def reset
  super
  @sentinel.previous = @sentinel
end

#tail ⇒ Object

Returns the last element of the linked list



18
19
20
 
# File 'lib/RubyDataStructures/doubly_linked_list.rb', line 18

def tail
  @sentinel.previous
end