Linked List with Ruby
Tags: ruby, datastructures, algorithms
Published: 2023-07-02 16:32:37

## Table of Contents
&nbsp;1. [Understanding Linked Lists](#understanding-linked-lists)
&nbsp;2. [Implementing a Linked List in Ruby](#implementing-a-linked-list-in-ruby)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.1. [print_list method](#-raw-printlist-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.2. [append Method](#-raw-append-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.3. [pop Method](#-raw-pop-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.4. [prepend Method](#-raw-prepend-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.5. [shift Method](#-raw-shift-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.6. [get method](#-raw-get-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.7. [set_value method](#-raw-setvalue-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.8. [insert method](#-raw-insert-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.9. [reverse Method](#-raw-reverse-endraw-method)

github repo: https://github.com/TheZero0-ctrl/leetcode-practice

## Understanding Linked Lists

![diagram representing linked list](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3d2n99utxa315vlhyg3n.png)
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.

```ruby
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.

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

```

![gif illustrating print list method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5s9fy5z5qft0eyayuvya.gif)
- 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.

```ruby
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

```

![gif illustrating append method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/6flzcyaxbtvlhkbt3nim.gif)
- 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.

```ruby
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

```

![gif illustrating pop method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/85hm8zc90xx1lsc4zqx0.gif)
- 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.

```ruby
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

```

![gif illustrating prepend method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n2tvuv2jgex5grtlktzk.gif)
- 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.

```ruby
def shift
  return if @length.zero?

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

```

![gif illustrating shift method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1rm0qxba0y17tern7t19.gif)
- 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.

```ruby
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.

```ruby
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.

```ruby
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.

```ruby
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.

```ruby
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

```

![gif illustrating reverse method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/826ua9b44igau8ja5qpq.gif)
- 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.