## 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

## 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)

## Top comments (0)