Linked lists are not an all purpose tool. In fact, the first time you play with a linked list will probably be to help develop your conceptual understanding of computer science theories. But you already, undoubtedly know a little bit about their functionality through other ruby data structures.

A linked list is a data structure used to sort and organize data. A linked list is similar to an array: it stores data at a particular value. However, it differs as each element in a linked list (called a node), has knowledge of the node that comes after it. You can think of a node object like this:

A node object contains the node itself as well as a pointer to the object that follows it (The link in linked list!). It therefore takes up more memory than an array. Here is what the node object looks like in ruby:

1
2
3
4
5
6
7
8
9

class Node
  attr_accessor :data, :pointer

  def initialize(data, pointer = nil)
    @data = data
    @pointer = pointer
  end

end

When the node is initialized, it has data as well as a pointer to the next node (this can be set to nil, if the proceeding node does not exist or is itself a nil value).

Now lets get in the console and play!

1
2
3
4
5

node_1 = Node.new("Hiya Buddy!")
 => #<Node:0x007fd1931b6f18 @data="Hiya Buddy!", @pointer=nil>  

node_2 = Node.new("Right Back Atcha!")
 => #<Node:0x007fd193184ea0 @data="Right Back Atcha!", @pointer=nil> 

We have two nodes, but both node_1’s pointer and node_2’s pointer’s are nil. In order for them to be connected to create the beginning of a linked list we need to set node_1’s pointer to node_2 as such:

1
2
3
4

 node_1.pointer = node_2

 node_1
  => #<Node:0x007fd1931b6f18 @data="Hiya Buddy!", @pointer=#<Node:0x007fd193184ea0 @data="Right back atcha!", @pointer=nil>> 

Now we can see that the object node_1 has knowledge of the node_2 object. This is the beginning of a linked list. You will commonly see the next method, used in place of a pointer. However, because next is a key word in ruby, we can’t initialize it in the node object–yet keep calm, we can alias the method as so:

1
2
3
4
5
6
7
8
9
10

class Node
  attr_accessor :data, :pointer
  alias_method :next, :pointer

  def initialize(data, pointer = nil)
    @data = data
    @pointer = pointer
  end

end

This will allow us to call the next method through the node object itself. Therefore if I want to call the node_2 object. I can do it as such:

1
2

node_1.next
 => #<Node:0x007fd192b4efb8 @data="Right Back atcha!", @pointer=nil> 

In a singly linked list there is a head, which represents the beginning of a linked list. To create this relationship, we will need a new object, our Linked List object, composed of our node objects.

1
2
3
4
5
6
7

class LinkedList
  attr_accessor :head, :data, :pointer

  def initialize(data)
    @head = Node.new(data, pointer)
  end
end

Here we have our very own linked list, we can begin to add methods to–for example, we can create a method to store data at the beginning of our linked list:

lets say we have the following linked list that looked like this:

1

a -> b -> c

To insert the string “the abc’s” into the 0 index, we would need to first create a new node object with the data “the abc’s” and set our new node object’s pointer to a, the current head of our linked list.

This would give us:

1

"the abc's" -> a -> b -> c

That said, the method should look like this:

1
2
3
4
5

  def unshift(data)
    new_node = Node.new(data) #first we create a new node
    new_node.pointer = @head #we set the pointer to the head (a) of our linked list
    @head = new_node #our new node become the new head, still pointing to (a) 
  end

This adds a node object at the beginning of our linked list by first creating a new node object, and then setting it’s pointer to the current head object (the first object in the list).

Now, what if we wanted to insert a value in the center of our linked list?

Say we want our linked list to look as such:

1

"the abc's" --> a --> b --> "psych!" --> c

To insert “psych” into the third index, we would have to move to the second index to get b, create a new node, “psych!”, set b’s pointer to “psych” and then set the pointer of our new node to c.

Our new code would look like this!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def insert_at_index(index, value)
  current = head

    (index - 1).times do
      if current.pointer == nil
        next_node = Node.new(nil, nil)
        next_node.pointer = current.pointer
        current.pointer = next_node
      end
      current = current.next
    end
  end
  new_node = Node.new(value) #new node "psych!"
  if current.pointer != nil
    new_node.pointer = current.pointer #"psych!"'s next node is b's next, c
  end
    current.pointer = new_node #b's next is "psych"
end

Please note, that this method will not work if you want to insert a new note at the beginning of the linked list, for this your user should be directed to the unshift method.

Now, onto the bigger questions: Why would we want to use a linked list instead of an Array?

Well, lets compare using a chart:

And there you have it. The hows and whys of linked lists. Good luck on your next and all future interviews!