Class: LinkedList

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

Overview

Linked list implementation. Linked lists have O(1) insertions and pops. Traversal is O(n).

Implementation Notes

This implementation isn’t thread safe. In fact, traversal is thread safe, but insertions and removals aren’t.

This implementation has problems with #dup, but beyond that, it looks fine. It needs to be battle tested though. As a performance optimization, #size is cached and maintained locally, instead of being recalculated everytime.

Defined Under Namespace

Classes: Node

Constant Summary collapse

VERSION = 
'1.0.0'

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ LinkedList

Returns a new instance of LinkedList.



21
22
23
 
# File 'lib/linked_list.rb', line 21

def initialize
  clear
end

Instance Attribute Details

#cdr ⇒ Object (readonly)

Returns the value of attribute cdr.



18
19
20
 
# File 'lib/linked_list.rb', line 18

def cdr
  @cdr
end

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

Returns the value of attribute size.



18
19
20
 
# File 'lib/linked_list.rb', line 18

def size
  @size
end

Instance Method Details

#<<(value) ⇒ Object Also known as: push, unshift

Pushes a new value at the head of this list



129
130
131
132
133
134
 
# File 'lib/linked_list.rb', line 129

def <<(value)
  @cdr = new_node(value, cdr)
  @lcdr = @cdr if @lcdr.nil?
  @size += 1
  self
end

#==(other) ⇒ Object

Two lists are equal if they have the same values in the same positions.



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

def ==(other)
  cdr == other.cdr
end

#[](*args) ⇒ Object 



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
# File 'lib/linked_list.rb', line 78

def [](*args)
  case args.length
  when 1
    case args.first
    when Range
      indexes = args.first
      start, stop = normalize_index(indexes.first), normalize_index(indexes.exclude_end? ? indexes.last - 1 : indexes.last)
      indexes = (start .. stop)
      result = []
      each_with_index do |value, idx|
        next unless indexes.include?(idx)
        result << value
      end
      result
    else
      at(args.first)
    end
  when 2
    index = normalize_index(args.first)
    return nil unless (0 .. length).include?(index)
    count = args.last
    self[index ... (index + count)]
  else
    raise ArgumentError, "Expected (index), (index, length) or (index0..index1), received #{args.inspect}"
  end
end

#at(index) ⇒ Object 



65
66
67
68
69
70
71
 
# File 'lib/linked_list.rb', line 65

def at(index)
  index = normalize_index(index)
  each_with_index do |value, idx|
    return value if index == idx
  end
  nil
end

#clear ⇒ Object

Initializes this list to the empty state



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

def clear
  @cdr, @lcdr, @size = nil, nil, 0
end

#concat(other) ⇒ Object Also known as: + 



165
166
167
168
169
170
171
172
173
174
 
# File 'lib/linked_list.rb', line 165

def concat(other)
  result = new_species
  other.reverse.each do |value|
    result << value
  end
  self.reverse.each do |value|
    result << value
  end
  result
end

#dup ⇒ Object

Returns a duplicate of this list, where the nodes are also copied. FIXME: Performance hog… The implementation sucks big time.



37
38
39
 
# File 'lib/linked_list.rb', line 37

def dup
  reverse.reverse
end

#each ⇒ Object

Yields each value



42
43
44
45
46
 
# File 'lib/linked_list.rb', line 42

def each
  each_node do |node|
    yield node.value
  end
end

#empty? ⇒ Boolean

A list is empty if it doesn’t have any nodes.

Returns:

  • (Boolean) 


31
32
33
 
# File 'lib/linked_list.rb', line 31

def empty?
  cdr.nil?
end

#first ⇒ Object

Returns the first value of this list



155
156
157
 
# File 'lib/linked_list.rb', line 155

def first
  cdr.nil? ? nil : cdr.value
end

#inspect ⇒ Object

Returns a nice looking view of this list.

list = LinkedList.new
list.push "a"
list.push "b"
list.inspect
#=> ("b" ("a" nil))



201
202
203
 
# File 'lib/linked_list.rb', line 201

def inspect
  cdr.inspect
end

#last ⇒ Object

Returns the last value of this list



160
161
162
163
 
# File 'lib/linked_list.rb', line 160

def last
  return nil if empty?
  @lcdr.value
end

#map(&block) ⇒ Object

Returns a new instance of self where the values have been replaced with the results of the block’s



122
123
124
125
126
 
# File 'lib/linked_list.rb', line 122

def map(&block)
  list = dup
  list.map!(&block)
  list
end

#map! ⇒ Object

Destructively maps this list’s values to the return value of the block



115
116
117
118
119
 
# File 'lib/linked_list.rb', line 115

def map!
  each_node do |node|
    node.value = yield(node.value)
  end
end

#pop ⇒ Object Also known as: shift

Pops the head of the list, returning the value



139
140
141
142
143
144
145
146
 
# File 'lib/linked_list.rb', line 139

def pop
  return nil if empty?
  @size -= 1
  value = cdr.value
  @cdr = cdr.cdr
  @lcdr = nil if empty?
  value
end

#reverse ⇒ Object

Returns a new instance of self with a reverse insertion order



106
107
108
109
110
111
112
 
# File 'lib/linked_list.rb', line 106

def reverse
  list = new_species
  each do |value|
    list << value
  end
  list
end

#to_a ⇒ Object

Returns an Array that has the same values as this LinkedList



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

def to_a
  inject(Array.new) do |memo, value|
    memo << value
  end
end