####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:
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:
# 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