Class: DataStructures::LinkedList

Inherits:
Object
  • Object
show all
Defined in:
lib/datastructures/linked_list.rb

Overview

Implements a doubly Linked List.

Defined Under Namespace

Classes: LLNode

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*entries) ⇒ LinkedList

Returns a new LinkedList

If no arguments are sent, the new LinkedList will be empty. When one or more objects are sent as arguments, the LinkedList is populated with those objects in the order sent.



20
21
22
23
24
25
26
27
28
 
# File 'lib/datastructures/linked_list.rb', line 20

def initialize *entries
  @size = 0
  unless entries.empty?
    @first = LLNode.new(entries.shift, nil, nil)
    @last = @first
    @size = 1
    self.push(*entries) unless entries.empty?
  end
end

Instance Attribute Details

#first ⇒ Object

Returns the value of attribute first.



9
10
11
 
# File 'lib/datastructures/linked_list.rb', line 9

def first
  @first
end

#last ⇒ Object

Returns the value of attribute last.



10
11
12
 
# File 'lib/datastructures/linked_list.rb', line 10

def last
  @last
end

#size ⇒ Object Also known as: length

Returns the value of attribute size.



11
12
13
 
# File 'lib/datastructures/linked_list.rb', line 11

def size
  @size
end

Instance Method Details

#[](index) ⇒ Object

Element Reference - Returns the element at index



36
37
38
39
40
41
42
 
# File 'lib/datastructures/linked_list.rb', line 36

def [] index
  current = @first
  index.times do
    current = current.next
  end
  current.data
end

#[]=(index, data) ⇒ Object

Element Assignment - Sets the element at index to :data



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/datastructures/linked_list.rb', line 46

def []= index, data
  if index > @size - 1
    # fill in the gaps
    ((index - @size) + 1).times do
      self.push nil
    end
    @last.data = data
  else
    # replace existing value
    current = @first
    index.times do
      current = current.next
    end
    current.data = data
  end
  self
end

#delete(index) ⇒ Object

Delete the node at :index



78
79
80
81
82
83
84
85
 
# File 'lib/datastructures/linked_list.rb', line 78

def delete index
  current = @first
  index.times do
    current = current.next
  end
  current.previous.next = current.next
  current.next.previous = current.previous
end

#each(&block) ⇒ Object

Calls the given block once for each element in self, passing that element as a parameter



89
90
91
92
93
94
95
 
# File 'lib/datastructures/linked_list.rb', line 89

def each &block
  current = @first
  @size.times do
    yield current.data
    current = current.next
  end
end

#empty? ⇒ Boolean

Returns true if the LinkedList is empty

Returns:

  • (Boolean) 


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

def empty?
  @size == 0
end

#index(data) ⇒ Object

Returns the first index equal to data (using == comparison). Counts from the beginning of the list.



148
149
150
151
152
153
154
155
156
157
 
# File 'lib/datastructures/linked_list.rb', line 148

def index data
  current = @first
  i = 0
  while !current.nil?
    return i if current.data == data
    current = current.next
    i += 1
  end
  nil
end

#insert(index, data) ⇒ Object

Insert a node with :data at :index. All nodes :index and above get moved along one.



66
67
68
69
70
71
72
73
74
75
 
# File 'lib/datastructures/linked_list.rb', line 66

def insert index, data
  old_node = @first 
  index.times do
    old_node = old_node.next
  end
  new_node = LLNode.new(data, old_node, old_node.previous)
  old_node.previous.next = new_node
  old_node.previous = new_node
  self
end

#pop ⇒ Object

Removes the last element from self and returns it. Raises an underflow error if empty.



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

def pop
  raise "Linked List underflow: nothing to pop." if self.size == 0
  last = @last
  @last = @last.previous
  @size -= 1
  last.data
end

#push(*elements) ⇒ Object Also known as: <<

Append - Pushes the given object(s) on to the end of this Linked List. The expression returns the list itself, so several appends may be chained together. See also #pop for the opposite effect.



100
101
102
103
104
105
106
107
108
109
 
# File 'lib/datastructures/linked_list.rb', line 100

def push *elements
  elements.each do |element|
    node = LLNode.new(element, nil, @last)
    @first = node if @first.nil?
    @last.next = node unless @last.nil?
    @last = node
    @size += 1
  end
  self
end

#shift ⇒ Object

Removes the first element of self and returns it (shifting all other elements down by one.



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

def shift
  raise "Linked List underflow: nothing to shift." if self.size == 0
  first = @first
  @first = @first.next
  @size -= 1
  first.data
end

#to_a ⇒ Object

Returns an array containing the data from the nodes in the list



160
161
162
163
164
165
166
167
168
 
# File 'lib/datastructures/linked_list.rb', line 160

def to_a
  current = @first
  array = []
  while !current.nil?
    array << current.data
    current = current.next
  end
  array
end

#to_s ⇒ Object

Returns a string representation of the list



171
172
173
 
# File 'lib/datastructures/linked_list.rb', line 171

def to_s
  self.to_a.to_s
end

#unshift(*elements) ⇒ Object

Prepends objects to the front of self, moving other elements upwards. See also #shift for the opposite effect.



125
126
127
128
129
130
131
132
133
134
 
# File 'lib/datastructures/linked_list.rb', line 125

def unshift *elements
  elements.each do |element|
    node = LLNode.new(element, @first, nil)
    @last = node if @last.nil?
    @first.previous = node unless @first.nil?
    @first = node
    @size += 1
  end
  self
end