double list Algorithm
The double list algorithm, also known as the doubly-linked list data structure, is an advanced version of the standard linked list. This data structure consists of a collection of nodes, where each node contains a data element and two pointers - one pointing to the previous node and the other pointing to the next node in the list. The double list algorithm allows for efficient traversal in both directions (forward and backward) through the list, as well as easy insertion and deletion of elements at any position within the list.
In a doubly-linked list, the first node's previous pointer and the last node's next pointer are set to null, indicating the beginning and end of the list. The primary advantage of the double list algorithm over a standard singly-linked list is that it enables more efficient manipulation of elements within the list. Since each node maintains a reference to both its adjacent nodes, operations such as insertions, deletions, and traversal can be performed in constant time, regardless of the size of the list. However, this increased functionality comes at the cost of increased complexity and memory overhead, as each node now requires two pointers instead of one.
# Define a node in the list
class Node
attr_accessor :value, :next, :prev
def initialize(value)
@value = value
@next = nil
@prev = nil
end
end
# A Class for double linked lists (each element links to the next one, and to the previous one)
class DoubleList
attr_accessor :head, :tail
def initialize()
@head = nil
@tail = nil
end
def insert_tail(value)
new_node = Node.new(value)
if (@head == nil)
@head = new_node
@tail = new_node
else
@tail.next = new_node
new_node.prev = @tail
@tail = new_node
end
end
def insert_head(value)
new_node = Node.new(value)
if (@head == nil)
@head = new_node
@tail = new_node
else
new_node.next = @head
@head.prev = new_node
@head = new_node
end
end
def delete_tail()
if (@tail != nil)
@tail = @tail.prev
if (@tail != nil)
@tail.next = nil
end
end
end
def delete_head()
if (@head != nil)
@head = @head.next
if (@head != nil)
@head.prev = nil
end
end
end
def print_list()
print "["
if (@head != nil)
printNode = @head
while (printNode != nil)
print "#{printNode.value}"
if (printNode != @tail)
print ", "
end
printNode = printNode.next
end
end
print "]"
STDOUT.flush
end
def is_empty()
return (@head==nil)
end
end
