Linked List (2nd Part)

In our last article, we talked about the Linked List and how its basic version is created. In this article, we are going to talk about the common methods of it.

If you did not read the first tutorial, I suggest you to take a look at it:

So, if we are ready, let’s get started:

Creating methods for Linked List

To use the Linked List, we will create some methods for insertion, deletion, etc. operations.

Firstly let’s have a look at the insertion methods:

Insertion methods

We can insert a node to the beginning, end, or middle of the Linked List. Let’s see them one-by-one:

Inserting Element At The Beginning

Let’s say we have a Linked List like in the image below and we want to insert a new node to the beginning.

To do that, we have these steps:

  • Update new node’s next reference to the head of the Linked List
  • Update head’s next reference to point to the new node

Our final result should look like this:

With this, we have inserted a new node at the beginning of the Linked List. Now, let’s see these steps in code:

  • Initially, we create a new node with the given value
  • Then we check if the head is null or not:
  1. If the head is null → it means the Linked List is empty. In this case, we set the head and tail pointers to point to the new node
  2. If the head is not null → it means the Linked List is not empty, so we continue to the else statement and do the following steps:
  • Firstly, we assign the new node’s next reference to the head of the Linked List
  • Then we update our head pointer to point to the new node
  • At the end, we increase the Size

Inserting Element At The End

To insert a node at the end, we do these steps:

  • Firstly, we set the tail’s next reference to the new node
  • Secondly, we update the tail to point to the new node
  • Then, we set the tail’s next reference to the null
  • At the end, we increase the Size

After these steps, Linked List will look like as below:

To implement it, let’s see the code:

  • Initially, as we did before, we create a new node with the given value
  • Then we check if the head is null or not:
  1. If the head is null → it means the Linked List is empty. In this case, we set the head and tail pointers to point to the new node
  2. If the head is not null → it means the Linked List is not empty, so we continue to the else statement and do the following steps:
  • In the else statement, we set the tail’s next reference to the new node
  • Then, we update tail to point to the new node and set its next reference to the null (because it is the last element).
  • At the end, we increase the Size

Inserting a Node After a Specific Node

We have learnt how to insert a node at the beginning and end of the Linked List. Now let’s learn how to insert a node at the middle.

To do that:

  • Firstly, we get the node after which we want to add a new node. We call that node tempNode
  • Secondly, we store its next reference to use later
  • Then we set tempNode’s next reference to the new node
  • After that, we set the new node’s next reference to the next node which we have stored before
  • At the end, as before we increase the Size.

These may seem complicated, but do not worry you will understand them when you see in code.

After these implementations, the code has to be like this:

To clarify the above steps, let’s see them in code:

Note: Unlike the other two methods, we have a position parameter which we will use to find the index for inserting a node.

  • Firstly, as always, we check if the Linked List is null or not. If it is null, we print the message about it
  • If it is not null, we continue to the else statement
  • Then we create a temporary node and assign the head reference to it
  • We create an index variable to store our current index
  • Then we traverse through the Linked List. In each step, we assign tempNode to its next node and increase the index variable by one.
  • When this loop is finished, the tempNode will be equal to the node whose index is equal to the position (one-based index system)
  • After the loop, we create a new nextNode variable to store the tempNode's next reference to use later
  • Then, we set tempNode's next reference to the new node
  • After that, we set the new node’s next reference to the nextNode which we stored before
  • At the end, we increase the Size

Deletion Methods

Till now, we have learnt how we insert a node to the Linked List, now let’s see how we are deleting nodes from the Linked List.

Delete the First Element

To delete an element from the beginning of the Linked List, we just need to set head to its next reference:

To implement it, we write:

  • Firstly, we check if the Linked List is null or not. If it is null, we print the message about it
  • If it is not null, we continue to the else statement
  • Then we check if head and tail are equal. If they are equal, it means we have only 1 element in the Linked List, so we set both of them to null.
  • If they are not equal, that is, we have more than 1 element, we simply set head to head's next reference. The previous head is being collected by the garbage collector
  • At the end, we decrease the Size

Delete the Last Element

To delete the last element, we need to traverse through the Linked List till we reach the node which is before the tail node.

When we reach that node, we set its next reference to null, so the tail node is being collected by the garbage collector

Lastly, we update the tail node.

Let’s understand the logic by seeing them in practice:

  • Here, firstly, we check if the head is null or not, if it is null, we print a message
  • If it is not null, then in the else statement, we check if head and tail are the same, meaning we have only 1 element. In that case, we set both of them to null
  • If we have more than 1 element, then we traverse through the Linked List till we reach the node which is before the last node. In our case, that node is tempNode
  • After the while loop, we set tempNode's next reference to the null
  • Then, we update the tail to point to the last node
  • At the end, we decrease the Size

Delete The Node at the Specific Location

To remove the node from the middle of the Linked List, the method will have one parameter which is the position.

For example, If there are 5 elements in the Linked List, and we want to remove the node which is in the position = 2. In this case, it will through the Linked List and find the 2nd node. Then it will remove the node which is after the 2nd node. (3rd node). See the image below to understand it

Let’s see how we are implementing it:

  • Here, again we check if the head is null or not
  • Then in the else statement, we check if there is only 1 element, if so, we set head and tail to the null
  • If we have more than one element, then we create two new variables, one for an index, another one for a temporary node
  • In the while loop, we traverse through the list till we reach the node whose index (one-based index system) is equal to the position parameter
  • After finding that element, we store its next reference
  • Then we set tempNode's next reference to the stored value’s next reference. So, the node which was in middle is being collected by the garbage collector
  • At the end, we decrease the Size

Deleting the Entire Linked List

If we look at the Deletion methods for deleting first, last and middle node of the Linked List, we will see that they are a bit complicated.
Unlike them, deleting entire Linked List is very simple so that we only set head and tail's next reference to the null. With this, all of the nodes are being collected by the garbage collector.

Let’s see the code:

  • Again, we check for the head
  • Then, if we have more than one element, we set both head and tail to null so that all of the nodes are being collected by the garbage collector
  • At the end we set the Size to 0

Getting the size of the Linked List

As we know, we created a Size property with get and private set. Now, we will use that property to get the size. See the example:

First by writing llist.Size we get Linked List’s size and assign it to the linkedListSize variable. The next line is responsible for printing the size to the console.

Printing the Linked List

To print a Linked List, we need to traverse all the nodes and in each step, print their value:

  • If there is no element in the Linked List, we print a message says that "There is no element to print", If we have an element, we continue to the else statement
  • Then we traverse through all the nodes and prints their data

Summary

If you read this conclusion, this means that you have read all the blog and learnt a lot of things about Linked List.

To summarize, in the first blog, we have learnt how to create a basic Linked List and what is the logic behind it. In this blog, we have learnt how to make methods to use the Linked list.

I hope this was helpful and you have learnt the Linked List. Thanks you for reading and if you have any question, feel free to ask in the comment section.

If you want, you can get all the codes from the article in this link:

The Editor of the Star Gazers

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store