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. = nil) @data = data @next_node = next_node end end : , : ( , class Node attr_accessor data next_node def initialize data next_node 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. = nil end # to add a node on the beginning def add(data) new_node = Node.new(data) new_node.next_node = @head @head = new_node end @ class LinkedList def initialize head Function 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) @head.nil? @head = new_node tail = @head (tail.next_node != nil) tail = tail.next_node end tail.next_node = new_node end end if else while 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 = node = @head node counter ===index node end counter+= node = node.next_node end node end 0 while if return 1 return 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) @head.nil? @head = Node.new(data) end index === @head = Node.new(data,@head) prev = get_at(index – ) new_node = Node.new(data) new_node.next_node = prev.next_node prev.next_node= new_node end end if if 0 else 1 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.
