Linked List: A data structure that consists of a group of nodes which represent a sequence together.
- Order matters (can’t move nodes around)
- Space is dynamic
- Each node contains data and reference to the next node.
- The last node does not have reference to the next node because it’s the last one and there’s nothing to reference to.
A real life example would be a train (linked list) made up of multiple train cars (nodes). Each car contains data of how many people are in the car, and it references to the next car (except the last car which references nothing/null).
My solution in Ruby:
I managed to solve this problem by digging around other people’s codes (in other languages), but I’m still not quite sure I understand it completely..
Things I learned:
- You could implement a linked list using classes, but arrays will give linked-list like behavior using the standard array methods. Below is an example of a linked list.
# A very simple representation class Node attr_accessor :value, :next_node def initialize(value, next_node=nil) @value = value @next = next_node end end class LinkedList def initialize(value) @head = Node.new(value) end def add(value) current = @head while !current.next_node.nil? current = current.next_node end current.next_node = Node.new(value) end end ll = LinkedList.new ll.add(10) ll.add(20)