Class: RubyDataStructures::SinglyLinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/RubyDataStructures/singly_linked_list.rb

Direct Known Subclasses

DoublyLinkedList

Defined Under Namespace

Classes: Element

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SinglyLinkedList

Initializes the SinglyLinkedList



3
4
5
6
 
# File 'lib/RubyDataStructures/singly_linked_list.rb', line 3

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

Instance Method Details

#delete(key) ⇒ Object

Removes the first element with a given key from the linked list Arguments: key => Key of the element to be removed



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/RubyDataStructures/singly_linked_list.rb', line 44

def delete(key)
  element = self.head
  prev_element = @sentinel
  
  while (element != @sentinel) && (element.key != key)
    prev_element = element
    element = element.next
  end

  if element == @sentinel
    raise "Argument Error - No element with the key found"
  else
    prev_element.next = element.next
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  self.head == @sentinel
end

#head ⇒ Object 



8
9
10
 
# File 'lib/RubyDataStructures/singly_linked_list.rb', line 8

def head
  @sentinel.next
end

#insert(item) ⇒ Object

Splices an element onto the front of the linked list Arguments: item => Value to store in the element to be inserted



23
24
25
26
27
 
# File 'lib/RubyDataStructures/singly_linked_list.rb', line 23

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

#reset ⇒ Object 



16
17
18
 
# File 'lib/RubyDataStructures/singly_linked_list.rb', line 16

def reset
  @sentinel.next = @sentinel
end

#search(key) ⇒ Object

Returns the first element with a given key Arguments: key => Key of the element to be searched for



32
33
34
35
36
37
38
39
 
# File 'lib/RubyDataStructures/singly_linked_list.rb', line 32

def search(key)
  element = self.head
  while (element != @sentinel) && (element.key != key)
    element = element.next
  end

  return element
end