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