Data Structures 101 - LinkedList implementation


In this post, we are going to analyze how to implement a LinkedList object in Ruby. A linked list is a linear collection of elements, usually called nodes, that have a pointer to the next element in the collection. For further details, check out the Wikipedia article.

Since we are implementing a collection like Array in Ruby, it would be nice to follow some common methods definitions made in the Array class, such as: push, <<, insert, fetch and delete. For the final version, check the code at DataStructures101.

Initial implementation

A LinkedList object similar to what Array object could end up being huge, so we are going to have as a goal to implement the main functionalities for a list to being usable.

Node object

The Node object is the holder of the data we want to store within the list as well as the pointer to the next element (i.e., node) in the list. A simple implementation could be as shown below:

class Node
    attr_accessor :value, :next

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

The Node class contains two accessors value and next to store the actual content of the list and the pointer to next node in the list respectively.

LinkedList object

Now, let’s focus on the actual LinkedList implementation. We have several details worth pointing out, such as:

  • Using a dummy node (@head) to hold the start of the nodes sequence, which helps create easier code.
  • As done in the Array class in the insert method, if the index is positive, it will insert the elements before the element with the current index, if negative it will be inserted after the element at the index.
  • The fetch method accepts also positive and negative integers as index
  • Delete removes all the occurrence of the value in the list and returns either nil if no element match or the last occurrence of the element.
class LinkedList

  attr_reader :size

  def initialize
    @size = 0
    @head = Node.new(nil)
  end

  def push(*values)
    curr = fetch_node(size - 1)
    values.each do |value|
      curr = add_node(value, curr)
    end
    self # Allows to concatenate consecutive calls to push
  end

  def <<(value)
    push(value)
  end

  # It will insert before the element at index if index >= 0
  # otherwise, it will insert after the element at index
  def insert(index, *values)
    curr = fetch_node(index >= 0 ? index - 1 : index)

    values.each do |value|
      curr = add_node(value, curr)
    end
    self
  end

  def fetch(index)
    fetch_node(index).value
  end

  def delete(value)
    prev = @head
    curr = @head.next
    return_value = nil
    until curr.nil?
      if curr.value == value
        remove_node(prev, curr)
        return_value = curr.value
      end
      prev = curr
      curr = curr.next
    end

    return_value
  end

  private

  def fetch_node(index)
    index += size if index < 0
    raise IndexError if index < 0 || index >= size

    pos = 0
    curr = @head.next
    while pos < index
      curr = curr.next
      pos += 1
    end

    curr
  end

  def add_node(value, prev_node)
    node = Node.new(value)
    prev_node.next = node
    @size += 1
    node
  end

  def remove_node(prev, curr)
    prev.next = curr.next
    @size -= 1
  end
end

Double Linked List

A double linked list is a variation of the classic linked list structure that supports iterating backward and forward over the sequence of nodes by using two pointers in each of the nodes holding the references to the previous and next nodes in the sequence. For more details, check the Wikipedia article.

For this iteration of the class, we want to also add methods such as: last, first present in the Array class and to mix in the Enumerable module to provide each, map methods among others.

Changes to Node class

To update our Node class accordingly, we have to add a pointer to hold the reference to the previous node in the sequence.

class Node
  attr_accessor :value, :prev, :next

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

This change will allows us to travel back and forth across the nodes of the list.

Double LinkedList implementation

Using the updated version of our Node class, we can proceed to show the implementation of the LinkedList class. We have made several changes in order to take advantage of the presence of the double link functionalities in the nodes:

  • Introduces another dummy node @tail to keep track of the end of list
  • Now, pushing an element is O(1) instead of O(N) as in the first version
  • Last element can be implemented in O(1) too, i.e. @tail.prev.value
class LinkedList
  include Enumerable

  attr_reader :size

  def initialize(*values)
    @size = 0
    @head = Node.new(nil)
    @tail = Node.new(nil, @head)
    @head.next = @tail

    push(*values)
  end

  def <<(value)
    push(value)
  end

  def delete(value)
    curr = @head.next
    return_value = nil
    until curr == @tail
      if curr.value == value
        remove_node(curr)
        return_value = curr.value
      end
      curr = curr.next
    end

    return_value
  end

  def each(&block)
    curr = head.next
    until curr.nil?
      block.call(value)
      curr = curr.next
    end
  end

  def fetch(index)
    fetch_node(index).value
  end

  def insert(index, *values)
    curr = fetch_node(index)

    curr = index < 0 ? curr : curr.prev

    values.each do |value|
      curr = add_node(value, curr.next)
    end
    self
  end

  def first(n = nil)
    return @head.next.value if n.nil?

    raise ArgumentError, "negative array size" if n < 0

    return new_list_from_range(0, n - 1)
  end

  def last(n = nil)
    return @tail.prev.value if n.nil?

    raise ArgumentError, "negative array size" if n < 0

    return new_list_from_range(size - n, size - 1)
  end

  def push(*values)
    values.each do |value|
      add_node(value, @tail)
    end
    self # Allows to concatenate consecutive calls to push
  end

  private

  def fetch_node(index)
    index += size if index < 0
    if index < 0 || index >= size
      raise IndexError, "index #{index} outside of array bounds: #{-size}...#{size}"
    end

    pos = 0
    curr = @head.next
    while pos < index
      curr = curr.next
      pos += 1
    end

    curr
  end

  def add_node(value, next_node)
    node = Node.new(value, next_node.prev, next_node)
    node.prev.next = node
    node.next.prev = node
    @size += 1
    node
  end

  def remove_node(node)
    node.prev.next = node.next
    node.next.prev = node.prev
    @size -= 1
  end

  def new_list_from_range(start_index, finish_index)
    new_list = LinkedList.new

    return new_list if size == 0 || start_index == size || finish_index == -1

    start_index = 0 if start_index < 0
    finish_index = size - 1 if finish_index >= size

    start_node = fetch_node(start_index)
    finish_node = fetch_node(finish_index)

    until start_node == finish_node.next
      new_list << start_node.value
      start_node = start_node.next
    end

    new_list
  end

end

One thing to highlight is the addition of testing for valid params that we didn’t show in the first iteration, so now there are several exceptions in place to be raised to avoid faulty usage :). Last, but not least, the gem code also provides the corresponding specs for the class tested with RSpec.

Now to wrap it up, thanks to read till the very end and hopefully, you may have learned something new or refresh previous knowledge. See you and stay tuned for more!!

Disclaimer: The opinions expressed herein are my own personal opinions and do not represent my employer’s view in any way.