class SinglyLinkedList
attr_reader :head
class SinglyLinkedList
attr_reader :head
Create a Node
struture to represent
an individual node in the linked list.
There is a data
field to hold any data
and a next
field that points to the
next item in the list.
class Node
attr_accessor :data, :next
def initialize(data)
@data = data
end
end
Initialize @head
as nil when creating the
Singly Linked List. This may not really be
required but I was just be explicit for clarity.
def initialize
@head = nil
end
If the head of the linked list is nil
the list is empty.
def is_empty?
@head.nil?
end
This removes a node from the linked list
by removing the node in question from chain,
so to speak. Basically, while iterating threw
the list it keeps track of the previous node
then when it finds the node it assigns
node.next
to prev.next
, affectively skipping
the found node.
O( n )
def remove!(node_to_remove)
node = @head
prev = nil
until node.next.nil?
if node == node_to_remove
prev.next = node.next
return
else
prev = node
end
node = node.next
end
end
This method modifies the linked list
to be unique with the help of a buffer.
Nodes are added to element_list
and it
is checked each iteration to see if the
current node already exists in it. If it
does, it set the previous node’s next link
to equal the current node’s next (removing
it from the linked list.
O( n )
def unique!
node = @head
prev = nil
element_list = []
until node.nil?
if element_list.include? node.data
prev.next = node.next
else
element_list << node.data
prev = node
end
node = node.next
end
end
To insert a new node we simply
pass in the data
and create a
new node using the Node
class.
The we just move @head
to be the
next
link and then reassign this
new node to @head
.
O( 1 )
def insert(data)
new_node = Node.new(data)
new_node.next = @head
@head = new_node
new_node
end
This is an iterative approach to reversing the linked list. There are a few things going on here:-
nil
@head
to be prev (which is the last node)
.O( n )
def reverse_using_iteration
node = @head
prev = nil
until node.nil?
next_node = node.next
node.next = prev
prev = node
node = next_node
end
@head = prev
end
def reverse_using_recursion(node=@head)
if node.next.nil?
@head = node
return
end
reverse_using_recursion(node.next)
node.next.next = node
node.next = nil
end
This is a simple print function that
iterates the linked list and allows you
to pass a block in to do what you want
with a given node.
Like so, print { |n| puts n }
O( n )
def print(&block)
node = @head
until node.nil?
node = node.next
yield node
end
end
end