LinkedList

LinkedList:

1. A LinkedList in Java is a doubly linked list implementation of the List and Deque interfaces, best when you need fast insertions and deletions but not random access.
2. A LinkedList is a linear data structure that stores elements in nodes, where each node contains:
3. The data (element)
4. A reference (pointer) to the next node
5. A reference (pointer) to the previous node (in case of doubly linked list)

Key Points:

• Part of Java Collections Framework -> Defined in java.util package.
• Implements List, Deque, Queue interfaces.
• Dynamic size -> Unlike arrays, it can grow or shrink dynamically.
• Allows duplicates & null -> Unlike Set, it allows duplicate elements and multiple null values.
• Not synchronized -> Multiple threads can cause issues if not handled properly. Use Collections.synchronizedList() if needed.

Common Methods:

1. add(E e), addFirst(E e), addLast(E e) → Add elements
2. remove(), removeFirst(), removeLast() → Remove elements
3. get(int index), getFirst(), getLast() → Access elements
4. contains(Object o) → Check if element exists
5. size() → Number of elements
6. clear() → Remove all elements

Advantages:

• Efficient insertion & deletion (O(1) if position known).
• Can be used as a List, Queue, or Deque.

Disadvantages:

• Accessing an element by index is slower (O(n)) compared to ArrayList’s O(1).
• More memory usage (because of storing next & prev references).