1. Introduction
A Doubly Linked List is a type of linked list in which each node contains a data part and two pointers. The two pointers are:
1. A pointer to the next node in the sequence (next_node).
2. A pointer to the preceding node in the sequence (prev_node).
This bidirectional link allows for more efficient traversal in both directions, but at the cost of increased complexity in insertion and deletion operations, as well as increased memory overhead due to the extra pointer.
2. Implementation Steps
1. Define the Node class, which will have three attributes: value, next_node, and prev_node.
2. Initialize the DoublyLinkedList class with a head node and a tail node, both set to nil.
3. Implement the append method to add elements to the end of the list.
4. Implement the prepend method to add elements at the beginning.
5. Implement the delete method to remove a node from the list.
6. Implement the size method to get the number of elements in the list.
7. Implement the at method to get the node at a given index.
3. Implementation in Ruby Programming
class Node
attr_accessor :value, :next_node, :prev_node
def initialize(value)
@value = value
@next_node = nil
@prev_node = nil
end
end
class DoublyLinkedList
def initialize
@head = nil
@tail = nil
end
# Append element at the end
def append(value)
new_node = Node.new(value)
if @head.nil?
@head = new_node
@tail = new_node
else
new_node.prev_node = @tail
@tail.next_node = new_node
@tail = new_node
end
end
# Prepend element at the beginning
def prepend(value)
new_node = Node.new(value)
if @head.nil?
@head = new_node
@tail = new_node
else
new_node.next_node = @head
@head.prev_node = new_node
@head = new_node
end
end
# Delete a node with given value
def delete(value)
current = @head
while current
if current.value == value
if current.prev_node
current.prev_node.next_node = current.next_node
else
@head = current.next_node
end
if current.next_node
current.next_node.prev_node = current.prev_node
else
@tail = current.prev_node
end
end
current = current.next_node
end
end
# Return size of the list
def size
count = 0
current = @head
while current
count += 1
current = current.next_node
end
count
end
# Return node at given index
def at(index)
current = @head
index.times do
return nil unless current.next_node
current = current.next_node
end
current
end
end
# Client code
dll = DoublyLinkedList.new
dll.append("A")
dll.append("B")
dll.prepend("C")
puts "Size after adding three elements: #{dll.size}" # Output: 3
puts "Element at index 1: #{dll.at(1).value}" # Output: A
dll.delete("A")
puts "Size after deleting an element: #{dll.size}" # Output: 2
Output:
Size after adding three elements: 3 Element at index 1: A Size after deleting an element: 2
Explanation:
1. The Node class represents each element in the doubly linked list. It has attributes for value, next_node (pointer to the next node), and prev_node (pointer to the previous node).
2. The DoublyLinkedList class initializes with both head and tail nodes set to nil.
3. The append method adds a node to the end. If the list is empty, the new node becomes both the head and tail. Otherwise, it is linked to the previous tail and then becomes the new tail.
4. The prepend method works similarly but adds the new node at the start.
5. The delete method iterates through the list searching for a node with a matching value. Once found, it adjusts the pointers of the neighboring nodes to exclude the found node, effectively deleting it.
6. The size method iterates through all nodes, counting them.
7. The at method traverses the list to a specified index and returns the node found there.
Comments
Post a Comment