What is LinkedList?
In Java, the LinkedList class is a part of the java.util package and implements the List and Deque
interfaces. Unlike an ArrayList, which stores elements in a contiguous block of memory, a LinkedList stores elements in nodes, where each node contains the data and a reference to the next node in the sequence.
Why Use a LinkedList?
- Efficient Insertions and Deletions: Inserting and removing elements from the beginning or middle of a LinkedList is faster compared to an ArrayList, as it doesn’t require shifting elements.
- Doubly Linked List: Java’s LinkedList is a doubly linked list, meaning each node has references to both the next and previous nodes, making traversing in both directions easy.
- Memory Usage: The LinkedList consumes more memory compared to an ArrayList due to its extra references (next and previous).
Core Features of Java LinkedList
- Linked Structure: Stores elements as nodes, each containing a reference to the next (and previous) node.
- Flexible Size: Like ArrayList, LinkedList does not have a fixed size. You can add elements dynamically.
- Efficient for Operations: Ideal for scenarios involving frequent insertions or deletions of elements at any position.
- Doubly Linked: Each node contains a reference to both the next and the previous element, allowing bidirectional traversal.
How to Use LinkedList in Java
1. Import the LinkedList Class
To use LinkedList, you must import it from the java.util package.
import java.util.LinkedList;
2. Creating a LinkedList
You can create a LinkedList that holds elements of a specific type by using generics, just like an ArrayList.
LinkedList<String> list = new LinkedList<>();
You can also initialize the list with values.
LinkedList<Integer> numbers = new LinkedList<>(Arrays.asList(10, 20, 30, 40));
Common Methods of LinkedList
Method | Description |
---|---|
add(E e) | Adds an element to the end of the list. |
addFirst(E e) | Adds an element at the beginning of the list. |
addLast(E e) | Adds an element at the end of the list. |
remove() | Removes and returns the first element of the list. |
removeFirst() | Removes the first element of the list. |
removeLast() | Removes the last element of the list. |
get(int index) | Retrieves the element at the specified index. |
size() | Returns the number of elements in the list. |
peek() | Retrieves but does not remove the first element. |
contains(Object o) | Checks if the list contains the specified element. |
clear() | Removes all elements from the list. |
Examples of Using LinkedList
1. Basic Operations
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// Create a LinkedList
LinkedList<String> fruits = new LinkedList<>();
// Add elements
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
// Display the LinkedList
System.out.println("Fruits: " + fruits);
// Add element at the beginning
fruits.addFirst("Orange");
System.out.println("After Adding First: " + fruits);
// Add element at the end
fruits.addLast("Grapes");
System.out.println("After Adding Last: " + fruits);
// Remove first element
fruits.removeFirst();
System.out.println("After Removing First: " + fruits);
// Remove last element
fruits.removeLast();
System.out.println("After Removing Last: " + fruits);
}
}
Output:
Fruits: [Apple, Banana, Cherry]
After Adding First: [Orange, Apple, Banana, Cherry]
After Adding Last: [Orange, Apple, Banana, Cherry, Grapes]
After Removing First: [Apple, Banana, Cherry, Grapes]
After Removing Last: [Apple, Banana, Cherry]
2. Traversing a LinkedList
You can iterate through a LinkedList using an enhanced for-loop or a standard for-loop.
Using a For-Each Loop
for (String fruit : fruits) {
System.out.println(fruit);
}
Using a For Loop
for (int i = 0; i < fruits.size(); i++) {
System.out.println(fruits.get(i));
}
3. Working with Integer LinkedList
import java.util.LinkedList;
public class IntegerLinkedListExample {
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
// Add numbers
numbers.add(10);
numbers.add(20);
numbers.add(30);
// Display numbers
System.out.println("Numbers: " + numbers);
// Find sum of all elements
int sum = 0;
for (int num : numbers) {
sum += num;
}
System.out.println("Sum: " + sum);
}
}
Output:
Numbers: [10, 20, 30]
Sum: 60
4. Peek and Poll Methods
The peek() method retrieves the first element without removing it, while poll() retrieves and removes the first element.
LinkedList<String> colors = new LinkedList<>();
colors.add("Red");
colors.add("Blue");
colors.add("Green");
System.out.println("Peek: " + colors.peek()); // Retrieves first element
System.out.println("Poll: " + colors.poll()); // Removes and retrieves first element
System.out.println("After Poll: " + colors);
Output:
Peek: Red
Poll: Red
After Poll: [Blue, Green]
Performance Considerations
- Insertion and Deletion: Inserting or removing elements at the beginning or in the middle of the list is faster than in an ArrayList, as LinkedList doesn’t require shifting elements.
- Memory Overhead: Each node in a LinkedList stores two references (next and previous), leading to higher memory consumption compared to an ArrayList.
- Random Access: Accessing elements by index is slower in a LinkedList compared to an ArrayList due to the need to traverse nodes.