single list Algorithm
The single list algorithm is a simple and efficient technique used in computer programming and data manipulation for organizing and sorting elements within a list. This algorithm operates on a single list, meaning that it does not require any additional data structures or memory allocation for its operation. The primary advantage of the single list algorithm is its simplicity, as it can be easily implemented and adapted to various applications, such as sorting, searching, or merging lists. Furthermore, its in-place nature ensures that the algorithm is memory-efficient, making it ideal for use in situations with limited memory resources.
In the context of sorting, the single list algorithm iteratively scans through the list, comparing adjacent elements and swapping them if they are out of order. This process is repeated until the entire list is sorted, which may require multiple passes through the list. While this approach may not be the most efficient sorting algorithm in terms of time complexity, its ease of implementation and low memory overhead make it suitable for small-scale applications or as a starting point for learning about more advanced sorting techniques. Other applications of the single list algorithm include searching for specific elements, merging two or more sorted lists, and removing duplicates from a list.
# Define a node in the list
class Node
attr_accessor :value, :next
def initialize(value)
@value = value
@next = nil
end
end
# A Class for single linked lists (each element links to the next one, but not to the previous one)
class SingleList
attr_accessor :head
def initialize()
@head = nil
end
def insert_tail(value)
newNode = Node.new(value)
if (@head == nil)
@head = newNode
else
tempNode = @head
while (tempNode.next != nil)
tempNode = tempNode.next
end
tempNode.next = newNode
end
end
def insert_head(value)
newNode = Node.new(value)
if (@head == nil)
@head = newNode
else
newNode.next = @head
@head = newNode
end
end
def print_list()
print "["
if (@head != nil)
printNode = @head
while (printNode != nil)
print "#{printNode.value}"
if (printNode.next != nil)
print ", "
end
printNode = printNode.next
end
end
print "]"
STDOUT.flush
end
def delete_head
if (@head != nil) && (@head.next != nil)
newHead = @head.next
@head = newHead
elsif (@head != nil) && (@head.next == nil)
@head = nil
end
end
def delete_tail
if (@head != nil)
tempNode = @head
while (tempNode.next.next != nil)
tempNode = tempNode.next
end
tempNode.next = nil
end
end
def isEmpty()
return (@head==nil)
end
end
