class DataStructures::LinkedList

Implements a doubly Linked List.

Constants

LLNode

Attributes

first[RW]
last[RW]
length[RW]
size[RW]

Public Class Methods

new(*entries) click to toggle source

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.

# 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

Public Instance Methods

<<(*elements)
Alias for: push
[](index) click to toggle source

Element Reference - Returns the element at index

# File lib/datastructures/linked_list.rb, line 36
def [] index
  current = @first
  index.times do
    current = current.next
  end
  current.data
end
[]=(index, data) click to toggle source

Element Assignment - Sets the element at index to :data

# 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) click to toggle source

Delete the node at :index

# 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() { |data| ... } click to toggle source

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

# 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?() click to toggle source

Returns true if the LinkedList is empty

# File lib/datastructures/linked_list.rb, line 31
def empty?
  @size == 0
end
index(data) click to toggle source

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

# 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) click to toggle source

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

# 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() click to toggle source

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

# 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) click to toggle source

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.

# 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
Also aliased as: <<
shift() click to toggle source

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

# 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() click to toggle source

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

# 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() click to toggle source

Returns a string representation of the list

# File lib/datastructures/linked_list.rb, line 171
def to_s
  self.to_a.to_s
end
unshift(*elements) click to toggle source

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

# 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