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
andnext
pointers accordingly. - If the list is empty, the new node becomes both the
head
and thetail
. - 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 thetemp
variable. - The
tail
pointer is updated to point to the previous node of the currenttail
, and the next pointer of the newtail
is set tonil
. - The
prev
pointer of the removed node is set tonil
, effectively disconnecting it from the list. - The
length
of the list is decremented. - If the list becomes empty after the removal, both the
head
andtail
pointers are set tonil
. - 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 thetail
. - If the list is not empty, the new node is added before the current
head
node, and the head'sprev
pointer is set to the new node. - The
head
pointer is updated to point to the new node, and thelength
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 thetemp
variable. - The
head
pointer is updated to point to thenext
node of the currenthead
, and theprev
pointer of the newhead
is set tonil
. - The
next
pointer of the removed node is set tonil
, effectively disconnecting it from the list. - The
length
of the list is decremented. - If the list becomes empty after the removal, both the
head
andtail
pointers are set tonil
. - 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 thetail
, depending on the index's position relative to themidpoint
of the list. - If the index is closer to the
head
(less than half the length), it starts from thehead
and traverses forward to find the desired node. - If the index is closer to the
tail
(more than half the length), it starts from thetail
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 theget
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
andnext
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
andnext
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
andtail
pointers to reflect the new head and tail of the reversed list. - Time Complexity: O(n)
Top comments (0)