Class: DSA::LinkedList::Singly

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/dsa-ruby/linked_list.rb

Overview

DSA::LinkedList::Singly - Singly linked list implementation.

Each node points only to the next node. Supports push (prepend), append, pop (from front), delete, find, and reverse!. Includes Enumerable for functional-style operations.

Examples:

list = DSA::LinkedList::Singly.new
list.push(1).push(2).push(3)
list.pop        # => 3
list.to_a       # => [2, 1]
list.reverse!
list.to_a       # => [1, 2]

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DSA::LinkedList::Singly

Initialize a new empty singly linked list.



65
66
67
68
 
# File 'lib/dsa-ruby/linked_list.rb', line 65

def initialize
  @head = nil
  @size = 0
end

Instance Method Details

#append(val) ⇒ DSA::LinkedList::Singly

Appends a value to the end of the list.

Examples:

list.append(1).append(2)
list.to_a  # => [1, 2]

Parameters:

  • val (Object) —

    the value to append

Returns:



90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/dsa-ruby/linked_list.rb', line 90

def append(val)
  new_node = Node.new(val)
  if @head.nil?
    @head = new_node
  else
    node = @head
    node = node.next while node.next
    node.next = new_node
  end
  @size += 1
  self
end

#delete(val) ⇒ Boolean

Deletes the first occurrence of a value from the list.

Examples:

list.push(1).push(2).push(3)
list.delete(2)  # => true
list.delete(5)  # => false

Parameters:

  • val (Object) —

    the value to delete

Returns:

  • (Boolean) —

    true if the value was found and deleted



139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/dsa-ruby/linked_list.rb', line 139

def delete(val)
  return false unless @head

  if @head.val == val
    @head = @head.next
    @size -= 1
    return true
  end

  node = @head
  while node.next
    if node.next.val == val
      node.next = node.next.next
      @size -= 1
      return true
    end
    node = node.next
  end

  false
end

#each {|val| ... } ⇒ Enumerator

Yields each value in the list from front to back.

Examples:

list.push(1).push(2).push(3)
list.each { |x| puts x }  # prints 3, 2, 1

Yields:

  • (val) —

    yields each value to the block

Returns:

  • (Enumerator) —

    if no block given



246
247
248
249
250
251
252
253
 
# File 'lib/dsa-ruby/linked_list.rb', line 246

def each(&block)
  return enum_for(:each) unless block_given?
  node = @head
  while node
    yield node.val
    node = node.next
  end
end

#empty? ⇒ Boolean

Checks if the list is empty.

Examples:

list = DSA::LinkedList::Singly.new
list.empty?  # => true

Returns:

  • (Boolean) —

    true if the list contains no elements



216
217
218
 
# File 'lib/dsa-ruby/linked_list.rb', line 216

def empty?
  @size == 0
end

#find(val) ⇒ Node?

Finds the first node with the given value.

Examples:

list.push(1).push(2)
list.find(2)  # => #<Node @val=2>
list.find(5)  # => nil

Parameters:

  • val (Object) —

    the value to find

Returns:

  • (Node, nil) —

    the node if found, nil otherwise



169
170
171
172
173
174
175
176
 
# File 'lib/dsa-ruby/linked_list.rb', line 169

def find(val)
  node = @head
  while node
    return node if node.val == val
    node = node.next
  end
  nil
end

#peek ⇒ Object

Returns the value at the front of the list without removing it.

Examples:

list.push(1).push(2)
list.peek  # => 2

Returns:

  • (Object) —

    the value at the front

Raises:

  • (IndexError) —

    if the list is empty



126
127
128
129
 
# File 'lib/dsa-ruby/linked_list.rb', line 126

def peek
  raise IndexError, "list is empty" unless @head
  @head.val
end

#pop ⇒ Object

Removes and returns the value at the front of the list.

Examples:

list.push(1).push(2)
list.pop  # => 2

Returns:

  • (Object) —

    the value at the front

Raises:

  • (IndexError) —

    if the list is empty



110
111
112
113
114
115
116
117
 
# File 'lib/dsa-ruby/linked_list.rb', line 110

def pop
  raise IndexError, "list is empty" unless @head

  val = @head.val
  @head = @head.next
  @size -= 1
  val
end

#push(val) ⇒ DSA::LinkedList::Singly

Prepends a value to the front of the list.

Examples:

list.push(2).push(1)
list.to_a  # => [1, 2]

Parameters:

  • val (Object) —

    the value to prepend

Returns:



77
78
79
80
81
 
# File 'lib/dsa-ruby/linked_list.rb', line 77

def push(val)
  @head = Node.new(val, @head)
  @size += 1
  self
end

#reverse! ⇒ DSA::LinkedList::Singly

Reverses the list in-place.

Examples:

list.push(1).push(2).push(3)
list.reverse!
list.to_a  # => [1, 2, 3]

Returns:



185
186
187
188
189
190
191
192
193
194
195
196
197
198
 
# File 'lib/dsa-ruby/linked_list.rb', line 185

def reverse!
  return self unless @head

  prev = nil
  curr = @head
  while curr
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
  end
  @head = prev
  self
end

#size ⇒ Integer

Returns the number of elements in the list.

Examples:

list.push(1).push(2)
list.size  # => 2

Returns:

  • (Integer) —

    the number of elements



206
207
208
 
# File 'lib/dsa-ruby/linked_list.rb', line 206

def size
  @size
end

#to_a ⇒ Array

Returns an array of all values in the list (front to back).

Examples:

list.push(1).push(2).push(3)
list.to_a  # => [3, 2, 1]

Returns:

  • (Array) —

    an array of values in list order



226
227
228
229
230
231
232
233
234
 
# File 'lib/dsa-ruby/linked_list.rb', line 226

def to_a
  result = []
  node = @head
  while node
    result << node.val
    node = node.next
  end
  result
end