Hackerrank Day 15: Linked List

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).

screen-shot-2016-12-23-at-3-21-28-pm

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..

screen-shot-2016-12-23-at-3-19-07-pm

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)
Advertisements
Hackerrank Day 15: Linked List

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s