Linked List in Java

When working with dynamic data structures in Java, the Linked List in Java is one of the most important data structures to understand. It provides a flexible way of storing elements compared to arrays, and it's widely used in many real-world applications. In this blog, we’ll explore the mechanics of a Linked List in Java, its different types, and its internal workings. We’ll also look at how Java 8 introduced enhancements to the Linked List class, making it easier than ever to work with linked data structures. Learn how to implement and use Linked List in Java. Understand its types, operations like insertion and deletion, and when to use it in real-world applications.

What is a Linked List in Java?

In Java, a linked list is a linear data structure with non-contiguous storage for its elements, also known as nodes.. Each node contains two parts:

1. Data: The actual value

2. Pointer (or Reference):  A variable that holds the memory address of the next node in the chain.

Linked lists employ dynamic memory allocation, in contrast to arrays, which are kept in contiguous memory locations.

Java offers a pre-implemented LinkedList class in the java. util package, making it easy to work with linked lists without having to build one from scratch.

Types of Linked Lists

There are several types of linked lists:

1. Singly Linked List: Nodes in this structure are linked to the next node in line, with no reference to the previous one.

2. Doubly Linked List: To allow for two-way traversal, each node has links to both the previous and next nodes.

3. Circular Linked List: The reference from the last node points back to the first node, creating a looped structure.
Note: Java's built-in LinkedList is implemented as a doubly linked list.

Linked List Implementation and some methods in Java Using Collections

Java has a ready-to-use LinkedList class in the java.util package:

import java.util.LinkedList;

public class IndianActorList {

    public static void main(String[] args) {

        LinkedList<String> listActors = new LinkedList<>();

listActors.add("Amitabh Bachchan");

listActors.add("Shah Rukh Khan");

listActors.add("Rajinikanth");

listActors.add("Priyanka Chopra");

listActors.add("Deepika Padukone");

        System.out.println("List of Actors:");

        for (String a : listActors) {

            System.out.println(a);

        }

listActors.addFirst("Ranbir Kapoor");

listActors.addLast("Alia Bhatt");

        System.out.println("\nUpdated  Actors:");

        for (String actor : listActors) {

            System.out.println(actor);

        }

        listActors.removeFirst();

        listActors.removeLast();

        System.out.println("\nFinal List of Indian Actors (After Removals):");

        for (String actor : listActors) {

            System.out.println(actor);

        }

    }

}

This built-in Linked List implementation in Java supports various methods like add(), remove(), get(), and size().

How a Linked List in Java Internally Works :

A doubly linked list serves as the foundation for Java's LinkedList internal structure.

 Here's how it works:

• Each node contains:
  • E itemData: the actual data.
  • Node<E> nextpointer: reference to the next node.
  • Node<E> prevpointer: reference to the previous node.
• The LinkedList keeps references to both the first and last nodes.

• Inserting or deleting elements at the start or end is highly efficient, with a time complexity of O(1).
• The traversal required to access elements by index has an O(n) time complexity. 
  The core structure of the Java source code (OpenJDK) looks somewhat like this:

private static class Node<E> {

    E itemData;

    Node<E> nextpointer;

    Node<E> prevpointer;

    Node(Node<E> prevpointer, E itemData, Node<E> nextpointer) {

        this.itemData = itemData;

        this.nextpointer = nextpointer;

        this.prevpointer = prevpointer;

    }

}

Advantages of Linked List in Java

1. Dynamic Size: Linked lists don't need a set startup size like arrays do.
2. Effective Additions and Removals: Especially at the start and middle of the list.
   
    
3. No Wasted Memory: Memory is allocated as needed.

Disadvantages of Linked List in Java

1. Slower Access Time: Random access is not possible. You must traverse from the head.
2. Extra Memory Usage: Each node stores additional pointers (next/prev).

Cache Inefficiency: Linked lists have poor locality of reference compared to arrays.

Program to Demonstrate the Use of Java's LinkedList with User-Defined Blog Class

public class MyBlog {

    // Instance variables (fields)

    private String title_blog;

    private String content_blog;

    public MyBlog(String title_blog, String content_blog) {

        this.title_blog = title_blog;

        this.content_blog = content_blog;

    }

    public String getTitleBlog() {

        return title_blog;

    }

    public void setTitleBlog(String title_blog) {

        this.title_blog = title_blog;

    }

    public String getContentBlog() {

        return content_blog;

    }

    public void setContentBlog(String content_blog) {

        this.content_blog = content_blog;

    }

    public void setContent(String content) {

        this.content = content;

    }

    @Override

    public String toString() {

        return "Blog{title='" + title_blog + "', content='" + content_blog + "'}";

    }

}

import java.util.LinkedList;

public class BlogExample {

    public static void main(String[] args) {

        LinkedList<Blog> blogList = new LinkedList<>();

        blogList.add(new MyBlog("Java Basics", "Content about Java programming."));

        blogList.add(new MyBlog("LinkedList in java", "Content about data structures."));

        blogList.add(new MyBlog("Introduction to Algorithms", "Content about algorithms."));

        System.out.println("All Blogs:");

        for (MyBlog blog : blogList) {

            System.out.println(blog);

}

    }

}

Synchronized LinkedList in Java: The list itself is synchronized, meaning that any modification or access to it is thread-safe. However, iterating over the list is not thread-safe unless you explicitly synchronize on the list during iteration. This is why we use a synchronized block when iterating through the list.

import java.util.*;

public class SynchronizedLinkedListDemo {

    public static void main(String[] args) {

        List<Integer> list = new LinkedList<>();

        List<Integer> synList = Collections.synchronizedList(list);

synList.add(10);

        synList.add(20);

        synList.add(30);

        System.out.println("Synchronized List: " + synList );

synList.remove(Integer.valueOf(20));

        System.out.println("Synchronized List after removal: " + synList);

        synchronized(synList) {

            for (Integer value : synList) {

                System.out.println(value);

            }

        }

    }

}

Java 8 Enhancements in LinkedList

Java 8 didn’t change the fundamental implementation of the Linked List in Java, but it introduced functional programming features to the collections, including LinkedList.

Here are some Java 8 features you can use with LinkedList:

1. Streams API

LinkedList<String> list = new LinkedList<>(Arrays.asList("Java", "Python", "Go"));

list.stream()

    .filter(lang -> lang.startsWith("J"))

    .forEach(System.out::println); // Output: Java

2. Lambda Expressions

list.forEach(item -> System.out.println(item.toUpperCase()));

3. Method References

list.forEach(System.out::println);

4. Collectors

List<String> filteredList = list.stream()

    .filter(lang -> lang.length() > 2)

    .collect(Collectors.toList());

These features significantly simplify working with collections like LinkedList, making the code more concise and readable.

To summarize, a Linked List in Java is a flexible, dynamic data structure ideal for certain use cases like frequent insertions and deletions. Understanding how linked list internally works, and how to build and use it, gives you an edge in writing optimized and maintainable Java code.

We also saw a synchronized linked list implementation in Java, explored the built-in LinkedList class, discussed advantages and disadvantages, and checked what Java 8 enhancements brought to the table in terms of usability.

Do visit our channel to explore more: SevenMentor 

Author:- Kiran Tiwari