What is a linked list?

A linked list is a data structure that can be considered as a list of boxes, where each box contains a value/element and has a reference or link pointing to the next element. These elements are referred to as "nodes".

The first element of the list is called the head.
The last element is called the tail.
Linked lists are often used in computer programming because they are relatively easy to insert and delete elements from, and they do not require the memory overhead that an array does.

Types of linked lists

Singly Linked List

A singly linked list is a data structure that consists of a sequence of elements, called nodes, where each node contains a value and a reference (or "next pointer") to the next node in the sequence.
The first node in the list is referred to as the head and contains a reference to the first element in the list.
The last node in the list is referred to as the tail and points to a null value, indicating the end of the list.
The nodes in a singly linked list only know their own value and to whom it is pointing (next pointer), they can only be traversed in one direction, from head to tail.

class Node{
int value;
Node next;
}

The basic structure of a linked list

public class LinkedList{
    int head;
    int tail;
    int size ;

    public LinkedList()
    {
        this.size=0;
    }
    private class Node{
        private int value;
        private Node next;

        public Node(int value)
        {
            this.value = value;
        }
        public Node(int value, Node next)
        {
            this.value = value;
            this.next = next;
        }
    }
}

public class Main{
    public static void main(String args[])
    {
        LinkedList list = new LinkedList();
    }
}

Display Singly linked list

To display a singly linked list we create a temporary node whose pointer points toward the current head (first element)

It prints the first element and then moves ahead.

 public void display(){
        Node temp = head;

        while(temp!=null){
            System.out.print(temp.value + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }

Insertion in a linked list

1-Insertion at the very first position:

There can be two conditions-

List is filled
List is empty

To insert an element in a singly linked list, first, we have to create a new node with the given value.

The new node's next pointer should point towards the current head (first element) of the list.

Then, the new node should be assigned as the new head of the list.

If the list is empty, it implies that the tail is equal to null, so both the head and tail should be assigned the new node's value. This way, the new node becomes the first and the last element in the list.


    public void InsertAtFirst(int val)
    {
        Node node = new Node(val);
        node.next = head;
        head = node;

        if(tail == null)
        {
            tail = head;
        }
        size += 1;
   }

2-Insertion at the last position

To insert a new node at the last position of a linked list, you would add the new node to the end of the list by setting the next pointer of the last node to the new node.
Finally, you would update the tail pointer to point to the new node, which is now the last node in the list.
If the list is empty then call the InsertAtFirst() method, that we created earlier.


    public void InsertAtLast(int val)
    {
        if(tail==null)
        {
            InsertFirst(val);
            return;
        }

        Node node = new Node(val);
        tail.next = node;
        tail = node;
        size++;

    }

Points to note:

Without the tail variable, the process of inserting a new node at the last position of a linked list would require traversing the entire list to find the last node. This would have a time complexity of O(n), where n is the number of nodes in the list.

However, with the use of a tail variable, which always points to the last node of the list, the process of inserting a new node at the last position becomes a constant time operation, O(1).

This is because the tail variable allows us to directly access the last node without having to traverse the entire list, which can save time in large lists.

3-Insertion at the required index(anywhere in the list)

Create a new node that contains the element you want to insert.
Traverse the list to find the position where you want to insert the new node.
Update the next pointer of the previous node to point to the new node.

Update the next pointer of the new node to point to the node that was originally at the insertion position.


     public void InsertAtIndex(int val,int index)      //insertion at any index
      {
          if(index == 0)
          {
              InsertFirst(val);
              return;
          }
          if(index == size)
          {
              InsertLast(val);
          return; 
          }

          Node temp = head;
          for(int i=1;i<index;i++)
          {
              temp = temp.next;

          }
          Node node = new Node(val,temp.next);
          temp.next = node;
          size++;

      }

Deletion in a linked list

1-Deletion at the very first position:

To delete an element from the first position in a singly linked list, the head pointer should be moved to the next node and the node at the current head position will be overridden.

If the list contains only one element, the head pointer will point toward null so tail pointers should also be set to null after the deletion.

   public int DeleteFirst()
     {
      int val = head.value;
      head = head.next;
      if(head == null)
      {
          tail = null;
          size--;
      }
      return val;
     }

2-Deletion at the last position:

To delete an element from the last position in a singly linked list, you can traverse the list until you reach the second to last node.
Once you reach that node, you can set its next pointer to null, effectively removing the last node from the list.
If the list only contains one element, the head and tail pointers should both be set to null after the deletion.

public int DeleteLast()
   {
    if(size<=1)
    {
        return DeleteFirst();
    }
    int val = tail.value;
    Node secondLast = get(size-2);

    tail = secondLast;
    tail.next = null;
    size--;
    return val;
   }

   public Node get(int index){

    Node node = head;
    for(int i=0;i<index;i++)
    {
        node = node.next;
    }
    return node;
 }

3-Deletion from anywhere in the list:

To delete an element from anywhere in a singly linked list, you can traverse the list until you reach the node that comes before the one you want to delete.

Once you reach that node, you can set its next pointer to the node that comes after the one you want to delete, effectively removing the desired node from the list.

    public void delete(int index) {
        if (index == 0) {
            head = head.next;
            size--;
            return;
        }
        if (index == size - 1) {
            Node secondLast = get(size - 2);
            secondLast.next = null;
            tail = secondLast;
            size--;
            return;
        }
        Node prevNode = get(index - 1);
        Node currNode = prevNode.next;
        prevNode.next = currNode.next;
        size--;
    }

Linked List : Connecting the building blocks of Data Structures

Table of contents