For this short tutorial, my examples would be written with the Ruby programming language. I will try to demonstrate adding nodes in the linked list on the way I understood it, I am still learning and practicing data structures and linked lists were something on what I spent some time to understand it.
reference to nil and we can call it tail. The number of nodes in a list is not fixed and can grow and shrink on demand. The content of the list must be data of the same type.
class Node
attr_accessor :data, :next_node
def initialize(data, next_node = nil)
@data = data
@next_node = next_node
end
end
whenever we make an instance of the class we need to make it with argument value, so we can have that value and pointer to the next node.
class LinkedList
def initialize
@head = nil
end
# Function to add a node on the beginning
def add(data)
new_node = Node.new(data)
new_node.next_node = @head
@head = new_node
end
What did we do?
def add_last(data)
new_node = Node.new(data)
if @head.nil?
@head = new_node
else
tail = @head
while(tail.next_node != nil)
tail = tail.next_node
end
tail.next_node = new_node
end
end
Somebody is in a hurry he asked first three people to give him there spot in the row, the third person offered their spot, he/she is standing now on that spot where the third person was standing, the third person is the previous person that was standing there, he/she is now next of that person.
def get_at(index)
counter = 0
node = @head
while node
if counter ===index
return node
end
counter+=1
node = node.next_node
end
return node
end
index, it's easy to understand, we made counter initialized on zero,
and while loop which will traverse throw elements until counter
becomes equal to desired index position, and node becomes nil, when
condition is fulfilled loop stops, then method returns node. After
this, we can proceed with writing function to insert a node in the
desired position.
def insert_at(data, index)
if @head.nil?
@head = Node.new(data)
end
if index === 0
@head = Node.new(data,@head)
else
prev = get_at(index – 1)
new_node = Node.new(data)
new_node.next_node = prev.next_node
prev.next_node= new_node
end
end
second if statement will work if we have only one node in the list,
it will add new data and that data will point to the head, else, to
add node in place of another node we initialize (new_node), new node
next needs to point to the next node of previous one, with that we
can move node that was in that place in front of new node and this
new node we need to put on that position, previous next node
(prev.next_node = new_node).