Algorithm Night
===============

####Linked Lists
- reference based ds
- a collection of node objects
- each node possesses a value and a reference

_PRO:_ adding anywhere but the end is better
_CON:_ adding at the end takes longer (have to find 'end')

- no bound capacity, fixed sized arrays aren't a problem anymore in other languages
- basis for other data structures (e.g. trees, graphs)

- used on other data structures we discussed two weeks ago (stacks, queques)

#####Node Class:
`````ruby
class Node
  # contains value and a reference
  attr_accessor :value, :next


  def initialize value
    @value = value
  end
end

first       = Node.new(42)
second      = Node.new(-3)
third       = Node.new(17)
fourth      = Node.new(0)

first.next  = second
second.next = third
third.next  = fourths
```````

#####Linked List Class:
`````ruby

# out linked list holds our nodes and allows us
# to call us methods/functions on them
class LinkedList
  attr_accessor :head, :size

  # Initially there is no 'head' and the size of the list is 0
  def initialize
    @head = nil
    @size = 0
  end

  def add_to_end value
    if @size == 0

      @head = Node.new(value)
      @size += 1
    else

      current = @head
      index = 0
      while index < @size
        current.next = Node.new(value) if current.next == nil
        current = current.next
        index += 1
      end
      @size += 1
    end
  end


end
`````````