LinkedList Implementation using Java

April 24, 2020

594

LinkedList is a Linear Data Structure. It stores the data in the form of Nodes.

Unlike Array, LinkedList elements are not stored in the Contiguous location. each node stored in the Memory in different locations and first Node points the next node.

Types of LinkedList:

The LinkedList categorised into 3 types:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List

Node:

A node consists of two parts:

1.Data Part: That stores the Data/value.

2.Pointer Node: That points to the Next Node otherwise NULL.

Single LinkedList Node Representation

Advantages of Using LinkedList:

Linked List is Dynamic in Size. The memory location is allocated dynamically when each node is created. We can extend or shrink the size of LinkedList at the runtime as per requirement. so, No there is no memory wastage in Linked lIst, unlike Array whose size define once and cannot be extended or shrunk down when required.
Insertion and deletion involve only to manipulate the pointers to the previous Node or Next Node. Thus Insertion and deletion take O(1)in Linked List.

Disadvantages of using LinkedList:

Extra memory space is required with each element to store the address of the next Node in the Linked List.
Random Access(Random Access Interface) is not allowed in LinkedList because the elements(Nodes) in LinkedList are not stored in a contiguous location, unlike array. For accessing any particular node in Linked List we first need to access the previous node because that node stores the address of that node we want to access.

Singly Linked List:

This is the most commonly used type of Linked List. In Single Linked List each node has only one pointer that points to the next node and stores the address of the next node. Single Linked List only travels in one direction(Uni-directional). To access the last element of the Linked List we need to traverse the whole list.

Single Linked List Representation

Node Representation in Java:

public class LinkedList {

    // Node class creates The Linked List Node
    static class Node{
        int data;
        Node next;

        //Constructor creates New Node and store value into data part and
        // set pointer as Null in starting.
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

Linked List implementation in Java:

In this implementation of Linked List using Java, I am using Simple Java class LinkedList .javathat contains the required operation Implementation to insert and display the Linked List.

LinkedList.java

public class LinkedList {

    // Node class creates The Linked List Node
    static class Node{
        int data;
        Node next;

        //Constructor creates New Node and store value into data part and
        // set pointer as Null in starting.
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }


    public Node insert(Node head, int ele){
        Node temp = head;

        if (temp == null){
            head = new Node(ele);
        }else{
            while(temp.next!=null){
                temp = temp.next;
            }
            temp.next = new Node(ele);
        }

        return head;
    }

    public void display(Node head){
        Node temp = head;

        if (temp == null){
            System.out.println("Linked List is Empty.");
        }else{
            while(temp.next!=null){
                System.out.print(String.format("%d--->",temp.data));
                temp = temp.next;
            }
            System.out.print(String.format("%d--->NULL",temp.data));
        }
        System.out.println();
    }

}

LinkedListImplementation.java

import java.util.Scanner;

public class LinkedListImplementation {

    public static void main(String[] args) {

        Scanner scanner  = new Scanner(System.in);
        System.out.println("Enter the length of Linked List : ");

        int n = scanner.nextInt();

        System.out.println("=================================");

        LinkedList list = new LinkedList();
        LinkedList.Node head = null;

        System.out.println("Enter the LinkedList Elements : ");

        for(int i=0;i<n;i++){
            int ele = scanner.nextInt();
            head = list.insert(head,ele);
        }

        System.out.println("=================================");

        System.out.println("Linked list after Insertion Operation : ");

        list.display(head);

        System.out.println("=================================");

    }
}

Output 1:

Enter the length of Linked List : 
5
=================================
Enter the LinkedList Elements : 
1
2
3
4
5
=================================
Linked list after Insertion Operation : 
1--->2--->3--->4--->5--->NULL
=================================

Output 2:

Enter the length of Linked List : 
0
=================================
Enter the LinkedList Elements : 
=================================
Linked list after Insertion Operation : 
Linked List is Empty.

=================================

Hope you like this post.

If you have any doubt please feel free to comment below.

Learn Stack Implementation using LinkedList

You may also learn these to build the Knowledge: