Linked List in Java

Introduction

A LinkedList in Java is a linear and fundamental data structure that stores the Java components. It offers Java users an efficient, flexible way to store and work with various Java elements.

Java LinkedList allows dynamic size adjustment as and when elements are subtracted or added. Here in this tutorial, you will learn what is LinkedList, its needs, its operation, demonstration, LinkedList in a data structure, and much more.

Overview

LinkedList is an element sequence where all the elements are kept safe in nodes. Along with the elements, each node has a reference point directed toward the next node. Read on to learn more about various linked list methods in Java, the insertion and deletion process in a LinkedList in Java, the creation of a LinkedList in Java, and so on.

Why do we need a LinkedList?

Linked lists are used because they have a range of advantages. They make better use of the memory from the viewpoint of allocation. The size for this list is also not pre-determined and thus allows easy addition and subtraction of elements from the list. Even for sorting algorithms LinkedLists are more efficient.

Creating a Linked List in Java

To create a linked list in Java, we must first define a class to represent the nodes of the list and implement methods to perform various operations on the list.

Let us understand linked lists with an example of creating a linked list.

We will have two classes: Node and LinkedList. The Node class will represent a single node in the linked list, storing an integer value and a reference to the next node. The LinkedList class will represent the linked list, maintaining a reference to the head node.

The LinkedList class will provide methods to insert nodes at the end of the list (insert method) and display the list's contents (display method).

We will then add the main method to create an instance of the LinkedList class and insert some elements into the list using the insert method. Finally, we display the contents of the list using the display method.

Here is the code:

class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}
class LinkedList {
    Node head;
    public LinkedList() {
        this.head = null;
    }
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}
public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.insert(40);
        list.display();
    }
}

Doubly Linked List

A doubly linked list is a type of linked list where all the nodes contain references to both the next and previous nodes, allowing for efficient traversal in both directions. In Java, you can implement a doubly linked list using a custom class representing the nodes and maintaining the necessary references.

Here is an example:

Code:

class Node {
    int data;
    Node prev;
    Node next;
    public Node(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}
class DoublyLinkedList {
    Node head;
    Node tail;
    public DoublyLinkedList() {
        this.head = null;
        this.tail = null;
    }
    // Methods for various operations on the doubly linked list go here
    public void addFirst(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }
    public void addLast(int data) {
        Node newNode = new Node(data);
        if (tail == null) {
            head = newNode;
            tail = newNode;
        } else {
            newNode.prev = tail;
            tail.next = newNode;
            tail = newNode;
        }
    }
    public void insertAfter(Node node, int data) {
        if (node == null) {
            return;
        }
        Node newNode = new Node(data);
        newNode.next = node.next;
        newNode.prev = node;
        if (node.next != null) {
            node.next.prev = newNode;
        }
        node.next = newNode;
        if (tail == node) {
            tail = newNode;
        }
    }
    public void remove(Node node) {
        if (node == null) {
            return;
        }
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }
    public void displayForward() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
    public void displayBackward() {
        Node current = tail;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.prev;
        }
        System.out.println();
    }
}
public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        // Adding elements
        list.addFirst(10);
        list.addLast(20);
        Node node = list.head;
        list.insertAfter(node, 30);
        // Displaying elements
        System.out.print("Forward order: ");
        list.displayForward();
        System.out.print("Backward order: ");
        list.displayBackward();
        // Updating elements
        node = list.head;
        node.data = 40;
        // Removing elements
        node = list.head.next;
        list.remove(node);
        // Displaying elements after update and removal
        System.out.print("Forward order after update and removal: ");
        list.displayForward();
    }
}

In the above example, we have a Node class representing a single node in the doubly linked list. Each node has an integer data value and references to the previous and next nodes in the list.

The DoublyLinkedList class represents the doubly linked list itself. It maintains references to the head and tail nodes of the list.

Constructors of Java LinkedList

The LinkedList class provides several constructors in Java to create LinkedList objects. Here are the commonly used constructors:

• LinkedList(): Creates an empty LinkedList.
• LinkedList(Collection<? extends E> c): Creates a LinkedList containing the elements of the specified collection in the order the collection's iterator returns them.

Example:

Methods of Java LinkedList

There are several methods to perform various operations on the linked list in Java. Here are some commonly used methods:

• add(element): Adds the specified element to the end of the linked list.
• add(index, element): Inserts the specified element at the specified position in the linked list.
• get(index): Returns the element at the specified position in the linked list.
• remove(index): Removes the element at the specified position in the linked list.
• size(): Returns the number of elements in the linked list.
• isEmpty(): Checks if the linked list is empty.
• contains(element): Checks if the linked list contains the specified element.
• clear(): Removes all elements from the linked list.
• toArray(): Converts the linked list to an array.

Performing Various Operations on LinkedList

Here is an example demonstrating various operations on a LinkedList:

Code:

import java.util.LinkedList;
public class LinkedListOperations {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        // Adding elements
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Orange");
        System.out.println("Initial LinkedList: " + linkedList);
        // Updating elements
        linkedList.set(1, "Mango");
        System.out.println("After updating: " + linkedList);
        // Removing elements
        linkedList.remove("Orange");
        linkedList.removeFirst();
        System.out.println("After removal: " + linkedList);
        // Iterating over elements
        System.out.print("Elements in the LinkedList: ");
        for (String element : linkedList) {
            System.out.print(element + " ");
        }
        System.out.println();
        // Converting to an array
        Object[] array = linkedList.toArray();
        System.out.print("Array representation: ");
        for (Object element : array) {
            System.out.print(element + " ");
        }
        System.out.println();
        // Size of the LinkedList
        System.out.println("Size of the LinkedList: " + linkedList.size());
        // Removing first and last elements
        linkedList.removeFirst();
        linkedList.removeLast();
        System.out.println("After removing first and last: " + linkedList);
    }
}

Java LinkedList as Queue

The LinkedList class can also be used as a queue in Java by using the methods provided by the Queue interface. Here's an example of using a LinkedList as a queue:

import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        // Adding elements to the queue
        queue.add("Apple");
        queue.add("Banana");
        queue.add("Orange");
        // Displaying the queue
        System.out.println("Queue: " + queue);
        // Removing elements from the queue
        String removedElement = queue.remove();
        System.out.println("Removed element: " + removedElement);
        // Accessing the head of the queue
        String head = queue.peek();
        System.out.println("Head of the queue: " + head);
        // Checking if the queue is empty
        boolean isEmpty = queue.isEmpty();
        System.out.println("Is the queue empty? " + isEmpty);
    }
}

In this example, we create a LinkedList and assign it to a Queue reference. We then use the queue-specific methods such as add, remove, peek, and isEmpty to perform queue operations.

When using LinkedList as a queue, elements are added to the end of the list (add method) and removed from the front of the list (remove method), following the FIFO (First-In-First-Out) order.

Java LinkedList as Deque

The LinkedList class can also be used as a double-ended queue (deque) in Java by utilizing the methods provided by the Deque interface. Here's an example of using a LinkedList as a deque:

import java.util.LinkedList;
import java.util.Deque;
public class DequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        // Adding elements to the front of the deque
        deque.addFirst("Apple");
        deque.addFirst("Banana");
        // Adding elements to the end of the deque
        deque.addLast("Orange");
        deque.addLast("Mango");
        // Displaying the deque
        System.out.println("Deque: " + deque);
        // Removing elements from the front and end of the deque
        String removedFirst = deque.removeFirst();
        String removedLast = deque.removeLast();
        System.out.println("Removed elements: " + removedFirst + ", " + removedLast);
        // Accessing the first and last elements of the deque
        String first = deque.peekFirst();
        String last = deque.peekLast();
        System.out.println("First element: " + first);
        System.out.println("Last element: " + last);
    }
}

In this example, we create a LinkedList and assign it to a Deque reference. We then use the deque-specific methods such as addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast to perform deque operations.

LinkedList vs Array List

ArrayList and LinkedList are manifestations of the Collection framework’s List interface. But, there are certain minute differences between the two terms.

Here’s a section on LinkedList vs. ArrayList Java to help you understand the key differences:

Advantages of Using LinkedList in Java

Here are the various advantages of LinkedList in Java:

• Dynamic in size

Much like vectors in Java, LinkedList is featured with the ability to grow in size or shrink. It simply means that to accommodate the addition of new elements, the LinkedList can grow. Or, it can shrink itself in case any elements are removed.

• Efficient memory

Compared to arrays, LinkedList has more efficient memory use. Array keeps all the elements in the memory locations, even though some elements might not be useful. LinkedList, however, allocates memory selectively. Memory is allocated only to the elements in use and thus is a memory savior where the data set size is variable or unknown.

• Efficient sorting

When compared to arrays, LinkedLists have more efficient sorting algorithms. Unlike arrays, swapping elements are unnecessary for LinkedLists, saving valuable time.

Conclusion

LinkedList offers efficient element manipulation in Java, which lets you comfortably add or subtract elements. It is a part of the Collection Framework and implements interfaces like Queue, List, and Deque. It has numerous advantages over an array, for being dynamic in size and having memory efficiency, but it also lacks an array’s capability of accessing random elements.

Considering the range of advantages, LinkedLists can be applicable in your day-to-day work. For instance, well-known software like Canva, MS-Word have an ‘undo’ feature executed by LinkedLists. Thus, it is an essential feature of the Java platform that you must master if you want to become a Java expert.

FAQs

1. Is LinkedList in C the same as LinkedList in Java?

The implementation and syntax of LinkedList in C and Java are different. LinkedLists are not a complementary, built-in structure in C as in Java. In C, pointers and structures are used to implement LinkedLists, while in Java, it is implementable in a doubly linked list.

2. What are the various types of LinkedLists?

The various types of LinkedLists are:

• Doubly linked list
• Singly linked list
• Circular linked list
• Multiply linked list

3. What are some LinkedList applications?

LinkedLists can be used for implementing Queues, Stacks. It also helps the user fill in elements at the head or the list's tail.

Take the Free Quiz on Java

Answer quick questions and assess your Java knowledge

Start Quiz