LinkedList in Java

How Does LinkedList Work Internally?

LinkedList is a linear data structure that consists of a sequence of nodes. Each node in a LinkedList contains two parts: a data value and a reference (or link) to the next node in the sequence. The first node is called the head, and the last node points to null, indicating the end of the list.

Internally, LinkedList maintains three instance variables:

1. Head: A reference to the first node in the list.
2. Tail: A reference to the last node in the list.
3. Size: An integer representing the number of elements in the list.

When an element is added to the LinkedList, a new node is created with the given data value. The new node's reference is set to the current head, and the head is updated to point to the new node. Similarly, when an element is removed, the references are adjusted to maintain the correct sequence of nodes.

LinkedList provides constant-time O(1) performance for insertion and deletion operations at both ends of the list (head and tail). However, accessing elements at a specific index requires traversing the list from the head or tail, resulting in a linear-time O(n) operation.

Here's a visual representation of a LinkedList:

Each node contains a data value and a reference to the next node, forming a chain-like structure.

Constructors in the LinkedList

LinkedList provides several constructors to create and initialize a new instance of the LinkedList class. Here are the available constructors:

1. LinkedList(): This is the default constructor that creates an empty LinkedList.

   LinkedList<Type> list = new LinkedList<>();

2. LinkedList(Collection<? extends E> c):  This constructor creates a LinkedList containing all the elements from the specified collection, in the order returned by the collection's iterator.

   List<Integer> numbers = Arrays.asList(1, 2, 3, 4, 5);
   LinkedList<Integer> list = new LinkedList<>(numbers);

These constructors provide flexibility in creating a LinkedList, either empty or initialized with elements from another collection.

Methods for Java LinkedList

LinkedList provides a rich set of methods to perform various operations on the list. Here are some commonly used methods:

Lets implement above methods:

To implement a LinkedList in Java, we can create a custom class that represents a node and contains methods for adding, removing, and accessing elements.

For example : 

• Java

Java

public class LinkedList<E> {

    private Node<E> head;

    private Node<E> tail;

    private int size;

    private static class Node<E> {

        E data;

        Node<E> next;

        Node(E data) {

            this.data = data;

            this.next = null;

        }

    }

    public void add(E element) {

        Node<E> newNode = new Node<>(element);

        if (head == null) {

            head = newNode;

            tail = newNode;

        } else {

            tail.next = newNode;

            tail = newNode;

        }

        size++;

    }

    public void add(int index, E element) {

        if (index < 0 || index > size) {

            throw new IndexOutOfBoundsException("Invalid index: " + index);

        }

        if (index == size) {

            add(element);

        } else {

            Node<E> newNode = new Node<>(element);

            if (index == 0) {

                newNode.next = head;

                head = newNode;

            } else {

                Node<E> prev = getNodeAtIndex(index - 1);

                newNode.next = prev.next;

                prev.next = newNode;

            }

            size++;

        }

    }

    public E get(int index) {

        if (index < 0 || index >= size) {

            throw new IndexOutOfBoundsException("Invalid index: " + index);

        }

        return getNodeAtIndex(index).data;

    }

    public E remove(int index) {

        if (index < 0 || index >= size) {

            throw new IndexOutOfBoundsException("Invalid index: " + index);

        }

        Node<E> removedNode;

        if (index == 0) {

            removedNode = head;

            head = head.next;

            if (head == null) {

                tail = null;

            }

        } else {

            Node<E> prev = getNodeAtIndex(index - 1);

            removedNode = prev.next;

            prev.next = removedNode.next;

            if (prev.next == null) {

                tail = prev;

            }

        }

        size--;

        return removedNode.data;

    }

    private Node<E> getNodeAtIndex(int index) {

        Node<E> current = head;

        for (int i = 0; i < index; i++) {

            current = current.next;

        }

        return current;

    }

    public int size() {

        return size;

    }

}

You can also try this code with Online Java Compiler

Run Code

In this implementation, we have a `Node` class that represents each node in the LinkedList. The `LinkedList` class contains methods for adding elements (`add()`), inserting elements at a specific index (`add(int index, E element)`), retrieving elements (`get()`), removing elements (`remove()`), and getting the size of the list (`size()`).

The `getNodeAtIndex()` method is a helper method that traverses the list to find the node at a specific index.

This implementation provides the basic functionality of a LinkedList. You can further extend it by adding more methods like `contains()`, `clear()`, and others based on your requirements.

Hierarchy of Java List Interface

In Java, the List interface is part of the Collection framework and extends the Collection interface. It represents an ordered collection that allows duplicate elements. Below is the hierarchy and a list of the commonly used classes that implement the List interface.

Hierarchy

java.lang.Object  
   ↳ java.util.Collection (Interface)  
       ↳ java.util.List (Interface)  
           ↳ java.util.AbstractList (Abstract Class)  
               ↳ java.util.ArrayList  
               ↳ java.util.Vector  
                   ↳ java.util.Stack  
               ↳ java.util.LinkedList  

Performing Various Operations on LinkedList

Let's see how to perform various operations on it:

1. Adding elements
2. Updating elements
3. Removing elements
4. Iterating over elements
5. To Array()
6. Size()
7. remove First()
8. remove last()

1. Adding elements

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

list.add("Apple");
list.add("Banana");
list.add(1, "Orange");
// list now contains ["Apple", "Orange", "Banana"]

2. Updating elements

list.set(1, "Grapes");
// list now contains ["Apple", "Grapes", "Banana"]

3. Removing elements

list.remove(1);
// list now contains ["Apple", "Banana"]
String removedElement = list.remove(0);
// removedElement = "Apple"
// list now contains ["Banana"]
Iterating over elements:
for (String element : list) {
    System.out.println(element);
}

Output:

Banana

4. Iterating over elements

You can iterate through the LinkedList using a for loop, forEach(), or an iterator.

for (String s : list) {  
    System.out.println(s);  
}  
list.forEach(s -> System.out.println(s));  

5. To Array()

String[] array = list.toArray(new String[list.size()]);
// array now contains ["Banana"]
Size():
int size = list.size();
// size = 1

6. Size()

The size() method returns the number of elements in the LinkedList.

int size = list.size();  
System.out.println("Size: " + size);  

7. remove First()

String firstElement = list.removeFirst();
// firstElement = "Banana"
// list is now empty

8. remove last()

list.add("Apple");
list.add("Orange");
String lastElement = list.removeLast();
// lastElement = "Orange"
// list now contains ["Apple"]

Advantages of using LinkedList in Java

LinkedList have several advantages over other data structures in certain scenarios, like :

1. Dynamic size: LinkedList allows for dynamic resizing, meaning the size of the list can grow or shrink as needed during runtime. This is particularly useful when the number of elements is not known in advance or when frequent additions or removals are required.
 

2. Efficient insertion and deletion: LinkedList provides constant-time O(1) performance for insertion and deletion operations at both ends of the list (head and tail). This makes it efficient for scenarios where elements need to be frequently added or removed from the beginning or end of the list.
 

3. No shifting of elements: Unlike arrays, inserting or removing elements from the middle of a LinkedList does not require shifting the subsequent elements. Each node maintains a reference to the next node, allowing for quick and efficient modifications to the list structure.
 

4. Flexibility: LinkedList can be used to implement various data structures such as stacks, queues, and associative arrays. Its flexibility allows for creative problem-solving and adapting to different requirements.
 

5. Memory efficiency: LinkedList allocates memory for each node dynamically, which can be more memory-efficient compared to arrays when dealing with large datasets or when the size of the list is not known in advance.

Disadvantages of using LinkedList in Java

Now, let’s discuss some of the disadvantages of Linkedlist : 

1. Random access is slow: Accessing an element at a specific index in a LinkedList requires traversing the list from the head or tail until the desired index is reached. This results in a linear-time O(n) operation, making random access inefficient compared to arrays, which provide constant-time O(1) access to elements by index.
 

2. Extra memory usage: LinkedList requires extra memory to store the references (pointers) to the next node for each element. This overhead can be significant when storing small elements or when memory is limited. In contrast, arrays store elements contiguously in memory, which can be more memory-efficient.
 

3. Lack of cache-friendly operations: Arrays have better cache locality because elements are stored contiguously in memory. This allows for efficient cache utilization and faster element retrieval. LinkedList, on the other hand, may have nodes scattered in different memory locations, leading to cache misses and slower performance for certain operations.
 

4. Overhead for small lists: For small lists or scenarios where the number of elements is known and fixed, using a LinkedList may introduce unnecessary overhead compared to using an array. The additional memory for references and the lack of cache-friendly access can make LinkedList less efficient in such cases.
 

5. Complexity of implementation: Implementing a LinkedList from scratch requires more code and is more complex compared to using an array. The additional complexity can make the code harder to read, understand, and maintain, especially for beginners.

Frequently Asked Questions

Why is Linked List used?

Linked List is used for efficient memory usage, dynamic sizing, and fast insertion or deletion operations, especially when frequent modifications are required.

When to use LinkedList in Java?

Use LinkedList in Java when your application requires frequent insertions or deletions in the middle of the list rather than quick random access.

What is the time complexity of inserting or removing elements at the beginning or end of a LinkedList?

The time complexity of inserting or removing elements at the beginning or end of a LinkedList is O(1) or constant time.

Can a LinkedList contain duplicate elements?

Yes, a LinkedList can contain duplicate elements. It allows for multiple occurrences of the same value.

Is it efficient to search for an element in a LinkedList?

 Searching for an element in a LinkedList requires traversing the list from the beginning, resulting in a time complexity of O(n) in the worst case. It is not as efficient as searching in an array or other data structures that provide random access.

How many types of linked lists are there in Java?

In Java, there are primarily two types of linked lists: Singly Linked List, where each node points to the next node, and Doubly Linked List, where each node points to both the next and previous nodes.

Why is linked list faster than ArrayList?

A LinkedList is faster than an ArrayList for insertions and deletions, as it doesn't require shifting elements like in an array. However, it has slower random access, as it requires traversing nodes to access elements.

Conclusion

In this article, we have learned about the LinkedList data structure in Java. We discussed its internal workings, constructors, and methods. We also looked at how to implement a LinkedList and perform various operations such as adding, updating, removing, and iterating over elements. Additionally, we discussed the advantages and disadvantages of using LinkedList in different scenarios.

Recommended Readings:

• Generic LinkedList in Java
• Linked List in Data Structure
• Singly Linked List in Java
• Difference between ArrayList and LinkedList
• Implementing a Linked List in Java Using Class