A linked list is a collection of nodes where each node contains a value and a reference to the next node in the sequence. The first node is called the head, and the last node is called the tail. The tail node's reference points to nil, indicating the end of the list.

In this blog post, we will explore a simple implementation of a linked list in Ruby and discuss each method along with its time complexity.

Implementing a Linked List in Ruby

Let's start by examining the provided Ruby code that implements a linked list. The LinkedList class represents the linked list, and each node is represented by the Node class.

class LinkedList
  attr_accessor :head, :tail, :length

  def initialize(value)
    new_node = Node.new(value)
    @head = new_node
    @tail = new_node
    @length = 1
  end

  # Other methods...
end

class Node
  attr_accessor :value, :next

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

The initialize method is the constructor of the LinkedList class and Node class.
It creates a new instance of the linked list with an initial value and a new instance of the node.
When a new node is created, its value will be the provided value, and the next node will be nil.
When a new linked list is created, it creates a new node object with the given value.
This node is set as both the head and tail of the linked list.
The length attribute is initialized to 1 since there is only one node in the list at the beginning.

`print_list` method

The print_list method iterates through the linked list and prints the value of each node.

def print_list
  temp = head
  while temp
    puts temp.value
    temp = temp.next
  end
end

Starting from the head node, the method iterates through the list by following the next reference of each node.
It prints the value of each node and continues until it reaches the end of the list (when temp becomes nil).
The time complexity of the print_list method is O(n), where n is the length of the linked list.
It needs to visit each node once to print its value.

`append` Method

The append method adds a new node with the given value at the end of the linked list.

def append(value)
  new_node = Node.new(value)
  if @head
    @tail.next = new_node
    @tail = new_node
  else
    @tail = new_node
    @head = new_node
  end
  @length += 1
  true
end

First, a new node is created with the provided value.
If the linked list is not empty (the @head node exists), the next reference of the current tail node is set to the new node, and the tail is updated to the new node. This way, the new node becomes the new tail.
If the linked list is empty, both the head and tail are set to the new node.
At last, we increment length by one
The time complexity of the append method is O(1) since it performs a constant number of operations regardless of the size of the linked list. It directly accesses and updates the tail node.

`pop` Method

The pop method removes and returns the last node from the linked list.

def pop
  return if @length.zero?

  temp = @head
  pre = @head

  while temp.next
    pre = temp
    temp = temp.next
  end

  @tail = pre
  @tail.next = nil

  @length -= 1

  return temp unless @length.zero?

  @head = nil
  @tail = nil

  temp
end

To remove the last node, the method iterates through the list until it reaches the second-to-last node.
The pre variable keeps track of the previous node while the temp variable moves forward.
After reaching the last node, it updates the tail to the second-to-last node, removes the reference to the last node, and decrements the length of the list.
If the list becomes empty after removing the last node, both the head and tail are set to nil.
The time complexity of the pop method is O(n), where n is the length of the linked list.
It needs to traverse the list to reach the second-to-last node for removal.

`prepend` Method

The prepend method adds a new node with the given value at the beginning of the linked list.

def prepend(value)
  new_node = Node.new(value)
  new_node.next = @head
  @head = new_node
  @tail = new_node if @length.zero?
  @length += 1
  true
end

First, a new node is created with the provided value.
The next reference of the new node is set to the current head node.
Then, the head is updated to the new node.
If the linked list was initially empty (length was zero), the tail is also set to the new node since it is the only node in the list.
At last, we increment length by one
The time complexity of the prepend method is O(1) since it performs a constant number of operations regardless of the size of the linked list.
It directly accesses and updates the head node.

`shift` Method

The shift method removes and returns the first node from the linked list.

def shift
  return if @length.zero?

  temp = @head
  @head = temp.next
  temp.next = nil
  @tail = nil if @length == 1
  @length -= 1
  temp
end

The method removes the head node by updating the head to its next node.
It also updates the next reference of the removed node to nil to detach it from the list.
If the list becomes empty after removal (length was initially one), the tail is set to nil.
At last, we decrement length by one.
The time complexity of the shift method is O(1) since it performs a constant number of operations regardless of the size of the linked list.
It directly accesses and updates the head node.

`get` method

The get method returns the node at the specified index in the linked list.

def get(index)
  return if index >= @length || index.negative?

  temp = @head
  (0...index).each do |_i|
    temp = temp.next
  end
  temp
end

The method first checks if the provided index is valid (within the range of the list).
If the index is not valid (greater than or equal to the length or negative), it returns nil.
Otherwise, it iterates through the list to reach the desired index and returns the corresponding node.
The time complexity of the get method is O(n), where n is the length of the linked list.
It needs to traverse the list to reach the desired index.

`set_value` method

The set_value method sets the value of the node at the specified index in the linked list.

def set_value(index, value)
  temp = get(index)

  if temp
    temp.value = value
    true
  else
    false
  end
end

The method first uses the get method to retrieve the node at the specified index.
If the node exists, it updates its value with the provided value and returns true.
Otherwise, it returns false.
The time complexity of the set_value method is O(n), where n is the length of the linked list.
It utilizes the get method, which has a time complexity of O(n), to retrieve the node at the specified index.

`insert` method

The insert method inserts a new node with the given value at the specified index in the linked list.

def insert(index, value)
  return if index >= @length || index.negative?

  return prepend(value) if index.zero?

  return append(value) if index == @length - 1

  temp = get(index - 1)

  new_node = Node.new(value)

  new_node.next = temp.next

  temp.next = new_node
  @length += 1
  true
end

First, it checks if the provided index is valid. If not, it returns nil.
If the index is zero, it uses the prepend method to add the new node at the beginning.
If the index is equal to the length minus one, it uses the append method to add the new node at the end.
Otherwise, it retrieves the node at the previous index (index - 1) using the get method.
Then, it creates a new node with the provided value and inserts it into the list by updating the next references accordingly.
At last, we increment length by one
The time complexity of the insert method is O(n), where n is the length of the linked list.
It utilizes the get method, which has a time complexity of O(n), to retrieve the node at the specified index.

`remove` method

The remove method removes and returns the node at the specified index in the linked list.

def remove(index)
  return if index >= @length || index.negative?

  return shift if index.zero?

  return pop if index == @length - 1

  prev = get(index - 1)
  temp = prev.next
  prev.next = temp.next
  temp.next = nil
  @length -= 1

  temp
end

The method first checks if the provided index is valid. If not, it returns nil.
If the index is zero, it uses the shift method to remove and return the head node.
If the index is equal to the length minus one, it uses the pop method to remove and return the tail node.
Otherwise, it retrieves the node at the previous index (index - 1) using the get method.
It updates the next references to detach the node at the specified index from the list.
At last, we decrement length by one.
The time complexity of the remove method is O(n), where n is the length of the linked list.
It utilizes the get method, which has a time complexity of O(n), to retrieve the node at the specified index.

`reverse` Method

The reverse method reverses the linked list by changing the order of the nodes.

def reverse
  temp = @head
  @head = @tail
  @tail = temp
  after = temp.next
  before = nil

  (0...@length).each do |_i|
    after = temp.next
    temp.next = before
    before = temp
    temp = after
  end
end

The method starts by swapping the head and tail nodes.
Then, it iterates through the list and reverses the next references of each node.
It uses three variables (temp, before, and after) to keep track of the nodes being reversed.
The loop continues until all nodes are reversed.
The time complexity of the reverse method is O(n), where n is the length of the linked list.
It needs to traverse the list once to reverse the nodes.

DEV Community

Linked List with Ruby

Table of Contents

Understanding Linked Lists

Implementing a Linked List in Ruby

`print_list` method

`append` Method

`pop` Method

`prepend` Method

`shift` Method

`get` method

`set_value` method

`insert` method

`remove` method

`reverse` Method

Top comments (0)

Read next

Exploring Basic Data Structures and Their Applications in LeetCode Problems

Buh-Bye Webpack and Node.js, Hello Rails and Import Maps

2053. Kth Distinct String in an Array

Daliy.rust day 3