LinkedList is a class in Java Collections Framework available in the java.util package.It stores data as nodes, where each node contains the element and links to the previous and next nodes.
- The size of a LinkedList can increase or decrease automatically while the program is running.
- It maintains the insertion order, meaning elements are stored in the order they are added.
- It allows duplicate elements.
- It provides faster insertion and deletion of elements compared to ArrayList, especially at the beginning or middle of the list.
Why LinkedList is Used?
LinkedList is preferred when:
1. Frequent Insertion
- Adding elements in the middle or beginning is fast.
list.addFirst("Java");
2. Frequent Deletion
- Removing elements does not require shifting other elements.
list.remove(2);
3. Queue and Deque Operations
LinkedList supports operations like:
addFirst()
addLast()
removeFirst()
removeLast()
Hence it can be used as:
- Queue
- Deque
- Stack
What is a Doubly Linked List?
A Doubly Linked List is a type of linked list in which each node contains:
- Data – the actual value stored.
- Previous Reference (Prev) – points to the previous node.
- Next Reference (Next) – points to the next node.
Because each node has links in both directions, we can traverse the list forward as well as backward.
Structure
NULL ← [10] ⇄ [20] ⇄ [30] ⇄ [40] → NULL
Each node contains:
[ Prev | Data | Next ]
For example:
[NULL | 10 | Address of 20]
[Address of 10 | 20 | Address of 30]
[Address of 20 | 30 | Address of 40]
[Address of 30 | 40 | NULL]
Advantages of Doubly Linked List
- Supports forward and backward traversal.
- Faster insertion and deletion compared to arrays.
- Easy to implement Queue, Deque, and Browser History features.
- No need to shift elements during insertion or deletion.
Disadvantages of Doubly Linked List
- Requires extra memory to store the previous reference.
- More complex than a singly linked list.
- Accessing elements by index is slower because traversal is required.