Class: DSA::LinkedList::Doubly

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

Overview

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

Each node points to both the next and previous nodes. Supports push_front, push_back, pop_front, pop_back, delete, and find. Includes Enumerable for functional-style operations.

Examples:

dll = DSA::LinkedList::Doubly.new
dll.push_back(1).push_back(2).push_back(3)
dll.pop_front   # => 1
dll.pop_back    # => 3
dll.to_a        # => [2]

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DSA::LinkedList::Doubly

Initialize a new empty doubly linked list.



272
273
274
275
276
 
# File 'lib/dsa-ruby/linked_list.rb', line 272

def initialize
  @head = nil
  @tail = nil
  @size = 0
end

Instance Method Details

#back ⇒ Object

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

Examples:

dll.push_back(1).push_back(2)
dll.back  # => 2

Returns:

  • (Object) —

    the value at the back

Raises:

  • (IndexError) —

    if the list is empty



365
366
367
368
 
# File 'lib/dsa-ruby/linked_list.rb', line 365

def back
  raise IndexError, "list is empty" unless @tail
  @tail.val
end

#delete(val) ⇒ Boolean

Deletes the first occurrence of a value from the list.

Examples:

dll.push_back(1).push_back(2).push_back(3)
dll.delete(2)  # => true
dll.delete(5)  # => false

Parameters:

  • val (Object) —

    the value to delete

Returns:

  • (Boolean) —

    true if the value was found and deleted



378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/dsa-ruby/linked_list.rb', line 378

def delete(val)
  node = @head
  while node
    if node.val == val
      node.prev.next = node.next if node.prev
      node.next.prev = node.prev if node.next
      @head = node.next if node == @head
      @tail = node.prev if node == @tail
      @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:

dll.push_back(1).push_back(2).push_back(3)
dll.each { |x| puts x }  # prints 1, 2, 3

Yields:

  • (val) —

    yields each value to the block

Returns:

  • (Enumerator) —

    if no block given



457
458
459
460
461
462
463
464
 
# File 'lib/dsa-ruby/linked_list.rb', line 457

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:

dll = DSA::LinkedList::Doubly.new
dll.empty?  # => true

Returns:

  • (Boolean) —

    true if the list contains no elements



427
428
429
 
# File 'lib/dsa-ruby/linked_list.rb', line 427

def empty?
  @size == 0
end

#find(val) ⇒ DoublyNode?

Finds the first node with the given value.

Examples:

dll.push_back(1).push_back(2)
dll.find(2)  # => #<DoublyNode @val=2>
dll.find(5)  # => nil

Parameters:

  • val (Object) —

    the value to find

Returns:

  • (DoublyNode, nil) —

    the node if found, nil otherwise



402
403
404
405
406
407
408
409
 
# File 'lib/dsa-ruby/linked_list.rb', line 402

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

#front ⇒ Object

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

Examples:

dll.push_back(1).push_back(2)
dll.front  # => 1

Returns:

  • (Object) —

    the value at the front

Raises:

  • (IndexError) —

    if the list is empty



353
354
355
356
 
# File 'lib/dsa-ruby/linked_list.rb', line 353

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

#pop_back ⇒ Object

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

Examples:

dll.push_back(1).push_back(2)
dll.pop_back  # => 2

Returns:

  • (Object) —

    the value at the back

Raises:

  • (IndexError) —

    if the list is empty



335
336
337
338
339
340
341
342
343
344
 
# File 'lib/dsa-ruby/linked_list.rb', line 335

def pop_back
  raise IndexError, "list is empty" unless @tail

  val = @tail.val
  @tail = @tail.prev
  @tail.next = nil if @tail
  @head = nil unless @tail
  @size -= 1
  val
end

#pop_front ⇒ Object

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

Examples:

dll.push_back(1).push_back(2)
dll.pop_front  # => 1

Returns:

  • (Object) —

    the value at the front

Raises:

  • (IndexError) —

    if the list is empty



317
318
319
320
321
322
323
324
325
326
 
# File 'lib/dsa-ruby/linked_list.rb', line 317

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

  val = @head.val
  @head = @head.next
  @head.prev = nil if @head
  @tail = nil unless @head
  @size -= 1
  val
end

#push_back(val) ⇒ DSA::LinkedList::Doubly

Inserts a value at the back of the list.

Examples:

dll.push_back(1).push_back(2)
dll.to_a  # => [1, 2]

Parameters:

  • val (Object) —

    the value to insert

Returns:



301
302
303
304
305
306
307
308
 
# File 'lib/dsa-ruby/linked_list.rb', line 301

def push_back(val)
  node = DoublyNode.new(val, nil, @tail)
  @tail.next = node if @tail
  @tail = node
  @head ||= node
  @size += 1
  self
end

#push_front(val) ⇒ DSA::LinkedList::Doubly

Inserts a value at the front of the list.

Examples:

dll.push_front(2).push_front(1)
dll.to_a  # => [1, 2]

Parameters:

  • val (Object) —

    the value to insert

Returns:



285
286
287
288
289
290
291
292
 
# File 'lib/dsa-ruby/linked_list.rb', line 285

def push_front(val)
  node = DoublyNode.new(val, @head, nil)
  @head.prev = node if @head
  @head = node
  @tail ||= node
  @size += 1
  self
end

#size ⇒ Integer

Returns the number of elements in the list.

Examples:

dll.push_back(1).push_back(2)
dll.size  # => 2

Returns:

  • (Integer) —

    the number of elements



417
418
419
 
# File 'lib/dsa-ruby/linked_list.rb', line 417

def size
  @size
end

#to_a ⇒ Array

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

Examples:

dll.push_back(1).push_back(2).push_back(3)
dll.to_a  # => [1, 2, 3]

Returns:

  • (Array) —

    an array of values in list order



437
438
439
440
441
442
443
444
445
 
# File 'lib/dsa-ruby/linked_list.rb', line 437

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