509 reads

WTF are Linked Lists?

by Danilo ZagarcaninJanuary 13th, 2020

Too Long; Didn't Read

Linked lists are different from arrays in their structure. The number of nodes in a linked list is not fixed and can grow and shrink on demand. Every element of the list is represented by an object with two fields. This object is called a node and first field of the node we often call head while the second field is pointing to the next node. To add a node as the last element, you changed your mind and you want to go on the end of the row, you must pass all people one by one till you arrive till the end. To insert node on the desired position we can make things easier and write the helper method that will return the index of the linked list.

Company Mentioned

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.

Linked lists are different from arrays in their structure. Arrays are an index-based data structure where each element is associated with an index. On the other hand, Linked list relies on references where each node consists of the data and the references to the previous and next node. Every element of the list is represented by an object with two fields.

This object is called a node and first field of the node we often call head while the second field is pointing to the next node. The last node has a
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.

If the head is nil then it means the list is empty. I will represent now class which is used for storing data, Node class will have two attributes data and next_node.

class Node 
  attr_accessor :data, :next_node 
      def initialize(data, next_node = nil) 
             @data = data
             @next_node = next_node 
      end
end

Here we initialized value and we set next_node to default which is nil,
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.

After this we need to make the class that will help us to make basic list operations, those operations are traversing, inserting and deleting elements from the list.For this tutorial, I will just show how to add a node at the beginning of the list, how to add a node on the end of the list and how to insert node on the desired position. Let's dive in and start writing class for a linked list, first we will start with function for adding a node in the first position of the list.

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?

Imagine you are in the bank, and guy is arguing with workers, you are in hurry and nervous and you just want to be in front of him, imagine that that guy is the head, to stand before him you need to push him, imagine every other new guy/girl that arrives is nervous and wants to be first in the row as you, like that every next guy/girl who comes will be the first one in the row and guy who was first in the row now is last and behind him is nobody, row ends, nil. We initialized new node, for now, we don't have anything in the list, head is nil but even if we have, every added node comes before the first node that is in the list, so we initialize new node and that node next will point to the value that is in the head, it means to put value of head at second position, and in head comes new node. To add a node as the last element, you changed your mind and you want to go on the end of the row, you must pass all people one by one till you arrive till the end of a row, you now that you are on the end if nobody Is behind you.

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

Here we start similar as in function before, we initialized (new_node), and in case that linked list is empty, the head is nil we will set new value instead of nil. If not we must traverse through nodes until it points to the nil if node points to nil it means it's the last node.

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.

To insert node on the desired position we can make things easier and write the helper method that will return the index of the element of the linked list. That method will be in this example like a worker who tells who is standing third in the row. Who is the third? Michael is third. This method looks like this :

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

If we call this method we will get the desired element on provided
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

First if statement will add node if list is empty, I already explained it,
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).

Now I can add node where ever I want, hope you understand this and my explanation helped you understand adding elements in linked lists, for this tutorial this will be enough.