LinkedList in Java

What is a LinkedList?

A LinkedList is a linear data structure, similar to an array, but with a fundamental difference in how elements are stored in memory. Instead of storing elements in contiguous memory locations, a LinkedList stores elements in nodes, where each node contains the data and a reference (or pointer) to the next node in the sequence. In a doubly-linked list, each node also contains a reference to the previous node.

This non-contiguous storage allows LinkedLists to efficiently insert or delete elements at any position without needing to shift elements around like you would with an array. However, accessing an element by index is generally slower in a LinkedList than in an array because you have to traverse the list from the beginning to find the desired element.

Detailed Explanation of the LinkedList Class in Java

Java's LinkedList class implements the List and Deque interfaces, providing a doubly-linked list implementation. This means each node has a reference to both the next and previous elements in the list.

Creation

You can create a LinkedList in Java using the following ways:

 import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // Create an empty LinkedList of Integers
        LinkedList<Integer> linkedList1 = new LinkedList<>();

        // Create a LinkedList with initial elements
        LinkedList<String> linkedList2 = new LinkedList<>();
        linkedList2.add("Apple");
        linkedList2.add("Banana");
        linkedList2.add("Cherry");

        // Alternatively using addAll
        LinkedList<String> linkedList3 = new LinkedList<>();
        java.util.List<String> initialList = java.util.Arrays.asList("Apple", "Banana", "Cherry");
        linkedList3.addAll(initialList);

        System.out.println("LinkedList 1: " + linkedList1); // Output: LinkedList 1: []
        System.out.println("LinkedList 2: " + linkedList2); // Output: LinkedList 2: [Apple, Banana, Cherry]
        System.out.println("LinkedList 3: " + linkedList3); // Output: LinkedList 3: [Apple, Banana, Cherry]
    }
} 

Adding Elements

LinkedList provides several methods for adding elements:

• add(E element): Appends the element to the end of the list.
• add(int index, E element): Inserts the element at the specified index.
• addFirst(E element): Inserts the element at the beginning of the list.
• addLast(E element): Appends the element to the end of the list (same as add(E element)).
• addAll(Collection<? extends E> c): Appends all the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
• addAll(int index, Collection<? extends E> c): Inserts all of the elements in the specified collection into this list, starting at the specified position.

 import java.util.LinkedList;

public class LinkedListAddExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        linkedList.add("Apple"); // Adds to the end
        linkedList.add("Banana");
        linkedList.add(1, "Mango"); // Inserts at index 1
        linkedList.addFirst("Grapes"); // Adds to the beginning
        linkedList.addLast("Orange"); // Adds to the end

        System.out.println(linkedList); // Output: [Grapes, Apple, Mango, Banana, Orange]

        java.util.List<String> newList = java.util.Arrays.asList("Plum", "Kiwi");
        linkedList.addAll(newList);
        System.out.println(linkedList); // Output: [Grapes, Apple, Mango, Banana, Orange, Plum, Kiwi]

        linkedList.addAll(2, java.util.Arrays.asList("Strawberry", "Blueberry"));
        System.out.println(linkedList); //Output: [Grapes, Apple, Strawberry, Blueberry, Mango, Banana, Orange, Plum, Kiwi]
    }
} 

Retrieving Elements

LinkedList provides methods to access elements:

• get(int index): Returns the element at the specified index.
• getFirst(): Returns the first element in the list.
• getLast(): Returns the last element in the list.
• peek(): Retrieves, but does not remove, the head (first element) of this list. Returns null if this list is empty.
• peekFirst(): Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
• peekLast(): Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

 import java.util.LinkedList;

public class LinkedListGetExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        System.out.println("Element at index 1: " + linkedList.get(1)); // Output: Element at index 1: Banana
        System.out.println("First element: " + linkedList.getFirst());   // Output: First element: Apple
        System.out.println("Last element: " + linkedList.getLast());    // Output: Last element: Cherry
        System.out.println("Peek first element: " + linkedList.peekFirst());    // Output: Peek first element: Apple
        System.out.println("Peek last element: " + linkedList.peekLast());    // Output: Peek last element: Cherry
    }
} 

Removing Elements

LinkedList provides several methods for removing elements:

• remove(int index): Removes the element at the specified index.
• remove(Object o): Removes the first occurrence of the specified element.
• removeFirst(): Removes and returns the first element in the list.
• removeLast(): Removes and returns the last element in the list.
• poll(): Retrieves and removes the head (first element) of this list. Returns null if this list is empty.
• pollFirst(): Retrieves and removes the first element of this list, or returns null if this list is empty.
• pollLast(): Retrieves and removes the last element of this list, or returns null if this list is empty.
• clear(): Removes all of the elements from this list. The list will be empty after this call returns.

 import java.util.LinkedList;

public class LinkedListRemoveExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");
        linkedList.add("Banana"); //Adding another "Banana" to demonstrate remove(Object o)

        linkedList.remove(1); // Removes element at index 1
        System.out.println(linkedList); // Output: [Apple, Cherry, Banana]

        linkedList.remove("Apple"); // Removes the first occurrence of "Apple"
        System.out.println(linkedList); // Output: [Cherry, Banana]

        linkedList.removeFirst(); // Removes the first element
        System.out.println(linkedList); // Output: [Banana]

        linkedList.add("Orange");
        linkedList.add("Grape");
        System.out.println(linkedList); //Output: [Banana, Orange, Grape]

        linkedList.removeLast(); // Removes the last element
        System.out.println(linkedList); // Output: [Banana, Orange]

        linkedList.clear(); //Removes all elements
        System.out.println(linkedList); //Output: []
    }
} 

Iterating

You can iterate through a LinkedList using several methods:

• For-each loop: Simplest and often the preferred way.
• Iterator: More control over the iteration, allows removal of elements during iteration.
• ListIterator: Allows bidirectional iteration and modification.
• Traditional for loop: Can be used, but less efficient than for ArrayLists, due to the get(int index) method having O(n) time complexity.

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

public class LinkedListIterationExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        System.out.println("Using for-each loop:");
        for (String fruit : linkedList) {
            System.out.println(fruit);
        }

        System.out.println("\nUsing Iterator:");
        Iterator<String> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("\nUsing ListIterator (bidirectional):");
        ListIterator<String> listIterator = linkedList.listIterator();
        while (listIterator.hasNext()) {
            System.out.println(listIterator.next());
        }
        System.out.println("\nIterating in reverse:");
        while (listIterator.hasPrevious()) {
            System.out.println(listIterator.previous());
        }

        System.out.println("\nUsing traditional for loop (less efficient):");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.get(i));
        }
    }
} 

LinkedList vs. ArrayList: When to Use Which

Both LinkedList and ArrayList implement the List interface, but they have different underlying implementations, which affects their performance for different operations.

• ArrayList: Uses a dynamic array to store elements.
• LinkedList: Uses a doubly-linked list to store elements.

When to use LinkedList:

• Frequent insertions and deletions at arbitrary positions: LinkedList excels here because inserting or deleting an element only requires updating the references of neighboring nodes, which is O(1) once the position is known. In contrast, ArrayList requires shifting elements, which can be O(n).
• Implementing queues and stacks: LinkedList implements the Deque interface, making it suitable for implementing queues and stacks efficiently.
• Memory usage is less of a concern: LinkedList generally uses more memory per element due to the storage of node references.

When to use ArrayList:

• Frequent random access: ArrayList provides O(1) access to elements by index, whereas LinkedList requires traversing the list from the beginning, which is O(n).
• Few insertions and deletions: If insertions and deletions are infrequent, the performance difference between ArrayList and LinkedList is less significant.
• Memory efficiency is important: ArrayList uses less memory overall due to the contiguous storage of elements.

Time Complexity of Operations:

Here's a table summarizing the time complexity of common operations for LinkedList and ArrayList:

Important Notes on Time Complexity of LinkedList:

• When considering add(int index, E element) or remove(int index) for a LinkedList, the O(n) complexity refers to the time it takes to *find* the element at the given index by traversing the list from the beginning. Once the node at that index is found, the insertion or deletion itself is O(1) because it only involves updating pointers.
• Similarly, remove(Object o) requires searching the list for the element, resulting in O(n) complexity.

In summary, choose LinkedList when insertions and deletions are frequent, and ArrayList when random access is a priority.