Linked List in Java

Understanding Linked List in Java

A linked list in Java is a linear data structure that we can use in Java Programming Language for storing a large amount of data with ease. The data stored in Linked List is not in a contiguous manner, but each data is stored at a different location, which can be accessed according to one’s need. Linked List is a preferred data structure over arrays, as inserting and deleting data in a linked list is easier than in an array.

Linked List

How to make a Linked List in Java

A linked list is a linear data structure that is made up of several nodes, which is further divided into two parts-:

  1. Node – This part stores the data.
  2. Link – This part stores the address of the memory location, where the next data of the list is stored.
Linked List in Java
// Node Class
class Node{
    int data;
    Node next;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
    }
}

Types of Linked Lists

There are many variations but below are the most important ones –

  • Singly Linked List
  • Doubly Linked List
  • Circular Linked List

Singly Linked List

It is the most basic linked list, which is made up of several nodes, which can further be divided into two parts

  • data
  • next

Each node is connected to one another as the next value for each node holds the address to the next node in the sequence.

The first node is called as head and the last node is called as tail, where the last node’s next value is null.

Linked List Singly

Doubly Linked List

This is a successor of a normal linked list. Nodes of a double linked list have three parts – 

  • Data – Data / Value held
  • Next – Reference Address to the previous node
  • Next – Reference Address to next node

The main advantage is we can traverse in any direction forwards and backwards.

Doubly Linked List

Circular Linked List

It is very similar to Singly Linked List with one change that rather than the last node pointing to null. It has the address to the first (head) node.

Which makes it circular in Nature, it is used in OS to implement round robin scheduling algorithms too.

Insertion and Deletion in Linked List in Java

import java.lang.*;

class LinkedList {
    Node head;
    // not using parameterized constructor would by default
    // force head instance to become null
    // Node head = null;  // can also do this, but not required

    // Node Class
    class Node{
        int data;
        Node next;

        Node(int x) // parameterized constructor
        {
            data = x;
            next = null;
        }
    }
    public Node insert(int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);
        // assigning this newNode's next as current head node
        newNode.next = head;

        // re-assigning head to this newNode
        head = newNode;

        return head;
    }


    public void display()
    {
        Node node = head;
        //as linked list will end when Node reaches Null
        while(node!=null)
        {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }

    public void delete()
    {
        if (head == null){
            System.out.println("List is empty, not possible to delete");
            return;
        }

        System.out.println("Deleted: " + head.data);
        // move head to next node
        head = head.next;
    }


    public static void main(String args[])
    {
        LinkedList ll = new LinkedList();

        ll.insert(6);
        ll.insert(5);
        ll.insert(3);
        ll.insert(4);
        ll.insert(2);
        ll.insert(1);

        ll.display();

        ll.delete();
        ll.delete();

        ll.display();
    }
}

Output

1 2 4 3 5 6 
Deleted: 1
Deleted: 2
4 3 5 6 
import java.lang.*;

// Node Class
class Node {
    int data;
    Node next;

    Node(int x) // parameterized constructor
    {
        data = x;
        next = null;
    }
}

class Main
{
    static Node insertStart(Node head, int data)
    {
        // Creating newNode memory & assigning data value
        Node newNode = new Node(data);

        // assigning this newNode's next as current head node
        newNode.next = head;
        // re-assigning head to this newNode
        head = newNode;

        return head;
    }

    public static Node delete(Node head)
    {
        if (head == null){
            System.out.println("List is empty, not possible to delete");
            return head;
        }

        System.out.println("Deleted: " + head.data);
        // move head to next node
        head = head.next;

        return head;
    }

    static void display(Node node) {

        //as linked list will end when Node is Null
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println("");
    }

    public static void main(String args[])
    {
        Node head = null;
        head = insertStart(head,6);
        head = insertStart(head,5);
        head = insertStart(head,4);
        head = insertStart(head,3);
        head = insertStart(head,2);
        head = insertStart(head,1);

        display(head);

        head = delete(head);
        head = delete(head);

        display(head);


    }
}

Output

1 2 3 4 5 6 
Deleted: 1
Deleted: 2
3 4 5 6 

Linked List vs Array

Linked List

  • Operation like insertion and deletion are easier.
  • Data is stored in a continuous manner
  • No need for pre-allocating the size of the list
  • Memory loss is comparatively low

Array

  • Operation like searching and traversing are easier.
  • Data is stored in a contiguous manner.
  • User need to define the size before inserting the data.
  • Memory loss is comparatively high

Linked List as a part of Collection

There are various different frameworks in Java which we can use for storing and operating efficiently on our data. Such is a framework known as Collection framework in Java. In this framework there are various different classes and interfaces are present using which we can code Linked List in Java in a very easy manner as it has a pre-defined class LinkedList stored in it, which has functions like

  • add()
  • delete()
  • search()
  • reverse(), etc

which we can use for operating on a linked list.

Some of the pre-defined function of LinkedList class

Method nameMethod Description
void addFirst(E e)This method inserts an element at the beginning of the list
void addLast(E e)This method inserts an element at the end of the list
void add(int index, E element)This method inserts an element at the specific position of the list
void clear()It is used to clear all the elements from the list
boolean contains(Object o)This method returns true if the specific element is present in the list, otherwise return false
element()This element let us view the first element of the list
getLast ()This method gives us the last element of the list
lastIndexOf(Object o)This method returns the index of the last occurrence of a specified element
size()This method returns the size of the list
toArray()This method converts the list into an array

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java