Class: DLinked::List

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

Overview

A fast, lightweight, and standards-compliant doubly linked list.

This class provides a memory-efficient and performant alternative to Ruby’s standard ‘Array` for scenarios requiring frequent O(1) insertions or deletions from the ends of the list (e.g., queues, stacks).

It includes the ‘Enumerable` module, allowing it to work seamlessly with standard Ruby collection methods like `map`, `select`, and `each`.

Examples:

Basic Usage

list = DLinked::List.new
list.append(20).prepend(10) # => [10, 20]
list.shift # => 10
list.to_a # => [20]

Direct Known Subclasses

CacheList

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ List

Initializes a new, empty list.

Examples:

list = DLinked::List.new
list.size # => 0


34
35
36
37
38
 
# File 'lib/d_linked/list.rb', line 34

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

Instance Attribute Details

#size ⇒ Object (readonly) Also known as: length

Returns the value of attribute size.



26
27
28
 
# File 'lib/d_linked/list.rb', line 26

def size
  @size
end

Instance Method Details

#+(other) ⇒ DLinked::List

Returns a new list by concatenating this list with another (non-destructive).

The complexity is **O(n + k)**, where ‘n` is the size of this list and `k` is the size of the `other` list.

Parameters:

  • other (#each) —

    The enumerable object to concatenate.

Returns:

  • (DLinked::List) —

    A new list containing all elements from both.



432
433
434
435
436
437
 
# File 'lib/d_linked/list.rb', line 432

def +(other)
  new_list = self.class.new
  each { |value| new_list.append(value) }
  other.each { |value| new_list.append(value) }
  new_list
end

#[](index) ⇒ Object? #[](start, length) ⇒ DLinked::List? #[](range) ⇒ DLinked::List

Overloads:

  • #[](index) ⇒ Object?

    Retrieves the element at a specific index. Traversal is optimized to start from the head or tail, whichever is closer.

    Parameters:

    • index (Integer) —

      The index (positive or negative).

    Returns:

    • (Object, nil) —

      The value at the index, or ‘nil` if out of bounds.

  • #[](start, length) ⇒ DLinked::List?

    Retrieves a slice of ‘length` elements starting at `start`.

    Parameters:

    • start (Integer) —

      The starting index.

    • length (Integer) —

      The number of elements to retrieve.

    Returns:

    • (DLinked::List, nil) —

      A new list containing the slice, or ‘nil` if `start` is out of bounds.

  • #[](range) ⇒ DLinked::List

    Retrieves a slice using a ‘Range`.

    Parameters:

    • range (Range) —

      The range of indices to retrieve.

    Returns:



251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/d_linked/list.rb', line 251

def [](*args)
  # Case 1: Single Index Access (list[i])
  if args.size == 1 && args[0].is_a?(Integer)
    index = args[0]
    index += @size if index.negative?
    return nil if index.negative? || index >= @size

    node = find_node_at_index(index)
    return node.value # Returns raw value
  end

  # Case 2 & 3: Slicing (list[start, length] or list[range])
  slice(*args) # Delegate to the robust slice method
end

#[]=(index, value) ⇒ Object? #[]=(start, length, value) ⇒ Object+ #[]=(range, value) ⇒ Object+

Overloads:

  • #[]=(index, value) ⇒ Object?

    Sets the value of an element at a single index.

    Parameters:

    • index (Integer) —

      The index to modify.

    • value (Object) —

      The new value.

    Returns:

    • (Object, nil) —

      The assigned value, or ‘nil` if the index is out of bounds.

  • #[]=(start, length, value) ⇒ Object+

    Replaces a slice of ‘length` elements starting at `start` with a new value (or values).

    Parameters:

    • start (Integer) —

      The starting index.

    • length (Integer) —

      The number of elements to replace.

    • value (Object, Array<Object>) —

      The new value(s).

    Returns:

    • (Object, Array<Object>) —

      The assigned value(s).

  • #[]=(range, value) ⇒ Object+

    Replaces a slice defined by a ‘Range` with a new value (or values).

    Parameters:

    • range (Range) —

      The range of indices to replace.

    • value (Object, Array<Object>) —

      The new value(s).

    Returns:

    • (Object, Array<Object>) —

      The assigned value(s).



284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
 
# File 'lib/d_linked/list.rb', line 284

def []=(*args)
  replacement = args.pop

  # 1. Handle Single Index Assignment (e.g., list[2] = 'a')
  if args.size == 1 && args[0].is_a?(Integer)
    index = args[0]
    index += @size if index.negative?
    return nil unless index >= 0 && index < @size

    node = find_node_at_index(index)
    node.value = replacement
    return replacement
  end

  # 2. Handle Slice Replacement
  start_index, length = *args

  if args.size == 1 && start_index.is_a?(Range)
    range = start_index
    start_index = range.begin
    length = range.end - range.begin + (range.exclude_end? ? 0 : 1)
  elsif args.size != 2 || !start_index.is_a?(Integer) || !length.is_a?(Integer)
    return nil
  end

  start_index += @size if start_index.negative?

  if start_index > @size
    replacement = Array(replacement)
    replacement.each { |val| append(val) }
    return replacement
  end

  replacement = Array(replacement)

  predecessor = start_index.positive? ? find_node_at_index(start_index - 1) : nil
  current = predecessor ? predecessor.next : @head

  deleted_count = 0
  length.times do
    break unless current
    current = current.next
    deleted_count += 1
  end
  successor = current

  if predecessor
    predecessor.next = successor
  else
    @head = successor
  end

  if successor
    successor.prev = predecessor
  else
    @tail = predecessor
  end
  @size -= deleted_count

  insertion_point = predecessor
  replacement.each do |value|
    new_node = Node.new(value, insertion_point, successor)
    if insertion_point
      insertion_point.next = new_node
    else
      @head = new_node
    end
    insertion_point = new_node
    @size += 1
  end

  if successor
    successor.prev = insertion_point
  else
    @tail = insertion_point
  end

  replacement
end

#append(value) ⇒ self Also known as: push, <<

Adds a new value to the end of the list (the tail).

This is an **O(1)** operation.

Examples:

list = DLinked::List.new
list.append(10)
list.append(20)
list.to_a # => [10, 20]

Parameters:

  • value (Object) —

    The value to add to the list.

Returns:

  • (self) —

    The list instance, for method chaining.



72
73
74
75
 
# File 'lib/d_linked/list.rb', line 72

def append(value)
  node = Node.new(value, @tail, nil)
  list_append_logic(node)
end

#clear ⇒ self

Removes all elements from the list.

This is an **O(1)** operation.

Returns:

  • (self) —

    The cleared list instance.



153
154
155
156
157
158
 
# File 'lib/d_linked/list.rb', line 153

def clear
  @head = nil
  @tail = nil
  @size = 0
  self
end

#concat(other) ⇒ self

Appends the elements of another list to this one (destructive).

This is an **O(k)** operation, where ‘k` is the size of the `other` list.

Parameters:

  • other (#each) —

    An enumerable object to append.

Returns:

  • (self) —

    The modified list instance.

Raises:

  • (TypeError) —

    if ‘other` is not enumerable.



417
418
419
420
421
422
423
 
# File 'lib/d_linked/list.rb', line 417

def concat(other)
  raise TypeError, "can't convert #{other.class} into DLinked::List" unless other.respond_to?(:each)
  return self if other.empty?

  other.each { |value| append(value) }
  self
end

#delete(value) ⇒ Object?

Deletes the first node that matches the given value.

This is an **O(n)** operation.

Parameters:

  • value (Object) —

    The value to search for and delete.

Returns:

  • (Object, nil) —

    The value of the deleted element, or ‘nil` if not found.



398
399
400
401
402
403
404
405
406
407
408
 
# File 'lib/d_linked/list.rb', line 398

def delete(value)
  current = @head
  while current
    if current.value == value
      delete_node(current)
      return value
    end
    current = current.next
  end
  nil
end

#each {|Object| ... } ⇒ self, Enumerator

Iterates through the list, yielding the value of each element in order from head to tail.

This is an **O(n)** operation.

Yields:

  • (Object) —

    The value of the current element.

Returns:

  • (self, Enumerator) —

    Returns ‘self` if a block is given, otherwise returns an `Enumerator`.



168
169
170
171
172
173
174
175
176
177
 
# File 'lib/d_linked/list.rb', line 168

def each
  return enum_for(:each) unless block_given?

  current = @head
  while current
    yield current.value
    current = current.next
  end
  self
end

#empty? ⇒ Boolean

Checks if the list contains any elements.

This is an **O(1)** operation.

Returns:

  • (Boolean) —

    ‘true` if the list is empty, `false` otherwise.



144
145
146
 
# File 'lib/d_linked/list.rb', line 144

def empty?
  @size.zero?
end

#first ⇒ Object?

Returns the value of the element at the head of the list without removing it.

This is an **O(1)** operation.

Returns:

  • (Object, nil) —

    The value of the first element, or ‘nil` if the list is empty.



126
127
128
 
# File 'lib/d_linked/list.rb', line 126

def first
  @head&.value
end

#index(value) ⇒ Integer?

Finds the index of the first occurrence of a given value.

This is an **O(n)** operation.

Parameters:

  • value (Object) —

    The value to search for.

Returns:

  • (Integer, nil) —

    The index of the first matching element, or ‘nil` if not found.



202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/d_linked/list.rb', line 202

def index(value)
  current = @head
  idx = 0
  while current
    return idx if current.value == value

    current = current.next
    idx += 1
  end
  nil
end

#insert(index, value) ⇒ self

Inserts a new element at the specified index.

This is an **O(n)** operation, unless inserting at the head (‘index` = 0) or tail (`index` >= `size`), in which case it is **O(1)**.

Parameters:

  • index (Integer) —

    The index before which to insert the new element.

  • value (Object) —

    The value to insert.

Returns:

  • (self) —

    The list instance for method chaining.

See Also:



374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
 
# File 'lib/d_linked/list.rb', line 374

def insert(index, value)
  if index.negative?
    index += @size
    index = 0 if index.negative?
  end

  return prepend(value) if index <= 0
  return append(value) if index >= @size

  current = find_node_at_index(index)
  new_node = Node.new(value, current.prev, current)
  current.prev.next = new_node
  current.prev = new_node

  @size += 1
  self
end

#last ⇒ Object?

Returns the value of the element at the tail of the list without removing it.

This is an **O(1)** operation.

Returns:

  • (Object, nil) —

    The value of the last element, or ‘nil` if the list is empty.



135
136
137
 
# File 'lib/d_linked/list.rb', line 135

def last
  @tail&.value
end

#pop ⇒ Object?

Removes the last element from the list (the tail) and returns its value.

This is an **O(1)** operation.

Examples:

list = DLinked::List.new << 1 << 2
list.pop # => 2
list.pop # => 1
list.pop # => nil

Returns:

  • (Object, nil) —

    The value of the removed element, or ‘nil` if the list is empty.



111
112
113
114
115
116
117
118
119
 
# File 'lib/d_linked/list.rb', line 111

def pop
  return nil if empty?

  value = @tail.value
  @tail = @tail.prev
  @tail ? @tail.next = nil : @head = nil
  @size -= 1
  value
end

#prepend(value) ⇒ self Also known as: unshift

Adds a new value to the beginning of the list (the head).

This is an **O(1)** operation.

Examples:

list = DLinked::List.new
list.prepend(10)
list.prepend(5)
list.to_a # => [5, 10]

Parameters:

  • value (Object) —

    The value to store in the new node.

Returns:

  • (self) —

    The list instance, allowing for method chaining.



54
55
56
57
 
# File 'lib/d_linked/list.rb', line 54

def prepend(value)
  node = Node.new(value, nil, @head)
  list_prepend_logic(node)
end

#reverse_each {|Object| ... } ⇒ self, Enumerator

Iterates through the list in reverse order, from tail to head.

This is an **O(n)** operation.

Yields:

  • (Object) —

    The value of the current element.

Returns:

  • (self, Enumerator) —

    Returns ‘self` if a block is given, otherwise returns an `Enumerator`.



185
186
187
188
189
190
191
192
193
194
 
# File 'lib/d_linked/list.rb', line 185

def reverse_each
  return enum_for(:reverse_each) unless block_given?

  current = @tail
  while current
    yield current.value
    current = current.prev
  end
  self
end

#shift ⇒ Object?

Removes the first element from the list (the head) and returns its value.

This is an **O(1)** operation.

Examples:

list = DLinked::List.new << 1 << 2
list.shift # => 1
list.shift # => 2
list.shift # => nil

Returns:

  • (Object, nil) —

    The value of the removed element, or ‘nil` if the list is empty.



90
91
92
93
94
95
96
97
98
 
# File 'lib/d_linked/list.rb', line 90

def shift
  return nil if empty?

  value = @head.value
  @head = @head.next
  @head ? @head.prev = nil : @tail = nil
  @size -= 1
  value
end

#slice(index) ⇒ DLinked::List? #slice(start, length) ⇒ DLinked::List? #slice(range) ⇒ DLinked::List

Overloads:

  • #slice(index) ⇒ DLinked::List?

    Extracts a single element at ‘index` and returns it in a new list.

    Parameters:

    • index (Integer) —

      The index to retrieve.

    Returns:

    • (DLinked::List, nil) —

      A new list with one element, or ‘nil` if out of bounds.

  • #slice(start, length) ⇒ DLinked::List?

    Returns A new list, or ‘nil` if `start` is out of bounds.

    Parameters:

    • start (Integer) —

      The starting index.

    • length (Integer) —

      The number of elements in the slice.

    Returns:

    • (DLinked::List, nil) —

      A new list, or ‘nil` if `start` is out of bounds.

  • #slice(range) ⇒ DLinked::List

    Returns A new list.

    Parameters:

    • range (Range) —

      A range of indices.

    Returns:



452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
 
# File 'lib/d_linked/list.rb', line 452

def slice(start, length = nil)
  if start.is_a?(Range) && length.nil?
    range = start
    start = range.begin
    length = range.end - range.begin + (range.exclude_end? ? 0 : 1)
  end

  start += @size if start.negative?
  return nil if start.negative? || start >= @size

  if length.nil?
    node = find_node_at_index(start)
    new_list = self.class.new
    new_list.append(node.value)
    return new_list
  end

  return List.new if length.negative?

  new_list = List.new
  current = find_node_at_index(start)

  count = 0
  while current && count < length
    new_list.append(current.value)
    current = current.next
    count += 1
  end

  new_list
end

#slice!(start, length) ⇒ DLinked::List? #slice!(range) ⇒ DLinked::List?

Extracts and removes a slice of elements, returning the removed slice as a new list.

This is an **O(n)** operation.

Overloads:

  • #slice!(start, length) ⇒ DLinked::List?

    Returns A new list with the removed elements, or ‘nil` if the slice is empty.

    Parameters:

    • start (Integer) —

      The starting index.

    • length (Integer) —

      The number of elements to remove.

    Returns:

    • (DLinked::List, nil) —

      A new list with the removed elements, or ‘nil` if the slice is empty.

  • #slice!(range) ⇒ DLinked::List?

    Returns A new list with the removed elements, or ‘nil` if the slice is empty.

    Parameters:

    • range (Range) —

      The range of indices to remove.

    Returns:

    • (DLinked::List, nil) —

      A new list with the removed elements, or ‘nil` if the slice is empty.



496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
 
# File 'lib/d_linked/list.rb', line 496

def slice!(*args)
  start_index, length = *args

  if args.size == 1 && start_index.is_a?(Range)
    range = start_index
    start_index = range.begin
    length = range.end - range.begin + (range.exclude_end? ? 0 : 1)
  elsif args.size == 1
    length = 1
  elsif args.size != 2 || length < 1
    return nil
  end

  start_index += @size if start_index.negative?

  return nil if start_index >= @size || length <= 0

  predecessor = start_index.positive? ? find_node_at_index(start_index - 1) : nil
  current = predecessor ? predecessor.next : @head

  length.times do
    break unless current
    current = current.next
  end
  successor = current

  result = self.class.new
  slice_node = predecessor ? predecessor.next : @head

  if predecessor
    predecessor.next = successor
  else
    @head = successor
  end

  if successor
    successor.prev = predecessor
  else
    @tail = predecessor
  end

  removed_count = 0
  while slice_node != successor
    next_node = slice_node.next
    result.append(slice_node.value)
    slice_node.prev = nil
    slice_node.next = nil
    slice_node = next_node
    removed_count += 1
  end

  @size -= removed_count
  result.empty? ? nil : result
end

#to_a ⇒ Array

Converts the linked list into a standard Ruby Array.

This is an **O(n)** operation.

Returns:

  • (Array) —

    A new ‘Array` containing all elements in order.



219
220
221
 
# File 'lib/d_linked/list.rb', line 219

def to_a
  map { |v| v }
end

#to_s ⇒ String Also known as: inspect

Returns a string representation of the list.

This is an **O(n)** operation.

Returns:

  • (String) —

    The string representation (e.g., ‘“[10, 20, 30]”`).



228
229
230
 
# File 'lib/d_linked/list.rb', line 228

def to_s
  "[#{to_a.join(', ')}]"
end