Class: LinkedList

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/linked_lists/linked_list.rb,
lib/linked_lists/linked_list/node.rb

Overview

An ‘Enumerable` data structure which implements a singly linked list. It’s a proper ‘Enumerable` object like `Array`, `Hash` or `Set`.

Its API has been heavily inspired by ‘Set` and `Array`.

list = LinkedList[1, 2, 3, :foo]

Prepending and shifting items is very fast and happens in *O(1)*.

list = LinkedList[:foo]
list.unshift :bar
list.prepend :baz
list >> 'foobar'
list #=> LinkedList["foobar", :baz, :bar, :foo]

Appending is possible but requires the entire list to be traversed, which gives a time complexity of *O(n)*.

list = LinkedList[:foo]
list.push :bar
list.append :baz
list << 'foobar'
list #=> LinkedList[:foo, :bar, :baz, 'foobar']

Optimal traversing is only possible in one direction, from head (first element) to tail (last element).

To get the length of a linked list, the entire list has to be traversed which happens in *O(n)*.

LinkedList[].size #=> 0
LinkedList[:foo].length #=> 1
LinkedList[:foo, 1, 2, 3].count #=> 4

Getting items by index is possible, but the list needs to be traversed from head to the index, which gives a time complexity of *O(n)*.

list = LinkedList["foobar", :baz, :bar, :foo]
list[0] #=> "foobar"
list.slice(0) #=> "foobar"
list[2] #=> :bar
list[-1] #=> :foo
list[1, 2] #=> [:baz, :bar]
list.slice(1, 2) #=> LinkedList[:baz, :bar]
list[1..3] #=> [:baz, :bar, :foo]

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(enum = nil) ⇒ LinkedList

Returns a new instance of LinkedList.

Parameters:

  • enum (Object) (defaults to: nil) —

    Enumerable object that will be converted.



72
73
74
75
76
77
 
# File 'lib/linked_lists/linked_list.rb', line 72

def initialize(enum = nil)
  @head = nil
  return if enum.nil?

  concat(enum)
end

Instance Attribute Details

#head ⇒ Node?

The first element of the linked list. Time complexity: *O(1)*

Returns:



69
70
71
 
# File 'lib/linked_lists/linked_list.rb', line 69

def head
  @head
end

Class Method Details

.[](*elements) ⇒ Object

Create a new ‘LinkedList` with these elements inserted.

Parameters:

  • elements (Array) 


60
61
62
 
# File 'lib/linked_lists/linked_list.rb', line 60

def [](*elements)
  new(elements)
end

Instance Method Details

#+(other) ⇒ self

Returns a new LinkedList which is the result of concatenating this linked list with another linked list or ‘Enumerable`.

Time complexity is *O(n + m)*, where n is the length of ‘self` and m is the length of `other`.

Parameters:

  • enum (Object)

Returns:

  • (self) 


835
836
837
 
# File 'lib/linked_lists/linked_list.rb', line 835

def +(other)
  dup.concat(other)
end

#[](index, length = nil) ⇒ Object, Array

Get the elements at the specified index. Head of the list is ‘0`.

This list in not indexed so the entire list will have to be traversed in the worst case. Time complexity: *O(n)*

Parameters:

  • index (Integer)
  • length (Integer, nil) (defaults to: nil)

Returns:

  • (Object, Array) 


219
220
221
 
# File 'lib/linked_lists/linked_list.rb', line 219

def [](index, length = nil)
  slice_with_enum(::Array, index, length)
end

#at(index) ⇒ Object?

Returns the item at the provided index. This list in not indexed so the entire list will have to be traversed in the worst case. Time complexity: *O(n)*

Parameters:

  • index (Integer)

Returns:

  • (Object, nil) 


206
207
208
 
# File 'lib/linked_lists/linked_list.rb', line 206

def at(index)
  node_at(index)&.value
end

#clear ⇒ self

Removes all elements from ‘self`. Sets the `head` to `nil`.

Time complexity: *O(1)*.

Returns:

  • (self) 


109
110
111
112
 
# File 'lib/linked_lists/linked_list.rb', line 109

def clear
  @head = nil
  self
end

#compact ⇒ self

Returns a new ‘LinkedList` containing all non-nil elements from `self`

Time complexity: *O(n)*

Returns:

  • (self) 


745
746
747
748
749
750
751
752
753
754
755
 
# File 'lib/linked_lists/linked_list.rb', line 745

def compact
  result = self.class.new

  each do |value|
    next if value.nil?

    result << value
  end

  result
end

#compact! ⇒ self?

Removes all ‘nil` elements from `self`.

Returns ‘self` if any elements removed, otherwise `nil`.

Time complexity: *O(n)*

Returns:

  • (self, nil) 


764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
 
# File 'lib/linked_lists/linked_list.rb', line 764

def compact!
  removed = nil
  prev_node = nil
  each_node do |node|
    if node.value.nil?
      removed = true
      prev_node, = delete_node_with_prev(prev_node, node.next)
      next
    end

    prev_node = node
  end
  return self if removed

  nil
end

#concat(enum) ⇒ self

Concatenates this linked list with another linked list or ‘Enumerable`.

Time complexity is *O(m)*, where m is the length of given ‘enum`.

Parameters:

  • enum (Object)

Returns:

  • (self) 


714
715
716
717
718
 
# File 'lib/linked_lists/linked_list.rb', line 714

def concat(enum)
  do_with_enum(enum) { |o| self << o }

  self
end

#concat!(list) ⇒ self

Concatenates this linked list with another linked list.

This version is faster for two linked lists but more unsafe because concatenating them happens in place by just linking the tail of the first list to the head of the second one. This means that modifying the second list after concatenating it will change the concatenated list as well!

Time complexity is *O(n)*, where n is the length of ‘self`.

Parameters:

  • list (self)

Returns:

  • (self)

Raises:

  • (::ArgumentError) 


732
733
734
735
736
737
738
 
# File 'lib/linked_lists/linked_list.rb', line 732

def concat!(list)
  raise ::ArgumentError, 'value must be a linked list' unless list.instance_of?(self.class)

  tail.next = list.head

  self
end

#delete(obj) ⇒ Object

Deletes the first item from ‘self` that is equal to `obj`. Returns the deleted item, or `nil` if no matching item is found.

Time complexity: *O(n)*

Parameters:

  • obj (Object) —

    object to be deleted

Returns:

  • (Object) 


395
396
397
398
399
400
401
402
403
404
405
406
 
# File 'lib/linked_lists/linked_list.rb', line 395

def delete(obj)
  removed = nil
  prev_node = nil
  each_node do |n|
    next (prev_node = n) unless n.value == obj

    delete_node_with_prev(prev_node, n.next)
    return n.value
  end

  removed
end

#delete_all(obj) ⇒ Object

Deletes all items from ‘self` that are equal to `obj`. Returns the last deleted item, or `nil` if no matching item is found.

Time complexity: *O(n)*

Parameters:

  • obj (Object) —

    object to be deleted

Returns:

  • (Object) 


415
416
417
418
419
420
421
422
 
# File 'lib/linked_lists/linked_list.rb', line 415

def delete_all(obj)
  removed = nil
  delete_if do |element|
    removed = element if element == obj
  end

  removed
end

#delete_at(index) ⇒ Object?

Deletes the element at the specified index returning that element, or ‘nil` if the `index` is out of range.

This list in not indexed so the entire list will have to be traversed in the worst case. Time complexity: *O(n)*

Parameters:

  • index (Integer)

Returns:

  • (Object, nil) 


455
456
457
458
459
460
461
462
463
464
 
# File 'lib/linked_lists/linked_list.rb', line 455

def delete_at(index)
  prev_node = nil
  each_node.with_index do |node, i|
    return node.value if i == index && delete_node_with_prev(prev_node, node.next)

    prev_node = node
  end

  nil
end

#delete_if {|An| ... } ⇒ self, ...

Returns self whose entries are those for which the block returns a truthy value. Or a new ‘Enumerator` if no block given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator, nil) 


384
385
386
 
# File 'lib/linked_lists/linked_list.rb', line 384

def delete_if(&block)
  reject!(&block) || self
end

#delete_node(node) ⇒ Node?

Deletes a node from ‘self` that is the same object as the given `node`. Returns the deleted node, or `nil` if no matching item is found.

Time complexity: *O(n)*

Parameters:

  • node (Node) —

    node to be deleted

Returns:

Raises:

  • (::ArgumentError) 


431
432
433
434
435
436
437
438
439
440
441
442
443
444
 
# File 'lib/linked_lists/linked_list.rb', line 431

def delete_node(node)
  raise ::ArgumentError, 'value should be a node' unless node.is_a?(Node)

  removed = nil
  prev_node = nil
  each_node do |n|
    next (prev_node = n) unless n == node

    delete_node_with_prev(prev_node, n.next)
    return n
  end

  removed
end

#each {|An| ... } ⇒ self, Enumerator Also known as: each_value

Calls the given block once for each element in linked list, passing the element as a parameter. Returns an enumerator if no block is given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator) 


244
245
246
247
248
 
# File 'lib/linked_lists/linked_list.rb', line 244

def each
  return enum_for(__method__) unless block_given?

  each_node { |node| yield node.value }
end

#each_node {|A| ... } ⇒ self, Enumerator

Calls the given block once for each node in the linked list, passing the node as a parameter. Returns an enumerator if no block is given.

Time complexity: *O(n)*

Yield Parameters:

  • A (Node) —

    node of the list.

Returns:

  • (self, Enumerator) 


260
261
262
263
264
265
266
267
268
269
270
271
 
# File 'lib/linked_lists/linked_list.rb', line 260

def each_node
  return enum_for(__method__) unless block_given?
  return unless @head

  element = @head
  loop do
    yield element
    break if (element = element.next).nil?
  end

  self
end

#empty? ⇒ Boolean

Checks if ‘head` is `nil`.

Time complexity: *O(1)*.

Returns:

  • (Boolean) 


119
120
121
 
# File 'lib/linked_lists/linked_list.rb', line 119

def empty?
  @head.nil?
end

#eql?(other) ⇒ Boolean Also known as: ==

Returns true if two linked lists are equal. The equality of each couple of elements is defined according to ‘#==`.

Time complexity is *O(min(n, m))*, where n is the length of ‘self` and m is the length of `other`.

LinkedList[1, 2] == LinkedList[1, 2]                   #=> true
LinkedList[1, 2] == LinkedList[1, 2.0]                 #=> true
LinkedList[1, 3, 5] == LinkedList[1, 5]                #=> false
LinkedList[1, 3, 5] == LinkedList[1, 3]                #=> false
LinkedList['a', 'b', 'c'] == LinkedList['a', 'c', 'b'] #=> true
LinkedList['a', 'b', 'c'] == ['a', 'c', 'b']           #=> false

Returns:

  • (Boolean) 


853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
 
# File 'lib/linked_lists/linked_list.rb', line 853

def eql?(other)
  return true if equal?(other)
  return false unless other.is_a?(self.class)

  self_node = @head
  other_node = other.head
  loop do
    break if self_node.nil? && other_node.nil?
    return false if self_node.nil? || other_node.nil?
    return false if self_node.value != other_node.value

    self_node = self_node.next
    other_node = other_node.next
  end

  true
end

#filter_map {|An| ... } ⇒ self, Enumerator

Returns a list containing truthy elements returned by the block.

With a block given, calls the block with successive elements; returns a list containing each truthy value returned by the block.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator) 


314
315
316
317
318
319
320
321
322
323
324
325
 
# File 'lib/linked_lists/linked_list.rb', line 314

def filter_map
  return enum_for(__method__) unless block_given?

  result = self.class.new
  each_node do |node|
    next unless (block_result = yield(node.value))

    result << block_result
  end

  result
end

#freeze ⇒ self

Freezes the list and its every node.

Time complexity is *O(n)*.

Returns:

  • (self) 


96
97
98
99
100
101
 
# File 'lib/linked_lists/linked_list.rb', line 96

def freeze
  super
  each_node(&:freeze)

  self
end

#index(obj = nil) ⇒ Object?

Returns the index of the first object in the linked list such that the object is ‘==` to `obj`. Time complexity: *O(n)*

If a block is given instead of an argument, returns the index of the first object for which the block returns ‘true`. Returns `nil` if no match is found.

Time complexity: *O(n)*

Parameters:

  • obj (Object) (defaults to: nil) —

    Value that will be compared with the nodes of this list.

Returns:

  • (Object, nil) 


165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
# File 'lib/linked_lists/linked_list.rb', line 165

def index(obj = nil)
  if block_given?
    each_with_index do |element, i|
      return i if yield(element)
    end

    return
  end

  each_with_index do |element, i|
    return i if obj == element
  end

  nil
end

#insert(index, *objects) ⇒ self

Inserts given objects before or after the element at ‘Integer` index offset; returns `self`.

Inserts all given objects before the element at offset index:

a = LinkedList[:foo, 'bar', 2]
a.insert(1, :bat, :bam) # => LinkedList[:foo, :bat, :bam, "bar", 2]

Extends the list if ‘index` is beyond the list (`index` >= `self.size`):

a = LinkedList[:foo, 'bar', 2]
a.insert(5, :bat, :bam)
a # => LinkedList[:foo, "bar", 2, nil, nil, :bat, :bam]

Does nothing if no objects given:

a = LinkedList[:foo, 'bar', 2]
a.insert(1)
a.insert(50)
a.insert(-50)
a # => LinkedList[:foo, "bar", 2]

Parameters:

  • index (Integer)
  • objects (Array)

Returns:

  • (self)

Raises:

  • (::ArgumentError) 


670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
 
# File 'lib/linked_lists/linked_list.rb', line 670

def insert(index, *objects)
  index = index.to_int

  raise ::ArgumentError, 'negative list index' if index.negative?
  return unshift(*objects) if index.zero?
  return self if objects.empty?

  last_node = nil
  prev_node = nil
  found_index = false
  last_index = 0
  each_node.with_index do |node, i|
    last_index = i
    last_node = node
    next (prev_node = node) unless i >= index

    found_index = true
    prev_node.insert_after(*objects)
    break
  end

  return self if found_index

  @head = last_node = Node.new if empty?

  loop do
    last_index += 1
    break if last_index >= index

    new_node = Node.new
    last_node.next = new_node
    last_node = new_node
  end
  last_node.insert_after(*objects)

  self
end

#inspect ⇒ String

Returns:

  • (String) 


908
909
910
 
# File 'lib/linked_lists/linked_list.rb', line 908

def inspect
  "#<#{self.class}: {#{join(', ', &:inspect)}}>"
end

#join(separator = nil) {|| ... } ⇒ String

Time complexity: *O(n)*

Parameters:

  • separator (String, nil) (defaults to: nil)

Yield Parameters:

  • (Object)

Returns:

  • (String) 


598
599
600
601
602
603
604
605
606
607
 
# File 'lib/linked_lists/linked_list.rb', line 598

def join(separator = nil)
  result = ::String.new
  each_node do |node|
    string_value = block_given? ? yield(node.value) : node.value
    result << string_value.to_s
    result << separator if separator && node.next
  end

  result
end

#keep_if {|An| ... } ⇒ self, ...

Returns self whose entries are those for which the block returns a truthy value. Or a new ‘Enumerator` if no block given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator, nil) 


553
554
555
 
# File 'lib/linked_lists/linked_list.rb', line 553

def keep_if(&block)
  select!(&block) || self
end

#last(*args) ⇒ Object, Array

Returns the last element, or the last ‘length` elements, of the linked list. If the list is empty, the first form returns `nil`, and the second form returns an empty list.

Keep in mind that it’s only possible to traverse this list in one direction from head to tail. So the entire list has to be traversed in order to retrieve the last elements.

Time complexity is *O(2n)*.

Parameters:

  • length (Integer)

Returns:

  • (Object, Array) 


151
152
153
 
# File 'lib/linked_lists/linked_list.rb', line 151

def last(*args)
  to_a.last(*args)
end

#map {|An| ... } ⇒ self, Enumerator Also known as: collect

Returns a new ‘LinkedList` which consists of the values returned by the block. Returns an enumerator if no block is given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator) 


293
294
295
296
297
298
299
300
301
302
 
# File 'lib/linked_lists/linked_list.rb', line 293

def map
  return enum_for(__method__) unless block_given?

  result = self.class.new
  each_node do |node|
    result << yield(node.value)
  end

  result
end

#map! {|An| ... } ⇒ self, Enumerator Also known as: collect!

Replaces the elements with ones returned by the block. Returns an enumerator if no block is given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator) 


334
335
336
337
338
339
340
341
342
 
# File 'lib/linked_lists/linked_list.rb', line 334

def map!
  return enum_for(__method__) unless block_given?

  each_node do |node|
    node.value = yield(node.value)
  end

  self
end

#node_at(index) ⇒ Node?

Returns the node at the provided index. This list in not indexed so the entire list will have to be traversed in the worst case. Time complexity: *O(n)*

Parameters:

  • index (Integer)

Returns:



188
189
190
191
192
193
194
195
196
197
 
# File 'lib/linked_lists/linked_list.rb', line 188

def node_at(index)
  index = index.to_int
  return each_node.to_a.at(index) if index.negative?

  each_node.with_index do |node, i|
    return node if i == index
  end

  nil
end

#pop(length = nil) ⇒ Object, Array

Removes and returns trailing elements.

When no argument is given and self is not empty, removes and returns the last element

Keep in mind that the entire list has to be traversed in the worst case to pop an item.

Time complexity: *O(n)*.

Parameters:

  • length (Integer, nil) (defaults to: nil)

Returns:

  • (Object, Array)

Raises:

  • (::TypeError) 


511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
 
# File 'lib/linked_lists/linked_list.rb', line 511

def pop(length = nil)
  raise ::TypeError, "no implicit conversion of #{length.class} into Integer" unless length.nil? || length.respond_to?(:to_int)
  return [] if length&.zero?
  raise ::ArgumentError, 'negative linked list size' if length&.negative?

  index = length ? -length : -1
  ary = each_node.to_a
  node = ary[index] || @head
  prev_node = ary[index - 1]

  if prev_node.nil?
    @head = nil
  else
    prev_node.next = nil
  end

  return node&.value unless length

  node&.to_list.to_a
end

#push(*objects) ⇒ self Also known as: <<, add, append

Appends the given ‘objects` to `self`.

Time complexity: *O(n)*.

Parameters:

  • objects (Object)

Returns:

  • (self) 


615
616
617
618
619
620
621
622
 
# File 'lib/linked_lists/linked_list.rb', line 615

def push(*objects)
  return self if objects.empty?

  @head  = Node.new objects.shift if empty?
  tail.insert_after(*objects)

  self
end

#reject {|An| ... } ⇒ self, Enumerator

Returns a new ‘LinkedList` object whose entries are those for which the block returns a falsey value. Or a new `Enumerator` if no block given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator) 


352
353
354
355
356
 
# File 'lib/linked_lists/linked_list.rb', line 352

def reject
  return enum_for(__method__) unless block_given?

  select { |o| !yield(o) }
end

#reject! {|An| ... } ⇒ self, ...

Returns self whose entries are those for which the block returns a falsey value. A new ‘Enumerator` if no block given. Or `nil` if no entries were removed.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator, nil) 


540
541
542
543
544
 
# File 'lib/linked_lists/linked_list.rb', line 540

def reject!
  return enum_for(__method__) unless block_given?

  select! { |o| !yield(o) }
end

#reverse ⇒ self

Returns a new ‘LinkedList` with the elements of `self` in reverse order. Time complexity: *O(2n)*

Returns:

  • (self) 


277
278
279
280
281
282
283
284
 
# File 'lib/linked_lists/linked_list.rb', line 277

def reverse
  result = self.class.new
  reverse_each do |obj|
    result << obj
  end

  result
end

#select {|An| ... } ⇒ self, Enumerator Also known as: filter

Returns a new ‘LinkedList` object whose entries are those for which the block returns a truthy value. Or a new Enumerator if no block given.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator) 


365
366
367
368
369
370
371
372
373
374
 
# File 'lib/linked_lists/linked_list.rb', line 365

def select
  return enum_for(__method__) unless block_given?

  result = self.class.new
  each do |value|
    result << value if yield(value)
  end

  result
end

#select! {|An| ... } ⇒ self, ... Also known as: filter!

Returns self whose entries are those for which the block returns a truthy value. A new ‘Enumerator` if no block given. Or `nil` if no entries were removed.

Time complexity: *O(n)*

Yield Parameters:

  • An (Object) —

    element of the list.

Returns:

  • (self, Enumerator, nil) 


565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
 
# File 'lib/linked_lists/linked_list.rb', line 565

def select!
  return enum_for(__method__) unless block_given?
  return if empty?

  removed = false
  prev_node = nil
  node = @head
  next_node = node.next
  loop do
    keep = yield(node.value)
    if keep
      prev_node = node
      node = prev_node.next
      next_node = node&.next
    else
      removed = true
      prev_node, node, next_node = delete_node_with_prev(prev_node, next_node)
    end

    break if node.nil?
  end

  return unless removed

  self
end

#shift(length = nil) ⇒ Object, Array

Removes and returns leading elements. When no argument is given, removes and returns the first element. When positive Integer argument ‘length` is given, removes the first `length` elements and returns those elements in a new `Array`.

Time complexity is *O(1)* when no ‘length` is given. Otherwise it’s *O(min(m, n))*, where m is the given ‘length` of elements to be shifted and n is the length of `self`.

Parameters:

  • length (Integer, nil) (defaults to: nil)

Returns:

  • (Object, Array)

Raises:

  • (::TypeError) 


477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
 
# File 'lib/linked_lists/linked_list.rb', line 477

def shift(length = nil)
  raise ::TypeError, "no implicit conversion of #{length.class} into Integer" unless length.nil? || length.respond_to?(:to_int)
  raise ::ArgumentError, 'negative linked list size' if length&.negative?
  return if empty?

  unless length
    prev_head = @head
    @head = @head.next
    return prev_head.value
  end

  length = length.to_int
  removed = []
  each_node.with_index do |node, i|
    break if i == length

    removed << @head.value
    @head = node.next
  end

  removed
end

#size ⇒ Integer Also known as: length

The number of elements in the list. Keep in mind that the entire list needs to be traversed in order to find out it’s length.

Time complexity is *O(n)*.

Returns:

  • (Integer) 


130
131
132
133
134
135
136
137
 
# File 'lib/linked_lists/linked_list.rb', line 130

def size
  return 0 if empty?

  length = 0
  each_with_index { |_, i| length = i }

  length + 1
end

#slice(index, length = nil) ⇒ Object, self

Get the elements at the specified index. Head of the list is ‘0`.

This list in not indexed so the entire list will have to be traversed in the worst case. Time complexity: *O(n)*

Parameters:

  • index (Integer)
  • length (Integer, nil) (defaults to: nil)

Returns:

  • (Object, self) 


232
233
234
 
# File 'lib/linked_lists/linked_list.rb', line 232

def slice(index, length = nil)
  slice_with_enum(self.class, index, length)
end

#sublist?(other) ⇒ Boolean

Checks whether ‘self` is a sublist of the provided list `other`. Time complexity is *O(m)*, where m is the length of `other`.

Parameters:

  • other (self)

Returns:

  • (Boolean)

Raises:

  • (::ArgumentError) 


798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
 
# File 'lib/linked_lists/linked_list.rb', line 798

def sublist?(other)
  return true if equal?(other)
  raise ::ArgumentError, 'value must be a linked list' unless other.is_a?(self.class)
  return true if (empty? && !other.empty?) || (empty? && other.empty?)
  return false if !empty? && other.empty?

  self_node = @head
  other_node = other.head

  at_least_one_equal = false
  loop do
    return true if self_node.equal?(other_node)
    return true if self_node.nil?
    return false if other_node.nil?

    if self_node.value == other_node.value
      at_least_one_equal = true
      self_node = self_node.next
      other_node = other_node.next
      next
    end

    return false if at_least_one_equal

    other_node = other_node.next
  end

  true
end

#superlist?(other) ⇒ Boolean

Checks whether ‘self` is a superlist of the provided list `other` (if the `other` list is a sublist of `self`). Time complexity is *O(n)*, where n is the length of `self`.

Parameters:

  • other (self)

Returns:

  • (Boolean)

Raises:

  • (::ArgumentError) 


787
788
789
790
791
 
# File 'lib/linked_lists/linked_list.rb', line 787

def superlist?(other)
  raise ::ArgumentError, 'value must be a linked list' unless other.is_a?(self.class)

  other.sublist?(self)
end

#tail ⇒ Node?

The last element of the linked list.

Keep in mind that in order to retrieve it the entire list needs to be traversed.

Time complexity is *O(n)*.

Returns:



87
88
89
 
# File 'lib/linked_lists/linked_list.rb', line 87

def tail
  each_node { |node| return node if node.next.nil? }
end

#to_set ⇒ Set

Returns:

  • (Set) 


898
899
900
901
902
903
904
905
 
# File 'lib/linked_lists/linked_list.rb', line 898

def to_set
  set = ::Set.new
  each do |value|
    set << value
  end

  set
end

#unshift(*objects) ⇒ self Also known as: >>, prepend

Prepends the given ‘objects` to `self`.

Time complexity is *O(1)* if one item is given. Otherwise it’s *O(m)*, where m is the length of given ‘objects`.

Parameters:

  • objects (Array)

Returns:

  • (self) 


634
635
636
637
638
639
640
641
642
 
# File 'lib/linked_lists/linked_list.rb', line 634

def unshift(*objects)
  objects.reverse_each do |obj|
    new_node = Node.new obj
    new_node.next = @head
    @head = new_node
  end

  self
end