Linked Lists

A linked list is a series of nodes that contain two things each, a value, and a reference to the next node in the list. The first node in a linked list will reference the second node, the second will reference the third, all the way until node n, which is the last node, which references NIL. If this sounds a lot like recursion, then you are on the right track. Linked Lists are known as recursive data structures. The benefits of a Linked List over something such as an Array is that it is easy to insert a new item into the linked list in Constant Time, and there are no size restrictions such as there are in Arrays.

Ruby Implementation

Lets try to re-create a Linked List in Ruby. Linked lists are not included in the Ruby source code, as they are not often used, and Ruby uses a number of tricks to get a lot of the same benefits of Linked Lists out of Arrays. However, Linked Lists are often asked about in Interviews, and are an interesting data structure to understand.

class Node
  attr_accessor: :value, :next

  def initialize(value,next = nil)
    @value = value
    @next = next
  end
end

Lets make a quick linked list


# Declare the variables and give them values
node1 = Node.new("First")
node2 = Node.new("Second")
node3 = Node.new("Third")

# Next link them all up
node1.next = node2
node2.next = node3

We just made a very simple linked list! We can reference various value by calling their value property, and traverse our way along the list by going to each "next" in succession.

Lets write a method that runs through the list and prints each list when given a starting node.


def self.print_list(node,msg = nil)
  msg ||= ''
  return msg[0..-5] if node.nil?
  self.print_list(node.next,msg << "#{node.node} -> ")
end

Here you see first-hand the Linked Lists' recursive nature.


Node.print_list node1
=> "First -> Second -> Third"
Insertion

We know that the main benefit of Linked Lists is that new nodes can be quickly inserted into them. Lets take a look at how to do that 3 different ways, Insertion at the beginning, insertion at the end, and insertion at a given point in the middle of the linked list

Beginning

Something that gives me trouble about linked lists is how to initially refer to them. Because they are each independent Nodes that are just referencing their respective "next" nodes, there does not seem be that singular entity that can be referenced such as one can with an Array or a Hash. The key here, at least I think, is that the head of the linked list must be kept in a variable or class somewhere, as that is the only way to ever get that value (please correct me if I'm wrong). If each node references only the "next" node, then no node references the first node. For this reason, we need to keep it in memory on our own.

Knowing this, lets go about adding a new node to the beginning of our Linked List


linked_list_head = node1

our_new_node = Node.new("New First")
old_head = linked_list_head
our_new_node.next = old_head
linked_list_head = our_new_node.next

Boom, our Linked List has a new node at the beginning. It does not matter the length of the Linked List, this is a constant time operation.

End

We have two options of implementing a "tail insertion" to a Linked List. If we store the "tail" of our list, as we did for our "head", then it will be a very similar implementation. This has some added costs, as keeping a link such as that can make other things complicated (what if the tail and the head were the same node in a 1 node list?). For the purposes of this exercise, lets assume we do not store the tail in a variable, and need to find it in order to add a node to the end of the list.


class Node
  def self.tail(node)
    return node if node.next.nil?
    tail(node.next)
  end
end

#now we just use the tail and replace it with our new node

new_tail_node = Node.new("Last")

old_tail_node = Node.tail(linked_list_head) # we still have our head after all
old_tail_node.next = new_tail_node

Our list now has a new node at the end. This operation is constant time if you store the tail in a variable, but O(N) time in the way we did it, because we had to traverse the entire node.

Middle (Point X)

Lets say we want to add a new node that will be the 3rd node in a linked list. If we don't know the node that is right in front of it, we need to traverse the list in order to do this. At which point our code will be very similar to our "Beginning Insertion".


class Node
  def self.find_node_at_x(node,x) #the first element is 0
    node = node
    (x).times do
      node = node.next
    end
    node
  end
end

# now lets say we want to add a new node to the 3rd position in our linked list

second_node = Node.find_node_at_x(linked_list_head, 1) # we want to find the second node so we can link it to our new third
new_third = Node.new("I'm the new third node")
new_third.next = second_node.next.next
second_node.next = new_third

This has a run time of O(N) because we need to traverse the list to find our node. If you look at the A link, it says that middle insertion is O(1). I think this is a little strange, because they do not count the finding of the node to be a part of the operation. If you include the traversal, which we did, then it is O(N).

Conclusion

Linked lists are rarely seen in the wild, but they are a interesting data type to look at. Thinking about and implementing a recursive data type like a Linked List is a fun exercise in understanding Recursion in general, so I was happy to dig into it.

Please let me know if you see anything strange or incorrect in this post.

JM

Shout Outs

http://matt.weppler.me/2013/08/14/implementing-a-linked-list-in-ruby.html for help on implementation http://www.sitepoint.com/rubys-missing-data-structure/ for better understanding its role in Ruby

comments powered by Disqus