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)

DEV Community

Doubly Linked List Implementation in Ruby

Table of Contents

Understanding Doubly Linked List