Class: LinkedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/algorithm_selector.rb

Overview

Singly-Linked List data structure Worst-Case Space Complexity: O(n)

Instance Method Summary collapse

Constructor Details

#initialize(data_set = []) ⇒ LinkedList

Returns a new instance of LinkedList.



424
425
426
427
428
429
430
 
# File 'lib/algorithm_selector.rb', line 424

def initialize(data_set=[])
  @head = LinkNode.new
  @tail = LinkNode.new
  @head.next = @tail
  @tail.prev = @head
  data_set.each { |i| insert(i) }
end

Instance Method Details

#[](i) ⇒ Object 



437
438
439
440
 
# File 'lib/algorithm_selector.rb', line 437

def [](i)
  each_with_index { |link, j| return link if i == j }
  nil
end

#each ⇒ Object 



487
488
489
490
491
492
493
 
# File 'lib/algorithm_selector.rb', line 487

def each
  current_link = @head.next
  until current_link == @tail
    yield current_link
    current_link = current_link.next
  end
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


450
451
452
 
# File 'lib/algorithm_selector.rb', line 450

def empty?
  @head.next == @tail
end

#first ⇒ Object 



442
443
444
 
# File 'lib/algorithm_selector.rb', line 442

def first
  empty? ? nil : @head.next
end

#get(val) ⇒ Object 



454
455
456
457
 
# File 'lib/algorithm_selector.rb', line 454

def get(val)
  each { |link| return link.val if link.val == val }
  nil
end

#include?(val) ⇒ Boolean

Returns:

  • (Boolean) 


459
460
461
 
# File 'lib/algorithm_selector.rb', line 459

def include?(val)
  any? { |link| link.val == val }
end

#insert(val) ⇒ Object

Insertion, Worst-Case Time Complexity: O(1)



464
465
466
467
468
469
470
471
472
 
# File 'lib/algorithm_selector.rb', line 464

def insert(val)
  each { |link| return link.val = val if link.val == val }
  new_link = LinkNode.new(val)
  @tail.prev.next = new_link
  new_link.prev = @tail.prev
  new_link.next = @tail
  @tail.prev = new_link
  new_link
end

#last ⇒ Object 



446
447
448
 
# File 'lib/algorithm_selector.rb', line 446

def last
  empty? ? nil : @tail.prev
end

#remove(val) ⇒ Object

Deletion, Worst-Case Time Complexity: O(1)



475
476
477
478
479
480
481
482
483
484
485
 
# File 'lib/algorithm_selector.rb', line 475

def remove(val)
  each do |link|
    if link.val == val
      link.prev.next = link.next
      link.next.prev = link.prev
      link.next, link.prev = nil, nil
      return link.val
    end
  end
  nil
end

#search(target) ⇒ Object

Search, Worst-Case Time Complexity: O(n)



433
434
435
 
# File 'lib/algorithm_selector.rb', line 433

def search(target)
  each { |current_link| return current_link.val if current_link.val == target }
end