Linked List in Java: Implementation, Usage, and Applications

Introduction

A linked list in Java is a linear data structure where elements are stored in separate objects called nodes. Each node contains data and a reference to the next node in the sequence. Unlike arrays, linked lists don't store elements in contiguous memory locations. This dynamic structure allows for efficient insertions and deletions.

In Java, Linked lists offer flexibility when the size of data may change frequently. They provide better memory utilization compared to arrays in certain scenarios. Understanding linked lists is essential for Java developers working on complex applications. 

They form the foundation for more advanced data structures like stacks and queues. Many online Software Engineering courses emphasize linked lists as a fundamental concept for aspiring programmers.

What is Linked List in Java?

A linked list in Java is a collection of nodes that forms a linear data structure. Each node contains two components: data and a reference to the next node. The first node is called the head, and the last node points to null. This structure allows for dynamic memory allocation as the program runs.

Linked lists in Java come in different types to suit various programming needs. The most common types include:

• Singly Linked List: Each node points to the next node in the sequence.
• Doubly Linked List: Each node references next and previous nodes.
• Circular Linked List: The last node points back to the first node, forming a circle.

When discussing what is linked list in Java, we must understand its key characteristics. Unlike arrays, linked lists don't require contiguous memory allocation. This feature makes them ideal for situations where the size of data is unknown beforehand. 

// Basic structure of a node in a linked list in Java
class Node {
    int data;       // Data stored in the node
    Node next;      // Reference to the next node
    
    // Constructor
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

This code has no direct output as it's just a class definition. However, it shows the fundamental building block of a linked list in Java. Each node stores an integer value and maintains a reference to the next node in the sequence. The constructor initializes a new node with the given data and sets the next reference to null, indicating it's not connected to any other node yet.

Linked List Implementation in Java

Implementing a linked list in Java requires understanding both custom implementation and built-in classes. A custom implementation gives you control over the internal workings. The built-in LinkedList class provides ready-to-use functionality for most applications.

Creating a Linked List in Java

To create a linked list in Java from scratch, you need to define two main components. First, create a Node class to represent each element. Then, implement the LinkedList class to manage these nodes.

Here's how to create a linked list in Java with a custom implementation:

// Custom implementation of a singly linked list
public class SinglyLinkedList {
    // Head of the linked list
    Node head;
    
    // Inner Node class
    static class Node {
        int data;
        Node next;
        
        // Constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    
    // Method to insert a new node at the beginning
    public void insertAtBeginning(int data) {
        // Create new node with given data
        Node newNode = new Node(data);
        
        // Make the new node point to the current head
        newNode.next = head;
        
        // Update head to point to the new node
        head = newNode;
    }
    
    // Method to print the linked list
    public void printList() {
        Node current = head;
        System.out.print("LinkedList: ");
        
        // Traverse through the linked list
        while (current != null) {
            // Print the data at current node
            System.out.print(current.data + " ");
            
            // Go to next node
            current = current.next;
        }
        System.out.println();
    }
    
    // Main method to test the implementation
    public static void main(String[] args) {
        // Create an empty linked list
        SinglyLinkedList list = new SinglyLinkedList();
        
        // Insert nodes at the beginning
        list.insertAtBeginning(5);
        list.insertAtBeginning(10);
        list.insertAtBeginning(15);
        
        // Print the linked list
        list.printList();
    }
}

Output:

LinkedList: 15 10 5

Explanation:

This code implements a simple singly linked list in Java. The main method demonstrates how to create a linked list and insert elements. When we insert 5, 10, and 15 at the beginning, each new element becomes the new head of the list. Therefore, the most recently added element (15) appears first, followed by 10 and then 5. The printList method traverses the list from head to tail, printing each node's data value.

This implementation shows how to create a linked list in Java with basic operations. The main components include the Node class, insertion, and traversal.

Many beginners wonder how to create a linked list in Java efficiently. The key is to understand the relationship between nodes. Each operation must maintain proper references to ensure the list's integrity.

Java's Built-in LinkedList Class

Java provides a built-in implementation of linked list through the java.util.LinkedList class. This class implements the List and Deque interfaces, making it versatile for various applications.

Here's how to use Java's built-in LinkedList class:

import java.util.LinkedList;

public class BuiltInLinkedListExample {
    public static void main(String[] args) {
        // Create a LinkedList of Strings
        LinkedList<String> languages = new LinkedList<>();
        
        // Add elements to the LinkedList
        languages.add("Java");
        languages.add("Python");
        languages.add("JavaScript");
        
        // Add an element at the beginning
        languages.addFirst("C++");
        
        // Add an element at the end
        languages.addLast("Ruby");
        
        // Print the LinkedList
        System.out.println("LinkedList: " + languages);
        
        // Get the first element
        System.out.println("First element: " + languages.getFirst());
        
        // Get the last element
        System.out.println("Last element: " + languages.getLast());
        
        // Remove an element
        languages.remove("Python");
        
        // Print the updated LinkedList
        System.out.println("After removal: " + languages);
    }
}

Output:

LinkedList: [C++, Java, Python, JavaScript, Ruby]

First element: C++

Last element: Ruby

After removal: [C++, Java, JavaScript, Ruby]

Explanation:

This code demonstrates using Java's built-in LinkedList class. First, we create a new LinkedList that stores String objects. Then we add three programming languages to the list. We use addFirst() to insert "C++" at the beginning and addLast() to append "Ruby" to the end. 

The program then displays the entire list, retrieves and displays the first and last elements, removes "Python" from the list, and finally shows the updated list after removal. This built-in implementation handles all the internal linked list operations for us.

The built-in LinkedList class offers numerous advantages over custom implementations. It provides methods for common operations, supports generics, and integrates well with Java's Collections Framework.

When you create a linked list in Java using the built-in class, you benefit from:

1. Thread safety when used with proper synchronization
2. Integration with other collection classes
3. Support for null elements
4. Rich set of methods for manipulation

Common Linked List Operations

Linked lists in Java support various operations for data manipulation. Understanding these operations is crucial for effective implementation.

Adding Elements

To add elements to a linked list in Java, you can use several methods:

At the beginning (head):

 // Custom implementation
public void addFirst(int data) {
    Node newNode = new Node(data);
    newNode.next = head;
    head = newNode;
}

// Using built-in LinkedList
linkedList.addFirst(data);
// OR
linkedList.offerFirst(data);

At the end (tail):

// Custom implementation
public void addLast(int data) {
    Node newNode = new Node(data);
    
    // If list is empty, make new node the head
    if (head == null) {
        head = newNode;
        return;
    }
    
    // Traverse to the last node
    Node last = head;
    while (last.next != null) {
        last = last.next;
    }
    
    // Connect the last node to the new node
    last.next = newNode;
}

// Using built-in LinkedList
linkedList.addLast(data);
// OR
linkedList.offerLast(data);

At a specific position:

// Custom implementation
public void insertAt(int position, int data) {
    Node newNode = new Node(data);
    
    // Handle special case for head
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return;
    }
    
    // Find the previous node of the position
    Node current = head;
    for (int i = 0; i < position - 1 && current != null; i++) {
        current = current.next;
    }
    
    // If position is out of bounds
    if (current == null) {
        System.out.println("Position out of bounds");
        return;
    }
    
    // Insert the new node
    newNode.next = current.next;
    current.next = newNode;
}

// Using built-in LinkedList
linkedList.add(position, data);

Removing Elements

Removing elements from a linked list in Java requires updating the references properly:

From the beginning:

// Custom implementation
public Node removeFirst() {
    if (head == null) {
        return null;
    }
    
    Node temp = head;
    head = head.next;
    return temp;
}

// Using built-in LinkedList
linkedList.removeFirst();
// OR
linkedList.pollFirst();

From the end:

// Custom implementation
public Node removeLast() {
    if (head == null) {
        return null;
    }
    
    // If only one node exists
    if (head.next == null) {
        Node temp = head;
        head = null;
        return temp;
    }
    
    // Find the second last node
    Node secondLast = head;
    while (secondLast.next.next != null) {
        secondLast = secondLast.next;
    }
    
    // Save the last node
    Node temp = secondLast.next;
    
    // Remove the last node
    secondLast.next = null;
    
    return temp;
}

// Using built-in LinkedList
linkedList.removeLast();
// OR
linkedList.pollLast();

By value:

// Custom implementation
public boolean removeByValue(int data) {
    if (head == null) {
        return false;
    }
    
    // If head node holds the value to be deleted
    if (head.data == data) {
        head = head.next;
        return true;
    }
    
    // Search for the node to be deleted
    Node current = head;
    while (current.next != null && current.next.data != data) {
        current = current.next;
    }
    
    // If value was not found
    if (current.next == null) {
        return false;
    }
    
    // Remove the node
    current.next = current.next.next;
    return true;
}

// Using built-in LinkedList
linkedList.remove(Integer.valueOf(data));

Searching Elements

Searching for elements in a linked list requires traversal:

// Custom implementation
public boolean search(int data) {
    Node current = head;
    
    // Traverse through the list
    while (current != null) {
        // If data is found
        if (current.data == data) {
            return true;
        }
        current = current.next;
    }
    
    // Data not found
    return false;
}

// Using built-in LinkedList
boolean exists = linkedList.contains(data);

No direct output is shown for this code as it's a method definition. The search method traverses the linked list to check if a specific value exists in any node. It starts from the head and sequentially checks each node until it either finds the value (returns true) or reaches the end of the list (returns false). The built-in LinkedList offers the contains() method that performs the same operation with similar time complexity (O(n)).

How to Reverse a Linked List

Reversing a linked list in Java is a common interview question. Here's how to implement it:

// Custom implementation
public void reverse() {
    Node previous = null;
    Node current = head;
    Node next = null;
    
    while (current != null) {
        // Save the next node
        next = current.next;
        
        // Reverse the link
        current.next = previous;
        
        // Move to the next nodes
        previous = current;
        current = next;
    }
    
    // Update the head
    head = previous;
}

// Using built-in LinkedList (works for specific scenarios)
Collections.reverse(linkedList);

No direct output is shown for this code snippet as it's a method definition. The reverse method performs an in-place reversal of a linked list. It uses three pointers (previous, current, and next) to reverse the direction of each link as it traverses the list. After reversing all links, the head pointer is updated to point to what was formerly the last node. For the built-in LinkedList, Collections.reverse() reverses the order of elements but works differently internally since the LinkedList class has bidirectional references.

Understanding how to reverse a linked list in Java demonstrates your grasp of pointers and references. The key is to change the direction of pointers without losing track of nodes.

Linked List Programs in Java

Let's explore a practical linked list program in Java that demonstrates multiple operations. This example shows how to implement a doubly linked list with various functionalities.

Problem Statement:

Create a doubly linked list with operations to insert at different positions, delete nodes, and display the list in both forward and backward directions.

Solution:

public class DoublyLinkedListDemo {
    // Node class for doubly linked list
    static class Node {
        int data;
        Node prev;
        Node next;
        
        // Constructor
        Node(int d) {
            data = d;
            prev = null;
            next = null;
        }
    }
    
    // Doubly linked list class
    static class DoublyLinkedList {
        Node head;
        
        // Insert at the beginning
        public void insertAtBeginning(int data) {
            // Create new node
            Node newNode = new Node(data);
            
            // If list is empty
            if (head == null) {
                head = newNode;
                return;
            }
            
            // Adjust references
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
        
        // Insert at the end
        public void insertAtEnd(int data) {
            // Create new node
            Node newNode = new Node(data);
            
            // If list is empty
            if (head == null) {
                head = newNode;
                return;
            }
            
            // Traverse to last node
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            
            // Adjust references
            last.next = newNode;
            newNode.prev = last;
        }
        
        // Insert after a given node
        public void insertAfter(Node prevNode, int data) {
            // Check if previous node exists
            if (prevNode == null) {
                System.out.println("Previous node cannot be null");
                return;
            }
            
            // Create new node
            Node newNode = new Node(data);
            
            // Adjust references
            newNode.next = prevNode.next;
            newNode.prev = prevNode;
            
            // Update next node's prev if it exists
            if (prevNode.next != null) {
                prevNode.next.prev = newNode;
            }
            
            // Update previous node's next
            prevNode.next = newNode;
        }
        
        // Delete a node
        public void delete(Node nodeToDelete) {
            // If list is empty or node is null
            if (head == null || nodeToDelete == null) {
                return;
            }
            
            // If node to delete is head
            if (head == nodeToDelete) {
                head = nodeToDelete.next;
            }
            
            // Change next only if node to delete is NOT the last node
            if (nodeToDelete.next != null) {
                nodeToDelete.next.prev = nodeToDelete.prev;
            }
            
            // Change prev only if node to delete is NOT the first node
            if (nodeToDelete.prev != null) {
                nodeToDelete.prev.next = nodeToDelete.next;
            }
        }
        
        // Display list forward
        public void displayForward() {
            Node current = head;
            System.out.print("Forward: ");
            
            while (current != null) {
                System.out.print(current.data + " ");
                current = current.next;
            }
            
            System.out.println();
        }
        
        // Display list backward
        public void displayBackward() {
            // If list is empty
            if (head == null) {
                System.out.println("Backward: ");
                return;
            }
            
            // Find the last node
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            
            // Traverse backward
            Node current = last;
            System.out.print("Backward: ");
            
            while (current != null) {
                System.out.print(current.data + " ");
                current = current.prev;
            }
            
            System.out.println();
        }
    }
    
    // Main method to test the implementation
    public static void main(String[] args) {
        // Create a new doubly linked list
        DoublyLinkedList dll = new DoublyLinkedList();
        
        // Insert nodes
        dll.insertAtEnd(6);
        dll.insertAtBeginning(7);
        dll.insertAtBeginning(1);
        dll.insertAtEnd(4);
        
        // Insert after second node
        dll.insertAfter(dll.head.next, 8);
        
        // Display the list
        System.out.println("Doubly linked list after operations:");
        dll.displayForward();
        dll.displayBackward();
        
        // Delete the third node
        dll.delete(dll.head.next.next);
        
        // Display the list after deletion
        System.out.println("Doubly linked list after deletion:");
        dll.displayForward();
        dll.displayBackward();
    }
}

Output:

Doubly linked list after operations:

Forward: 1 7 8 6 4 

Backward: 4 6 8 7 1 

Doubly linked list after deletion:

Forward: 1 7 6 4 

Backward: 4 6 7 1 

Explanation:

This linked list program in Java demonstrates a doubly linked list implementation. Each node contains data, a reference to the previous node, and a reference to the next node. The program performs these operations:

1. Inserts nodes at the beginning and end
2. Inserts a node after a specific node
3. Deletes a node from any position
4. Displays the list in both forward and backward directions

The doubly linked list differs from a singly linked list by allowing traversal in both directions. This bidirectional property makes certain operations more efficient.

How Linked Lists Work Internally

Understanding how linked list internally works in Java requires knowledge of memory management and references. When you create a linked list, you're creating a chain of node objects.

Memory Allocation

In Java, linked list nodes are allocated on the heap. Each node is a separate object with its own memory space. This is different from arrays, where elements are stored in contiguous memory locations.

Here's how linked lists utilize memory:

1. Dynamic Allocation: Nodes are created on demand using the new keyword.
2. Non-contiguous Storage: Nodes can be scattered across the heap.
3. Reference Connections: The structure is maintained through references between nodes.

Also Explore: Stack and Heap Memory in Java

Reference Management

How linked list internally works in Java largely depends on reference management. These references create the "links" in the linked list:

1. In Singly Linked Lists: Each node has one reference pointing to the next node.
2. In Doubly Linked Lists: Each node has two references, one to the next node and one to the previous node.
3. In Circular Linked Lists: The last node's reference points back to the first node.

Internal Implementation of Java's LinkedList Class

Java's built-in LinkedList class is implemented as a doubly linked list. Here's a simplified view of how it works internally:

// Simplified view of Java's LinkedList implementation
public class LinkedList<E> {
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
    // Methods for manipulation...
}

This is not an executable code example but rather a simplified representation of how Java's LinkedList class is structured internally. There's no direct output for this code. The actual Java LinkedList implementation is a doubly linked list that maintains references to both the first and last nodes in the list. The transient keyword indicates these fields won't be serialized. Each node stores the actual data element and references to both the previous and next nodes, allowing for bidirectional traversal.

The LinkedList class maintains references to both the first and last nodes for efficient access. When elements are added or removed, only the necessary references are updated, avoiding the need to shift elements as in arrays.

Garbage Collection

How linked list internally works in Java is also related to garbage collection. When a node is removed from the list, it becomes eligible for garbage collection if no other references to it exist. This automatic memory management is a significant advantage in Java.

Linked List vs. ArrayList

When comparing linked list to ArrayList in Java, several factors come into play. Each has strengths and weaknesses for different scenarios.

Comparison Table

When to Use LinkedList

Linked list in Java is preferable in these scenarios:

• Frequent insertions and deletions at the beginning or middle
• No need for random access to elements
• Memory fragmentation is not a concern
• Implementation of stacks, queues, or deques
• When size is unknown and may change frequently

When to Use ArrayList

ArrayList performs better in these cases:

• Frequent random access to elements
• More read operations than write operations
• Limited insertions and deletions
• Memory efficiency is important
• Need for efficient iteration

Conclusion

Linked lists in Java provide a flexible way to handle dynamic data collections. They excel in situations where frequent insertions and deletions occur. The key benefit lies in their ability to grow and shrink without reallocation. 

Java offers both custom implementation options and a built-in LinkedList class. Each approach has its merits depending on specific application needs. Understanding linked list operations helps in selecting the right data structure.

The internal workings demonstrate essential concepts in reference management. Comparing linked lists with ArrayList helps in making informed design decisions. Master linked lists to build more efficient Java applications.

FAQs

1. What is a linked list in Java?

A linked list in Java is a linear data structure where elements are stored in nodes. Each node contains data and a reference to the next node in the sequence. This structure allows for dynamic memory allocation and efficient insertions and deletions.

2. How do I create a linked list in Java?

You can create a linked list in Java either by implementing your own linked list class or by using Java's built-in LinkedList class. For custom implementation, define a Node class and a LinkedList class to manage the nodes. For built-in implementation, use LinkedList<Type> list = new LinkedList<>();.

3. What are the advantages of linked list over arrays in Java?

Linked lists in Java offer dynamic size adjustment, efficient insertions and deletions (especially at the beginning), and better memory utilization for certain scenarios. They don't require contiguous memory allocation and don't need to be resized when elements are added.

4. How to create a singly linked list in Java?

To create a singly linked list in Java, define a Node class with data and next pointer. Then create a LinkedList class with a head reference and methods for insertion, deletion, and traversal. Each node in a singly linked list points only to the next node.

5. How to implement a doubly linked list in Java?

Implementing a doubly linked list in Java requires nodes with both next and previous references. Create a Node class with data, prev, and next fields. The LinkedList class should maintain references to both head and tail nodes for efficient operations at both ends.

6. How linked list internally works in Java?

Linked lists in Java work by connecting Node objects through references. Each node stores data and references to adjacent nodes. Java's built-in LinkedList class uses a doubly linked list implementation, maintaining references to both first and last nodes for efficiency.

7. How to reverse a linked list in Java?

To reverse a linked list in Java, iterate through the list while changing the direction of each node's reference. Three pointers (previous, current, and next) are used to track the nodes during reversal. The head reference is updated to point to the last node at the end.

8. What is the time complexity of operations in a linked list?

In a linked list, insertion and deletion at the beginning take O(1) time. Operations at the end take O(1) for doubly linked lists and O(n) for singly linked lists. Finding, inserting, or deleting a node in the middle takes O(n) time. Random access also requires O(n) time.

9. Can linked lists store different types of data in Java?

Yes, linked lists in Java can store different types of data using generics. Java's built-in LinkedList class is a generic class, allowing you to specify the type of elements it will contain. For custom implementations, you can make your Node and LinkedList classes generic.

10. How to iterate through a linked list in Java?

You can iterate through a linked list in Java using a for-each loop, Iterator, or ListIterator. For custom implementations, use a while loop with a current node reference that traverses from head to tail. For the built-in LinkedList class, you can use any standard collection iteration method.

11. What is the difference between ArrayList and LinkedList in Java?

The main differences are in internal structure and performance characteristics. ArrayList uses a dynamic array, providing fast random access but slower insertions and deletions. LinkedList uses a doubly linked list, offering fast insertions and deletions but slower random access and iteration.

12. Is LinkedList thread-safe in Java?

No, the built-in LinkedList class in Java is not thread-safe. For multi-threaded environments, you need to use external synchronization or concurrent collection classes like ConcurrentLinkedDeque or use Collections.synchronizedList() to wrap the LinkedList.

Take the Free Quiz on Java

Answer quick questions and assess your Java knowledge

Start Quiz