Doubly Linked List Implementation in Ruby

Table of Contents

 1. Understanding Doubly Linked List
 2. Implementation of Doubly Linked List

       2.1. print_list method

       2.2. append method

       2.3. pop method

       2.4. Prepend Method

       2.5. Shift Method

       2.6. Get Method

       2.7. set_value Method

       2.8. Insert Method

       2.9. Remove Method

       2.10. Reverse method

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

Understanding Doubly Linked List

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

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

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

append method

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

• 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

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

• 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

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

• 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

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

• 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

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

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

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

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

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)