Java LinkedList Class Implementation Guide and Examples

LinkedList is a linear data structure that is used to store a collection of elements. It is a sequence of nodes, where each node contains an element and a reference to the next node in the sequence. The first node in the sequence is called the head of the list, while the last node is called the tail.

In Java, LinkedList is part of the Java Collection Framework and is implemented in the java.util package. Here’s an example of how to create a LinkedList in Java:

import java.util.LinkedList;

public class MyLinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> myLinkedList = new LinkedList<>();
        myLinkedList.add("Apple");
        myLinkedList.add("Banana");
        myLinkedList.add("Cherry");
        System.out.println("My LinkedList: " + myLinkedList);
    }
}

In this example, we first import the LinkedList class from the java.util package. We then create a LinkedList object and add three elements to it using the add() method. Finally, we print the contents of the LinkedList using the toString() method.

One thing to keep in mind while using LinkedList is that it provides constant-time performance for adding or removing elements from the beginning or end of the list. However, accessing elements in the middle of the list can be slower since the list must be traversed from the beginning or end.

Another gotcha is that LinkedList is not thread-safe, meaning that if multiple threads are accessing the list at the same time, there can be issues with synchronization. To avoid this, you can use the synchronized keyword while accessing the list or use a thread-safe implementation such as java.util.concurrent.ConcurrentLinkedDeque.

Additionally, since LinkedList implements the List interface, you can use all the methods provided by the List interface, such as add(), remove(), get(), and set().

Doubly LinkedList using java Linkedlist class

In Java, the LinkedList class also provides an implementation of a double-linked list, meaning each node in the list has a reference to both the previous and next nodes. Here’s an example of how to use the LinkedList class to create a double-linked list:

import java.util.LinkedList;

public class DoubleLinkedListExample {

    public static void main(String[] args) {
        
        // Create a new LinkedList
        LinkedList<String> myLinkedList = new LinkedList<>();

        // Add some elements to the list
        myLinkedList.add("Apple");
        myLinkedList.add("Banana");
        myLinkedList.add("Cherry");
        
        // Add an element at the beginning of the list
        myLinkedList.addFirst("Orange");
        
        // Add an element at the end of the list
        myLinkedList.addLast("Grape");
        
        // Remove an element from the beginning of the list
        myLinkedList.removeFirst();
        
        // Remove an element from the end of the list
        myLinkedList.removeLast();
        
        // Iterate over the elements in the list
        for (String element : myLinkedList) {
            System.out.println(element);
        }
    }
}

In this example, we first create a new LinkedList object called myLinkedList. We then add some elements to the list using the add method, which appends the elements to the end of the list.

To add an element at the beginning of the list, we use the addFirst method, which inserts the element at the front of the list. To add an element at the end of the list, we use the addLast method, which appends the element to the end of the list.

To remove an element from the beginning of the list, we use the removeFirst method, which removes and returns the first element of the list. To remove an element from the end of the list, we use the removeLast method, which removes and returns the last element of the list.

Finally, we iterate over the elements in the list using a for-each loop and print each element to the console.

Note that because LinkedList is a generic class, you can specify the type of objects that the list will hold when you create a new LinkedList object. In this example, we’ve created a LinkedList of String objects.

Circular LinkedList using Java LinkedList class

The LinkedList class in Java does not provide a built-in implementation of a circular linked list. A circular linked list is a linked list where the last node in the list has a reference to the first node in the list, creating a loop.

However, you can easily create a circular linked list in Java by extending the LinkedList class and adding a reference to the first node in the list. Here’s an example:

public class CircularLinkedList<E> extends LinkedList<E> {

    // Reference to the first node in the list
    private Node first;

    // Constructor
    public CircularLinkedList() {
        super();
    }

    // Add an element to the list
    public void addElement(E element) {
        // Create a new node
        Node newNode = new Node(element);

        // If the list is empty, set the first node to the new node
        if (isEmpty()) {
            first = newNode;
        } else {
            // Otherwise, set the next node of the last node to the new node
            getLastNode().setNext(newNode);
        }

        // Set the next node of the new node to the first node, creating a loop
        newNode.setNext(first);

        // Add the element to the list
        add(element);
    }

    // Get the last node in the list
    private Node getLastNode() {
        Node node = first;
        while (node.getNext() != first) {
            node = node.getNext();
        }
        return node;
    }

    // Check if the list is empty
    private boolean isEmpty() {
        return first == null;
    }

    // Node class
    private class Node {

        // Data of the node
        private E data;

        // Reference to the next node
        private Node next;

        // Constructor
        public Node(E data) {
            this.data = data;
        }

        // Getter for data
        public E getData() {
            return data;
        }

        // Getter for next
        public Node getNext() {
            return next;
        }

        // Setter for next
        public void setNext(Node next) {
            this.next = next;
        }
    }
}

In this example, we’ve created a new CircularLinkedList class that extends the built-in LinkedList class. We’ve also added a private inner Node class to represent the nodes in the list.

The CircularLinkedList class has a reference to the first node in the list, which is initialized to null. When an element is added to the list using the addElement method, a new node is created and added to the end of the list using the add method of the LinkedList class. The next reference of the new node is then set to the first node in the list, creating a loop. If the list was previously empty, the first node in the list is set to the new node.

The getLastNode method is used to get a reference to the last node in the list, which is needed to set the next reference of the new node. The isEmpty method is used to check if the list is empty.

Note that this implementation does not check for null values in the add method, which could result in a NullPointerException if the addElement method is called with a null value. In a real implementation, you would want to add null checks to ensure that the list is not corrupted.

Methods that can be used with LinkedList in Java

add(E e): This method adds the specified element to the end of the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");

add(int index, E element): This method adds the specified element at the specified position in the list. It has a time complexity of O(n) where n is the index of the element being added and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add(1, "Banana");

addFirst(E e): This method adds the specified element to the beginning of the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.addFirst("Apple");

addLast(E e): This method adds the specified element to the end of the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.addLast("Cherry");

clear(): This method removes all elements from the list. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.clear();

clone(): This method returns a shallow copy of the list. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(n).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
LinkedList<String> copiedLinkedList = (LinkedList<String>) myLinkedList.clone();

contains(Object o): This method returns true if the list contains the specified element, false otherwise. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
boolean containsApple = myLinkedList.contains("Apple");

get(int index): This method returns the element at the specified position in the list. It has a time complexity of O(n) where n is the index of the element being retrieved and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String firstElement = myLinkedList.get(0);

getFirst(): This method returns the first element in the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String firstElement = myLinkedList.getFirst();

getLast(): This method returns the last element in the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
String lastElement = myLinkedList.getLast();

indexOf(Object o): This method returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
int index = myLinkedList.indexOf("Banana");

isEmpty(): This method returns true if the list contains no elements, false otherwise. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
boolean empty = myLinkedList.isEmpty();

lastIndexOf(Object o): This method returns the index of the last occurrence of the specified element in the list, or -1 if the element is not found. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
myLinkedList.add("Apple");
int lastIndex = myLinkedList.lastIndexOf("Apple");

remove(Object o): This method removes the first occurrence of the specified element from the list, if it is present. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
myLinkedList.remove("Banana");

remove(int index): This method removes the element at the specified position in the list. It has a time complexity of O(n) where n is the index of the element being removed and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
myLinkedList.remove(0);

removeFirst(): This method removes the first element from the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.removeFirst();

removeLast(): This method removes the last element from the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
myLinkedList.removeLast();

size(): This method returns the number of elements in the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
int size = myLinkedList.size();

toArray(): This method returns an array containing all of the elements in the list. It has a time complexity of O(n) where n is the number of elements in the list and a space complexity of O(n).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
Object[] array = myLinkedList.toArray();

offer(E e): This method adds the specified element to the end of the list, returning true if the operation was successful and false if it was not. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
boolean added = myLinkedList.offer("Apple");

offerFirst(E e): This method adds the specified element to the beginning of the list, returning true if the operation was successful and false if it was not. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
boolean added = myLinkedList.offerFirst("Apple");

offerLast(E e): This method adds the specified element to the end of the list, returning true if the operation was successful and false if it was not. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
boolean added = myLinkedList.offerLast("Apple");

peek(): This method retrieves, but does not remove, the first element of the list, or returns null if the list is empty. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String firstElement = myLinkedList.peek();

peekFirst(): This method retrieves, but does not remove, the first element of the list, or returns null if the list is empty. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String firstElement = myLinkedList.peekFirst();

peekLast(): This method retrieves, but does not remove, the last element of the list, or returns null if the list is empty. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String lastElement = myLinkedList.peekLast();

poll(): This method retrieves and removes the first element of the list, or returns null if the list is empty. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String firstElement = myLinkedList.poll();

pollFirst(): This method retrieves and removes the first element of the list, or returns null if the list is empty. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
String firstElement = myLinkedList.pollFirst();

pollLast(): This method retrieves and removes the last element of the list, or returns null if the list is empty. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
String lastElement = myLinkedList.pollLast();

addAll(Collection<? extends E> c): This method adds all of the elements in the specified collection to the end of the list. It has a time complexity of O(n) where n is the number of elements being added and a space complexity of O(n).

LinkedList<String> myLinkedList = new LinkedList<>();
ArrayList<String> myArrayList = new ArrayList<>();
myArrayList.add("Apple");
myArrayList.add("Banana");
myLinkedList.addAll(myArrayList);

addAll(int index, Collection<? extends E> c): This method adds all of the elements in the specified collection at the specified position in the list. It has a time complexity of O(n) where n is the number of elements being added and a space complexity of O(n).

LinkedList<String> myLinkedList = new LinkedList<>();
ArrayList<String> myArrayList = new ArrayList<>();
myArrayList.add("Apple");
myArrayList.add("Banana");
myLinkedList.addAll(1, myArrayList);

containsAll(Collection<?> c): This method returns true if the list contains all of the elements in the specified collection, false otherwise. It has a time complexity of O(n^2) where n is the number of elements in the list and the collection being compared, and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
ArrayList<String> myArrayList = new ArrayList<>();
myArrayList.add("Apple");
boolean containsAll = myLinkedList.containsAll(myArrayList);

iterator(): This method returns an iterator over the elements in the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
Iterator<String> iterator = myLinkedList.iterator();

listIterator(): This method returns a list iterator over the elements in the list. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
ListIterator<String> listIterator = myLinkedList.listIterator();

listIterator(int index): This method returns a list iterator over the elements in the list, starting at the specified position. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
ListIterator<String> listIterator = myLinkedList.listIterator(1);

removeAll(Collection<?> c): This method removes all of the elements in the list that are also in the specified collection. It has a time complexity of O(n^2) where n is the number of elements in the list and the collection being compared, and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
ArrayList<String> myArrayList = new ArrayList<>();
myArrayList.add("Apple");
myLinkedList.removeAll(myArrayList);

retainAll(Collection<?> c): This method removes all of the elements in the list that are not in the specified collection. It has a time complexity of O(n^2) where n is the number of elements in the list and the collection being compared, and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
ArrayList<String> myArrayList = new ArrayList<>();
myArrayList.add("Apple");
myLinkedList.retainAll(myArrayList);

set(int index, E element): This method replaces the element at the specified position in the list with the specified element. It has a time complexity of O(n) where n is the index of the element being replaced and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
myLinkedList.set(1, "Orange");

subList(int fromIndex, int toIndex): This method returns a view of the portion of the list between the specified fromIndex, inclusive, and toIndex, exclusive. It has a time complexity of O(n) where n is the size of the sublist being created, and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
myLinkedList.add("Orange");
List<String> sublist = myLinkedList.subList(1, 3);

descendingIterator(): This method returns an iterator over the elements in the list in reverse order. It has a time complexity of O(1) and a space complexity of O(1).

LinkedList<String> myLinkedList = new LinkedList<>();
myLinkedList.add("Apple");
myLinkedList.add("Banana");
Iterator<String> descendingIterator = myLinkedList.descendingIterator();