What is a LinkedList?

Implementation of List and Deque interfaces in Java, representing a doubly linked list. Each node contains references to the previous and next elements, as well as data.

Features:

• Insertion/removal: Efficiently insert or remove elements anywhere in the list (O(1)), as it only requires changing the links of neighboring nodes.
• Arbitrary access: Accessing an element by index (get) or searching for an element (indexOf) requires traversing the list from the beginning or end, which takes time proportional to the position of the element (O(n)).
• Memory usage: Requires more memory compared to ArrayList, as each node stores two references in addition to data.
• Null elements: Allows storing null.
• Thread safety: Not thread-safe by default.

Usage:

• Implementation of queues and stacks, where add/remove operations are frequently performed from the beginning or end.
• Scenarios requiring frequent modification of the list (insertion/removal) at arbitrary positions.

Example:

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

// Adding elements
list.add("Apple");
list.add("Banana");
list.addFirst("Orange"); // Add at the beginning

// Removing an element
list.removeLast(); // Remove the last

// Getting an element
String firstElement = list.getFirst(); // Get the first

// Iteration
for (String item : list) {
    System.out.println(item);
}