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 it till the very end and hopefully, you may have learned something new or refresh previous knowledge. See you and stay tuned for more!!