Java LinkedList

---

In Java, the LinkedList class is a part of the Java Collections Framework and implements both the List and Deque interfaces. This means a LinkedList can function as both a dynamic list and a double-ended queue, offering high flexibility in handling elements. A LinkedList is typically implemented as a doubly linked list, where each element (node) contains references to both the previous and next elements in the sequence. This makes it efficient for operations that involve frequent insertions and deletions at both ends or in the middle of the list.

---

What is a Java LinkedList?

A LinkedList in Java is a doubly linked list that stores elements in nodes, where each node contains:

1. A reference to the next node.
2. A reference to the previous node.
3. The data itself.

Unlike an ArrayList, which uses a dynamically resizing array to store elements, a LinkedList stores elements as separate objects (nodes), each pointing to the next and previous nodes. This allows for constant-time insertion or deletion of elements at the beginning or middle of the list, but access times (for reading elements) are slower compared to an ArrayList.

The LinkedList class implements both the List interface (which allows indexed access to elements) and the Deque interface (which allows adding/removing elements from both ends), making it a versatile choice for a wide range of use cases.

---

Key Features of Java LinkedList

• Doubly Linked: Each node points to both the next and the previous node, making insertion and deletion efficient at both ends and within the list.
• No Fixed Size: LinkedList does not have a fixed size, unlike arrays, and can grow or shrink dynamically as elements are added or removed.
• Insertion/Deletion Efficiency: Efficient insertion and deletion of elements at the beginning, end, or middle of the list (O(1) time complexity if the position is known).
• Slower Access Time: Accessing elements by index is slower (O(n) time complexity) compared to ArrayList since it requires traversal of the list.

---

Common Methods of the Java LinkedList

The LinkedList class provides several useful methods for adding, removing, and accessing elements:

• add(E e): Appends the specified element to the end of the list.
• addFirst(E e): Inserts the specified element at the beginning of the list.
• addLast(E e): Appends the specified element to the end of the list (same as add).
• remove(): Removes and returns the first element in the list.
• removeFirst(): Removes and returns the first element.
• removeLast(): Removes and returns the last element.
• get(int index): Retrieves the element at the specified index.
• set(int index, E e): Replaces the element at the specified index with the provided element.
• size(): Returns the number of elements in the list.
• isEmpty(): Checks if the list is empty.
• contains(Object o): Checks if the list contains the specified element.
• peek(): Retrieves, but does not remove, the first element.
• offer(E e): Inserts the specified element at the end of the list (equivalent to add).

---

Creating a Java LinkedList

You can create a LinkedList using the default constructor or specify an initial collection of elements.

Example 1: Creating and Using a LinkedList

import java.util.LinkedList;

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

        // Add elements to the list
        list.add("Java");
        list.add("Python");
        list.add("JavaScript");

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

        // Access elements by index
        System.out.println("Element at index 1: " + list.get(1));

        // Remove an element from the list
        list.remove("Python");

        // Display the updated list
        System.out.println("Updated LinkedList: " + list);
    }
}

Output:

LinkedList: [Java, Python, JavaScript]
Element at index 1: Python
Updated LinkedList: [Java, JavaScript]

In this example, we create a LinkedList of String type, add elements, access an element by index, and remove an element from the list.

---

Example 2: Using LinkedList as a Queue

Because LinkedList implements the Deque interface, you can use it as a queue to add and remove elements from both ends.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Create a LinkedList to be used as a queue
        LinkedList<String> queue = new LinkedList<>();

        // Add elements to the queue
        queue.addLast("Task 1");
        queue.addLast("Task 2");
        queue.addLast("Task 3");

        // Display the queue
        System.out.println("Queue: " + queue);

        // Remove elements from the queue (FIFO)
        System.out.println("Dequeued: " + queue.removeFirst());
        System.out.println("Dequeued: " + queue.removeFirst());

        // Display the queue after removals
        System.out.println("Queue after dequeue: " + queue);
    }
}

Output:

Queue: [Task 1, Task 2, Task 3]
Dequeued: Task 1
Dequeued: Task 2
Queue after dequeue: [Task 3]

Here, we treat the LinkedList as a FIFO queue using the addLast() method to enqueue elements and removeFirst() to dequeue them.

---

Example 3: Using LinkedList as a Stack

You can also use a LinkedList as a stack (LIFO) by adding and removing elements from the front.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        // Create a LinkedList to be used as a stack
        LinkedList<String> stack = new LinkedList<>();

        // Push elements onto the stack
        stack.addFirst("Red");
        stack.addFirst("Green");
        stack.addFirst("Blue");

        // Display the stack
        System.out.println("Stack: " + stack);

        // Pop elements from the stack (LIFO)
        System.out.println("Popped: " + stack.removeFirst());
        System.out.println("Popped: " + stack.removeFirst());

        // Display the stack after pops
        System.out.println("Stack after pop: " + stack);
    }
}

Output:

Stack: [Blue, Green, Red]
Popped: Blue
Popped: Green
Stack after pop: [Red]

In this case, the LinkedList functions as a stack using the addFirst() and removeFirst() methods, following the LIFO (Last-In-First-Out) principle.

---

When to Use a LinkedList

The LinkedList class is useful when you need:

1. Efficient insertions and deletions at both ends or in the middle of the list.
2. Dynamic sizing, as it grows or shrinks based on the number of elements.
3. A queue or stack implementation with flexible operations on both ends.

However, if you need to perform frequent random access (i.e., accessing elements by index), an ArrayList might be a better choice due to its O(1) access time compared to the O(n) time for accessing elements in a LinkedList.

---

LinkedList vs. ArrayList

Here’s a quick comparison between LinkedList and ArrayList:

• Memory Usage: LinkedList has higher memory overhead because it stores references to both the next and previous elements for each node, while ArrayList stores elements in a contiguous block of memory.
• Insertion and Deletion: LinkedList excels in insertion and deletion operations (especially at the beginning and middle of the list), while ArrayList performs better for random access.
• Access Speed: ArrayList offers faster index-based access to elements (O(1)), while LinkedList requires traversal (O(n)).

---

---