Java LinkedList

Introduction

The LinkedList in Java is a part of the Java Collection Framework, extending the AbstractList class and implementing the List and Deque interfaces. 

Important Key Points About Java LinkedList Class

Data Structure

LinkedList is based on a doubly-linked list data structure, which means it contains a link to the next node in the list along with a link to the previous node.

Insertion Order

Java LinkedList maintains the insertion order of the elements.

Dynamic Size

LinkedList in Java can grow and shrink dynamically as items are added or removed.

Duplicates and Null Elements

LinkedList can have duplicate and null values.

Insertion & Deletion

Insertion and deletion operations are efficient in LinkedList as compared to ArrayList, as shifting is not required. When a new element is added, it gets placed at a specific position based on the reference in the list.

Sequential Access

Accessing elements is slower compared to ArrayList because it has to traverse from the head of the list to reach the specified node.

Memory Overhead

Each element in the LinkedList consumes more memory as it holds data as well as address fields for the previous and the next element.

Use Cases

LinkedList is better for manipulating data, i.e., insertions and deletions, whereas ArrayList is better for storing and accessing data.

Implements Interfaces

The LinkedList class implements Queue and Deque interfaces. Therefore, it can also be used as a Queue, Deque, or Stack.

Iterator and ListIterator

LinkedList provides methods to return an Iterator and a ListIterator that can be used to traverse the list in either the forward or the backward direction.

Not Thread Safe

Java LinkedList is not thread-safe. You must explicitly synchronize concurrent modifications to the LinkedList in a multi-threaded environment.

Create LinkedList

Here is the syntax to create a LinkedList class object:

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

Add Elements

We can add new elements to the end of the LinkedList using add() method:

// Creating LinkedList of Strings
LinkedList<String> list = new LinkedList<>();

// Using add() method to add elements in the list
list.add("Java");
list.add("Python");
list.add("JavaScript");

We can add an element at the specified position in the LinkedList using add(index, element) method:

// Adding an element at the specific position in the list
list.add(1, "C++");

We can add an element at the beginning of the LinkedList using the addFirst() method:

// Adding elements at the beginning of the list using addFirst()
list.addFirst("Swift");

We can add an element at the end of the LinkedList using the addLast() method:

// Adding elements at the end of the list using addLast()
list.addLast("Kotlin");

Here is a complete example with output:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Creating LinkedList of Strings
        LinkedList<String> list = new LinkedList<>();

        // Using add() method to add elements in the list
        list.add("Java");
        list.add("Python");
        list.add("JavaScript");

        // Displaying the initial LinkedList
        System.out.println("Initial LinkedList : " + list);

        // Adding an element at the specific position in the list
        list.add(1, "C++");

        // Displaying the LinkedList after adding an element at position 1
        System.out.println("After add(1, \"C++\") : " + list);

        // Adding elements at the end of the list using addLast()
        list.addLast("Kotlin");

        // Displaying the LinkedList after adding an element at the end
        System.out.println("After addLast(\"Kotlin\") : " + list);

        // Adding elements at the beginning of the list using addFirst()
        list.addFirst("Swift");

        // Displaying the LinkedList after adding an element at the beginning
        System.out.println("After addFirst(\"Swift\") : " + list);
    }
}

Output:

Initial LinkedList : [Java, Python, JavaScript]
After add(1, "C++") : [Java, C++, Python, JavaScript]
After addLast("Kotlin") : [Java, C++, Python, JavaScript, Kotlin]
After addFirst("Swift") : [Swift, Java, C++, Python, JavaScript, Kotlin]

Access Elements

In order to access elements from a LinkedList in Java, you can use the get(int index), getFirst(), and getLast() methods.

Using get(int index) Method

// Creating a LinkedList of Strings
LinkedList<String> list = new LinkedList<>();

// Adding elements to the LinkedList
list.add("Java");
list.add("Python");
list.add("JavaScript");
list.add("C++");
list.add("Kotlin");

// Accessing elements from the LinkedList
// The get() method throws IndexOutOfBoundsException, if the specified index is out of range
System.out.println("Element returned by get(2): " + list.get(2));

Using getFirst() Method

// The first() method returns the first element in this list
System.out.println("Element returned by first(): " + list.getFirst());

Using getLast() Method

// The last() method returns the last element in this list
System.out.println("Element returned by last(): " + list.getLast());

Here is a complete example with output:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Creating a LinkedList of Strings
        LinkedList<String> list = new LinkedList<>();

        // Adding elements to the LinkedList
        list.add("Java");
        list.add("Python");
        list.add("JavaScript");
        list.add("C++");
        list.add("Kotlin");

        // Accessing elements from the LinkedList
        // The get() method throws IndexOutOfBoundsException, if the specified index is out of range
        System.out.println("Element returned by get(2): " + list.get(2));

        // The first() method returns the first element in this list
        System.out.println("Element returned by first(): " + list.getFirst());

        // The last() method returns the last element in this list
        System.out.println("Element returned by last(): " + list.getLast());
    }
}

Output:

Element returned by get(2): JavaScript
Element returned by first(): Java
Element returned by last(): Kotlin

Remove Elements

In Java, you can remove elements from a LinkedList using a variety of methods such as remove(Object), remove(int index), removeFirst(), removeLast(), and clear().

Here's a simple code example illustrating this, along with comments explaining each operation:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Creating a LinkedList of Strings
        LinkedList<String> list = new LinkedList<>();

        // Adding elements to the LinkedList
        list.add("Java");
        list.add("Python");
        list.add("JavaScript");
        list.add("C++");
        list.add("Kotlin");

        // Displaying the LinkedList
        System.out.println("Initial LinkedList: " + list);

        // The remove(int index) method removes the element at the specified position in this list
        list.remove(2);
        System.out.println("LinkedList after removing element at index 2: " + list);

        // The remove(Object) method removes the first occurrence of the specified element from this list, if it is present
        list.remove("Python");
        System.out.println("LinkedList after removing 'Python': " + list);

        // The removeFirst() method removes and returns the first element from this list
        list.removeFirst();
        System.out.println("LinkedList after removing first element: " + list);

        // The removeLast() method removes and returns the last element from this list
        list.removeLast();
        System.out.println("LinkedList after removing last element: " + list);

        // The clear() method removes all of the elements from this list
        list.clear();
        System.out.println("LinkedList after calling clear(): " + list);
    }
}

Output:

Initial LinkedList: [Java, Python, JavaScript, C++, Kotlin]
LinkedList after removing element at index 2: [Java, Python, C++, Kotlin]
LinkedList after removing 'Python': [Java, C++, Kotlin]
LinkedList after removing first element: [C++, Kotlin]
LinkedList after removing last element: [C++]
LinkedList after calling clear(): []

Search Elements

In Java, you can search for elements in a LinkedList using the contains(Object), indexOf(Object), and lastIndexOf(Object) methods.

Using contains(Object) Method

// The contains(Object) method returns true if this list contains the specified element
boolean found

 = list.contains("Python");
System.out.println("'Python' is in the list: " + found);

Using indexOf(Object) Method

// The indexOf(Object) method returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element
int firstIndex = list.indexOf("Python");
System.out.println("First occurrence of 'Python' is at index: " + firstIndex);

Using lastIndexOf(Object) Method

// The lastIndexOf(Object) method returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element
int lastIndex = list.lastIndexOf("Python");
System.out.println("Last occurrence of 'Python' is at index: " + lastIndex);

Here is a complete example with output:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Creating a LinkedList of Strings
        LinkedList<String> list = new LinkedList<>();

        // Adding elements to the LinkedList
        list.add("Java");
        list.add("Python");
        list.add("JavaScript");
        list.add("C++");
        list.add("Python");
        list.add("Kotlin");

        // Displaying the LinkedList
        System.out.println("LinkedList: " + list);

        // The contains(Object) method returns true if this list contains the specified element
        boolean found = list.contains("Python");
        System.out.println("'Python' is in the list: " + found);

        // The indexOf(Object) method returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element
        int firstIndex = list.indexOf("Python");
        System.out.println("First occurrence of 'Python' is at index: " + firstIndex);

        // The lastIndexOf(Object) method returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element
        int lastIndex = list.lastIndexOf("Python");
        System.out.println("Last occurrence of 'Python' is at index: " + lastIndex);
    }
}

Output:

LinkedList: [Java, Python, JavaScript, C++, Python, Kotlin]
'Python' is in the list: true
First occurrence of 'Python' is at index: 1
Last occurrence of 'Python' is at index: 4

Iterate or Loop Through LinkedList

In Java, there are several ways to iterate over a LinkedList, including using an iterator, an enhanced for loop, a traditional for loop, and Java 8 features like the forEach method and streams. Let's see some examples for each of these methods:

Using Iterator

import java.util.Iterator;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Creating a LinkedList of Strings
        LinkedList<String> list = new LinkedList<>();
        list.add("Java");
        list.add("Python");
        list.add("JavaScript");
        list.add("C++");

        // Using Iterator
        System.out.println("Iterating using Iterator:");
        Iterator<String> iterator = list.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }

        // Using Enhanced For loop
        System.out.println("Iterating using Enhanced For loop:");
        for(String language: list){
            System.out.println(language);
        }

        // Using Traditional For loop
        System.out.println("Iterating using Traditional For loop:");
        for(int i = 0; i < list.size(); i++){
            System.out.println(list.get(i));
        }

        // Using forEach() method (Java 8)
        System.out.println("Iterating using forEach() method:");
        list.forEach(language -> {
            System.out.println(language);
        });

        // Using forEach() method with method reference (Java 8)
        System.out.println("Iterating using forEach() method with method reference:");
        list.forEach(System.out::println);

        // Using Streams (Java 8)
        System.out.println("Iterating using Streams:");
        list.stream().forEach(System.out::println);
    }
}

Output:

Iterating using Iterator:
Java
Python
JavaScript
C++
Iterating using Enhanced For loop:
Java
Python
JavaScript
C++
Iterating using Traditional For loop:
Java
Python
JavaScript
C++
Iterating using forEach() method:
Java
Python
JavaScript
C++
Iterating using forEach() method with method reference:
Java
Python
JavaScript
C++
Iterating using Streams:
Java
Python
JavaScript
C++

ArrayList vs LinkedList

ArrayList and LinkedList are two commonly used classes in Java that implement the List interface. While both of them can be used to store objects, there are some key differences between the two that make them suited for different scenarios:

Underlying Data Structure

The most fundamental difference is in the way they store and manage data. An ArrayList uses a dynamic array to store the data, whereas a LinkedList uses a doubly-linked list.

Performance

ArrayLists are generally faster for lookup operations, i.e., when you want to access a specific element because it supports random access and the time complexity is O(1).

On the other hand, LinkedLists have to traverse from the head of the list to the required index, leading to a time complexity of O(n). However, LinkedLists are faster at add and remove operations, because they simply need to change the pointers of the previous and next nodes, whereas ArrayLists need to shift all elements.

Memory Usage

A LinkedList uses more memory than an ArrayList because, in addition to storing the actual data, each node in a LinkedList also needs to store two references to the next and previous nodes.

Resizable

Both ArrayList and LinkedList are resizable. But resizing an ArrayList by adding more elements than its initial capacity leads to an expensive operation of resizing the array and copying elements to the new array. LinkedList does not have this problem as elements can be added or removed without the need for resizing.

Use Cases

If you have a large number of get operations, you should use ArrayList. If you have a large number of add/remove operations (especially not at the end of the list), and you don't know the index of elements, you should use LinkedList.

Overall, the choice between ArrayList and LinkedList depends on the specific requirements of your project, such as the type of operations you need to perform, the number of elements, and memory considerations.

Conclusion

That’s all folks! In this article, you learned what a LinkedList is, the key points about LinkedList, how to create a LinkedList, how to add, remove, and search for elements in a LinkedList, how to iterate over a LinkedList, and what are the differences between a LinkedList and an ArrayList.