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
insertmethod, 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
fetchmethod accepts also positive and negative integers as index Deleteremoves 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!!