Doubly Linked List Implementation in Ruby
Tags: ruby, algorithms, datastructures
Published: 2023-08-09 15:29:40

## Table of Contents
&nbsp;1. [Understanding Doubly Linked List](#understanding-doubly-linked-list)
&nbsp;2. [Implementation of Doubly Linked List](#implementation-of-doubly-linked-list)

&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-method-endraw-)

&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. [Remove Method](#-raw-remove-endraw-method)

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 2.10. [Reverse method](#-raw-reverse-endraw-method)

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

## Understanding Doubly Linked List

![Image describing doubly linked list](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gobmsdrx92jm1cazztr1.png)
A Doubly Linked List is a data structure that consists of a sequence of nodes, where each node contains a value and two pointers, one pointing to the previous node and the other pointing to the next node. This allows for efficient insertion and deletion operations at both the beginning and end of the list, unlike a singly linked list.

## Implementation of Doubly Linked List
we will explore a Ruby implementation of a Doubly Linked List using two classes: `DoublyLinkedList` and `Node`. We will discuss each method along with their time complexities.
Here is the code for `Node` and `DoublyLinkedList` classes

```ruby
class DoublyLinkedList
  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, :prev

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

```
Only different with linked list is that Node not only have next pointer but also prev pointer
### `print_list` method
It is same as `print_list` method of linked list
```ruby
def print_list
  temp = head
  while temp
    puts temp.value
    temp = temp.next
  end
end

```
### `append` method

```ruby
def append(value)
  new_node = Node.new(value)
  if @head
    new_node.prev = @tail
    @tail.next = new_node
  else
    @head = new_node
  end

  @tail = new_node
  @length += 1
  true
end

```

![Illustration representing append method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nkr5o5cskbgvokqlrl9c.gif)
- The `append` method adds a new node with the given value to the end of the list.
- It creates a new node and updates the `prev` and `next` pointers accordingly.
- If the list is empty, the new node becomes both the `head` and the `tail`.
- The `length` of the list is incremented by 1.
- Time Complexity: O(1)

### `pop` method

```ruby
def pop
  return nil if @length.zero?

  temp = @tail
  @tail = temp.prev
  @tail.next = nil
  temp.prev = nil
  @length -= 1

  return temp unless @length.zero?

  @head = nil
  @tail = nil

  temp
end

```

![Illustration representing pop method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qdiikvudzwity1hlbaag.gif)

- The `pop` method removes the last node (tail) from the doubly linked list and returns it.
- If the list is empty (length is zero), it returns `nil`.
- The `tail` node is stored in the `temp` variable.
- The `tail` pointer is updated to point to the previous node of the current `tail`, and the next pointer of the new `tail` is set to `nil`.
- The `prev` pointer of the removed node is set to `nil`, effectively disconnecting it from the list.
- The `length` of the list is decremented.
- If the list becomes empty after the removal, both the `head` and `tail` pointers are set to `nil`.
- Time Complexity: O(1)

### `Prepend` Method

```ruby
def prepend(value)
  new_node = Node.new(value)
  if @length.zero?
    @head = new_node
    @tail = new_node
  else
    new_node.next = @head
    @head.prev = new_node
    @head = new_node
  end

  @length += 1
  true
end

```

![Illustration representing prepend method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9b3vmojxm9vn42uddxp4.gif)

- The `prepend` method adds a new node with the given value at the beginning of the doubly linked list.
- It creates a new node using the input value.
- If the list is empty (@length is zero), the new node becomes both the `head` and the `tail`.
- If the list is not empty, the new node is added before the current `head` node, and the head's `prev` pointer is set to the new node.
- The `head` pointer is updated to point to the new node, and the `length` of the list is incremented.
- Time Complexity: O(1)

### `Shift Method`

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

  temp = @head
  @head = temp.next
  @head.prev = nil
  temp.next = nil
  @length -= 1

  return temp unless @length.zero?

  @head = nil
  @tail = nil

  temp
end

```

![Illustration representing shift method](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a2bds8pnbs4qx57y94ot.gif)

- The `shift` method removes the first node (head) from the doubly linked list and returns it.
- If the list is empty (length is zero), it returns `nil`.
- The `head` node is stored in the `temp` variable.
- The `head` pointer is updated to point to the `next` node of the current `head`, and the `prev` pointer of the new `head` is set to `nil`.
- The `next` pointer of the removed node is set to `nil`, effectively disconnecting it from the list.
- The `length` of the list is decremented.
- If the list becomes empty after the removal, both the `head` and `tail` pointers are set to `nil`.
- Time Complexity: O(1)

### `Get` Method

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

  if index < @length / 2
    temp = @head
    (0...index).each do |_i|
      temp = temp.next
    end
  else
    temp = @tail
    (index...@length - 1).each do |_i|
      temp = temp.prev
    end
  end
  temp
end

```

- The `get` method retrieves the node at the specified index in the doubly linked list.
- If the index is out of bounds (negative or greater than or equal to the list length), it returns `nil`.
- To optimize the search, it chooses to start from either the `head` or the `tail`, depending on the index's position relative to the `midpoint` of the list.
- If the index is closer to the `head` (less than half the length), it starts from the `head` and traverses forward to find the desired node.
- If the index is closer to the `tail` (more than half the length), it starts from the `tail` and traverses backward to find the desired node.
- Time Complexity: O(n)

### `set_value` Method

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

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

```

- The `set_value` method updates the value of the node at the specified index in the doubly linked list.
- It uses the `get` method to retrieve the node at the given index.
- If the node is found, its value is updated with the input value, and the method returns true.
- If the index is out of bounds and the node is not found, it returns false.
- Time Complexity: O(n) - The time complexity of the `set_value` method depends on the time complexity of the `get` method, which is O(n).

### `Insert` Method

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

  return prepend(value) if index.zero?

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

  new_node = Node.new(value)
  before = get(index - 1)
  after = before.next

  new_node.prev = before
  new_node.next = after

  before.next = new_node
  after.prev = new_node

  @length += 1
  true
end

```

- The `insert` method adds a new node with the given value at the specified index in the doubly linked list.
- If the index is out of bounds (negative or greater than or equal to the list length), it returns `nil`.
- If the index is zero, the method prepends the new node to the beginning of the list using the `prepend` method.
- If the index is equal to the length of the list minus one, the method appends the new node to the end of the list using the `append` method.
- Otherwise, a new node is created and inserted between the nodes at the index - 1 (before) and index (after).
- The `prev` and `next` pointers of the new node and the adjacent nodes are adjusted to insert the new node into the list.
- Time Complexity: O(n)

### `Remove` Method

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

  return shift if index.zero?

  return pop if index == @length - 1

  temp = get(index)
  before = temp.prev
  after = temp.next

  before.next = after
  after.prev = before

  temp.next = nil
  temp.prev = nil

  @length -= 1
  temp
end

```

- The `remove` method removes the node at the specified index from the doubly linked list and returns it.
- If the index is out of bounds (negative or greater than or equal to the list length), it returns `nil`.
- If the index is zero, the method removes the first node from the list using the `shift` method.
- If the index is equal to the length of the list minus one, the method removes the last node from the list using the `pop` method.
- Otherwise, it retrieves the node at the specified index using the `get` method and removes it from the list.
- The `prev` and `next` pointers of the adjacent nodes are adjusted to disconnect the removed node from the list.
- Time Complexity: O(n)

### `Reverse` method

```ruby
def reverse
  temp = @head
  while temp
    temp.next, temp.prev = temp.prev, temp.next
    temp = temp.prev
  end

  @head, @tail = @tail, @head
end
```

- The `reverse` method is used to reverse the order of nodes
- it does this by traversing through the list, and for each node, it swaps the next and prev pointers.
- Finally, it updates the `head` and `tail` pointers to reflect the new head and tail of the reversed list.
- Time Complexity: O(n)