LinkedList -A treasure hunt towards explanation. (Java)

11 min readFeb 4, 2018

Hi everyone, Dhruvam here. Today we’re going to cover the in-depth knowledge of Singly LinkedList in java. There is a fully fledged Java API for linkedList data structures for using it. But today we’ll see what goes beyond some of the the methods defined in Java API.
We’ll cover the details of a Singly LinkedList in a very intuitive way while also pointing out the comparison points between a Linkedlist, Array and an ArrayList.
Java API has built a Doubly LinkedList as a data structure. After learning Singly LinkedList, it would not be too hard for you to develop the Doubly LinkedList. I have provided the code for Doubly Circular LinkedList too.

If you directly want to jump to the code, click here.

CONTENT:

Basics about LinkedLists.
Some History.
A treasure hunt analogy for LinkedList explanation.
Code and it’s Explanation.
Types of Linked List.
Comparison between Array, ArrayList and LinkedList.

Prerequisites:

Basic knowledge of Java. And that’s it.

1. Basics. Basics. Basics

A Linkedlist is a very unique data structure. I had so much confusion built around it earlier. Time Complexities, Root, Nodes, Abstract Data Structures, pointers, it all had me so confused that I always ran away so I decided to take up this data structure as an article.

Definition: an ordered set of data elements, each containing a link to its successor (and sometimes its predecessor).

2. Let’s dig up some history.

An array is a static data structure, meaning, while creating an array, it has to be explicitly mentioned how many spaces or bytes the array will take. Example: For storing 7 elements in an integer array, the compiler will first find 7 places in memory (if they are available) and then create it. For starters, you should know that array stores elements in a contiguous manner, meaning, the array we created earlier for 7 integers, will need to find 7 memory spaces together. Unlike an array, LinkedList is a data structure that does not require contiguous places to store it’s elements. So we do not need to define the size of the LinkedList while creating it. This is why its is a dynamic data structure.

A LinkedList is all the same as an array but instead of storing just one element, a LinkedList stores 2 different items for each element. One item is the element itself and the other is link to the next element. Because linked list is not contiguous, that is why a LinkedList cannot be referred using index.

In Java API of LinkedList, we can refer the items using index. This is made to make the LinkedList work much like an array.

3. A Treasure Hunt Game

Let’s draw an analogy here for the understanding of a LinkedList. In a treasure hunt game, we start from the first clue at the starting point and solve the clue to reach to the second point because the clue contain some information to reach there. The game continues by solving the clues until we reach the end of the game.

This is basically a LinkedList. The place where we start from is a Root in LinkedList Terminology. And there is some data and hint in the clue. So the clue is a Node. The data part of the clue is the info. The hint part of the clue is the link or next. You can name these parts whatever you want. All of this is LinkedList terminologies. Don’t get confused, stay with me.
For every clue there must be these information bits present. So in every node, there must be an info part and a link or next part present. A node is what makes up a linked list. Still with me? Okay good.
A root is just a pointer. And so is a link or next. And java has no pointers? It indeed has actually. This is the practice of pointers for you. But don’t worry, Java made it too easy for us by abstracting all of the pain for us.

4. CODE. (The treasure hunt is till on)

Let’s start the code by building the clues. I mean building Nodes.

private class Node<E> {
  ...
}

The node class is private here for some reason which we’ll cover later. We’ve taken the Node as a class because we want to have different methods and variables in the Node. The Angle brackets after Node Class, is the generic part stating that the Node class can store any type of data, be it integers, Strings, boolean, etc.

private class Node<E> { private E info;
 private Node<E> next;
 ...
}

Excuse the Yellow stain! It’s clue and not due!

What we’ve done now is we’ve defined a data part of the Clue or Node. It is of the type E. Whatever we make the Node Type to be, the info part will be of that type too. Also we’ve defined a link part of the clue or node, that is next. It is a pointer of type Node. It will be used to define the links.

private class Node<E> { private E info;
 private Node<E> next; public Node(E info) {
  super();
  this.info = info;
  this.next = null;
 }}

Next we’ve defined a constructor, which says it all. But still, it first initializes the Node with the Element which is info here. And the Next is defined as null which is just for the initialization purpose.

private class Node<E> { private E info;
 private Node<E> next; public Node(E info) {
  this.info = info;
  this.next = null;
 } /**
 * @return the info
 */
 public E getInfo() {
  return this.info;
 }
 
 /**
 * @param next the next to set
 */
 public void setNext(Node<E> next) {
  this.next = next;
 } /**
 * @return the next
 */
 public Node<E> getNext() {
  return this.next;
 }}

Now that’s too much, isn’t it? NO! These are just getters and setters for the Info and the Next part. Nothing else.

Let’s move onto adding a New Node in a LinkedList.

class SinglyLinkedList<E> {
 ...
 private class Node<E> {
  ...
 }
}

First let’s create a class named SinglyLinkedList or whatever name it pleases you. You see the angle brackets? Those defines the same thing. It states what type of data will the LinkedList store. Also the Node Class will be an inner class of this Class. That is why it was kept private.

Now let’s add a Node.

class SinglyLinkedList<E> { /* defining variables */
 private Node<E> root;
 private int count;
 private Node<E> last; /* constructor definition */
 public SinglyLinkedList() {
  root = null;
  last = null;
 } /* getting the length of the linked list */
 public int getCount() {
  return count;
 } /* add method */
 public boolean add(E info) {
  Node<E> node = new Node<E>(info);
  if (root == null) {
  root = node;
  last = node;
  count++;
  return true;
 }
 
  last.setNext(node);
  last = node;
  count++;
  return true;
 }  /*  Node Class commented out */
}

Now now! Don’t get blown away with too much! It’s easy.

First we declared a pointer to the first Element, then to the Last Element. And also a variable to keep track of the length of the list.
Then I created a constructor to initialize the LinkedList.
Then a getter method for the length of the LinkedList named getCount.
Lastly I added an add Method for adding a node. The parameter of the method is info, it is used to initialize the Node.

There are 3 cases for addition of a node into LinkedList.

At the beginning of the list.
At the end of the list
Somewhere between the list.

In the Add Method, we’ve taken 2 cases. One of which is the case if the Linked List is empty, we need to add the node at the start of the List, that is if root = null. It means that currently list is not pointing toward any node. So we made the root point toward the new Node. As there is just one node, we made the last pointer point to the new node as well. And we increased the count by 1.

Second case is if the list is not empty and we want to add a new node at the end of the list, we just need to do 3 things:

Set the last node’s next part to point toward the new Node.
Set the last pointer point toward the New Node. The 1st and the 2nd points are different if you read carefully what I wrote. Last is just a pointer. We need to set it to point to the new last node. And the 1st point stated that the old last node’s next part is to be linked to the new last node.
Increase the count by 1.

A diagrammatic Representation of Add operation:

Adding a node somewhere in between the linked list.

Whenever you want to add a node, you will have to delete one connection and build two more.

The LinkedList API allows to save the last node location to make the addition at the beginning and the end an O(1) operation. In the middle, the operation has a time complexity of O(n) if we include the searching operation too.

Now let’s remove a Node.

For removing a node, we need to know the node to delete and also the node previous to it.


public boolean remove(E info) {
 
 /* Initializing the variables */
 Node<E> tempNode = root;
 Node<E> previousNode = root;
 int pointerCount = 0;
  /* if the list is empty do nothing */
 if (root == null) {
  return false;
 } /* if the list contains just one element */
   else if ( count == 1) {
    if (tempNode.getInfo() == info) {
     root = null;
     last = null;
     count--;
     return true;
 } else {
   return false;
  }
 } /* finding the position of the element and the previous node */
   else {    int temp = 0;
    while (tempNode.getInfo() != (info) && temp < getCount()) {
    temp++;
    tempNode = tempNode.getNext();
    if (pointerCount%2 != 0) {
     previousNode = previousNode.getNext();
   }
   pointerCount++;
  }
 /* checking if the node contains the info or did we reached the end of the list */
 if (tempNode.getInfo() == info) {  /* if the node to be deleted is present at the beginning */
  if (tempNode == root) {
   
   root = root.getNext();
   count--;
   return true;
   } /* if the node to be deleted is present at the last */
     else if( tempNode == last) {
      last = previousNode;
     }
  
   previousNode.setNext(tempNode.getNext());
   count--;
   return true;
  } else {
     System.out.println("element not found!");
    }
 }
  return false;}

Now now! Don’t just blame me! I have made the code much easier to read with the comments.

Cases I’ve dealt with:

If the list is empty: Just return back.
If there is just one element, make the pointers root and last point to null. This is because, there is now no element left in the list. And also decrease the length by 1.
Then for the general case, deleting the element from the middle, we need to find the element to be deleted and the element before it. We’ve used the method of even — odd. For every odd move, We store the previous node.
Then we check if the node that we found is the node or did we just reached the end of the list.
Then we check if the node we found is at the beginning of the list. If so, we just set the root to point to the next Node.
Then we check if the node we need to delete is last node. If so, then we make the last pointer point to the previous node.
And if the node is in between, we need to set the previous node to point to the node after the node to be deleted.
Decrease the count!

Diagrammatic Representation of the Remove Operation:

Print a List.

public void printAll() {
 Node<E> tmpref = root;
 while (tmpref != null) {
  System.out.print("->" + tmpref.getInfo());
  tmpref = tmpref.getNext();
 }
 System.out.println();}

To print a list, we just need to take a temporary pointer and point it to the root pointer. Now just traverse the list until we reach the end. And while moving, print the elements of the list.

5. Different Types of LinkedList.

There are 4 different types of LinkedLists available.

Singly LinkedList.

2. Circular LinkedList.

3. Doubly LinkedList.

4. Circular Doubly LinkedList.

6. Comparison Between Arrays, ArrayLists and LinkedLists.

The final and last topic of this article is the comparison. The thing to note here is that the LinkedList and ArrayList both implements List interface. So they give almost the same performance. We are going to talk about the Doubly LinkedList.

The array is a final class whose documentation is hidden from us. It can be found in the java.lang.reflect.Array package.

Now that’s some hidden information, right?

Search Operation:

Array has a time complexity of O(1). As it is an index based data-structure and stores data in contiguous locations, it is not a time consuming process.
ArrayList has a time complexity of O(1) too. The same reason.
A linkedlist on the other hand has a time complexity of O(n). This is because it is a sequential list. Therefore searching has to start from the head (or from the end).

Nature:

Array is a static data structure. It means that we have to specify how much space the array will take while creating it.
ArrayList is a dynamic data structure. Meaning, we can create the space for new elements at run-time.
LinkedList is a dynamic data structure too.

Insertion:

Array insertion operation has a variable time complexity. In the best case performance, it is O(1) when the element is to be added at last. For the rest cases, it is O(n) when the element is to be added at the starting or in between. This is because while adding, all the elements have to be shifted by one place for a new element to be added.
ArrayList has the same time complexities as that of an array.
LinkedList insertion has an O(1) time complexity because only the pointers have to be changed. No need to shift all the other elements. (we do not include the search operation in addition or deletion operation)

Deletion:

Array deletion operation has a variable time complexity. In the best case performance, it is O(1) when the element is to be deleted at last. For the rest cases, it is O(n) when the element is to be deleted at the starting or in between. This is because while deleting, all the elements have to be shifted for a new element to be deleted too.
ArrayList has the same time complexities as that of an array.
LinkedList deletion has an O(1) time complexity because only the pointers have to be changed. No need to shift all the other elements.

Aaaaand we’re finally done with this article.