Java's LinkedList class is a powerful and flexible data structure that implements the List interface and the Deque interface. It's based on a doubly-linked list, which means each element in the list has references to both its previous and next elements. This structure allows for efficient insertions and deletions at both ends of the list, as well as anywhere in between.
In this comprehensive guide, we'll explore the various methods provided by the LinkedList class, demonstrating their usage with practical examples and explaining the inner workings of this versatile data structure.
Understanding the LinkedList Structure
Before we dive into the methods, let's briefly review the structure of a LinkedList:
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
The LinkedList class is generic, allowing you to specify the type of elements it will contain. Each element in the list is represented by a Node object, which contains the element itself and references to the previous and next nodes.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
This structure allows for efficient insertions and deletions, as only the references need to be updated, rather than shifting elements as in an ArrayList.
Creating a LinkedList
Let's start by creating a LinkedList and adding some elements to it:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
System.out.println("Initial LinkedList: " + fruits);
}
}
Output:
Initial LinkedList: [Apple, Banana, Cherry]
Adding Elements
The LinkedList class provides several methods for adding elements:
1. add(E element)
This method adds an element to the end of the list.
fruits.add("Date");
System.out.println("After adding 'Date': " + fruits);
Output:
After adding 'Date': [Apple, Banana, Cherry, Date]
2. add(int index, E element)
This method inserts an element at the specified index.
fruits.add(1, "Blueberry");
System.out.println("After adding 'Blueberry' at index 1: " + fruits);
Output:
After adding 'Blueberry' at index 1: [Apple, Blueberry, Banana, Cherry, Date]
3. addFirst(E element)
This method adds an element to the beginning of the list.
fruits.addFirst("Apricot");
System.out.println("After adding 'Apricot' at the beginning: " + fruits);
Output:
After adding 'Apricot' at the beginning: [Apricot, Apple, Blueberry, Banana, Cherry, Date]
4. addLast(E element)
This method adds an element to the end of the list (equivalent to add(E element)).
fruits.addLast("Elderberry");
System.out.println("After adding 'Elderberry' at the end: " + fruits);
Output:
After adding 'Elderberry' at the end: [Apricot, Apple, Blueberry, Banana, Cherry, Date, Elderberry]
Removing Elements
LinkedList provides various methods for removing elements:
1. remove()
This method removes and returns the first element of the list.
String removed = fruits.remove();
System.out.println("Removed element: " + removed);
System.out.println("LinkedList after remove(): " + fruits);
Output:
Removed element: Apricot
LinkedList after remove(): [Apple, Blueberry, Banana, Cherry, Date, Elderberry]
2. remove(int index)
This method removes the element at the specified index.
String removedAtIndex = fruits.remove(2);
System.out.println("Removed element at index 2: " + removedAtIndex);
System.out.println("LinkedList after remove(2): " + fruits);
Output:
Removed element at index 2: Banana
LinkedList after remove(2): [Apple, Blueberry, Cherry, Date, Elderberry]
3. remove(Object o)
This method removes the first occurrence of the specified element.
boolean isRemoved = fruits.remove("Date");
System.out.println("Is 'Date' removed? " + isRemoved);
System.out.println("LinkedList after remove('Date'): " + fruits);
Output:
Is 'Date' removed? true
LinkedList after remove('Date'): [Apple, Blueberry, Cherry, Elderberry]
4. removeFirst() and removeLast()
These methods remove and return the first and last elements of the list, respectively.
String first = fruits.removeFirst();
String last = fruits.removeLast();
System.out.println("Removed first: " + first + ", Removed last: " + last);
System.out.println("LinkedList after removeFirst() and removeLast(): " + fruits);
Output:
Removed first: Apple, Removed last: Elderberry
LinkedList after removeFirst() and removeLast(): [Blueberry, Cherry]
Accessing Elements
LinkedList provides methods to access elements at specific positions:
1. get(int index)
This method returns the element at the specified index.
String element = fruits.get(1);
System.out.println("Element at index 1: " + element);
Output:
Element at index 1: Cherry
2. getFirst() and getLast()
These methods return the first and last elements of the list without removing them.
String first = fruits.getFirst();
String last = fruits.getLast();
System.out.println("First element: " + first + ", Last element: " + last);
Output:
First element: Blueberry, Last element: Cherry
Searching and Checking
LinkedList provides methods for searching elements and checking the list's contents:
1. contains(Object o)
This method checks if the list contains the specified element.
boolean containsCherry = fruits.contains("Cherry");
boolean containsGrape = fruits.contains("Grape");
System.out.println("Contains Cherry? " + containsCherry);
System.out.println("Contains Grape? " + containsGrape);
Output:
Contains Cherry? true
Contains Grape? false
2. indexOf(Object o) and lastIndexOf(Object o)
These methods return the index of the first and last occurrence of the specified element, respectively.
fruits.add("Blueberry");
int firstIndex = fruits.indexOf("Blueberry");
int lastIndex = fruits.lastIndexOf("Blueberry");
System.out.println("First index of Blueberry: " + firstIndex);
System.out.println("Last index of Blueberry: " + lastIndex);
Output:
First index of Blueberry: 0
Last index of Blueberry: 2
Iterating Over a LinkedList
There are several ways to iterate over a LinkedList:
1. Using a for-each loop
System.out.print("Iterating using for-each loop: ");
for (String fruit : fruits) {
System.out.print(fruit + " ");
}
System.out.println();
Output:
Iterating using for-each loop: Blueberry Cherry Blueberry
2. Using an Iterator
System.out.print("Iterating using Iterator: ");
Iterator<String> iterator = fruits.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
Output:
Iterating using Iterator: Blueberry Cherry Blueberry
3. Using a ListIterator
ListIterator allows bidirectional traversal and modification of the list during iteration.
System.out.print("Iterating using ListIterator (forward): ");
ListIterator<String> listIterator = fruits.listIterator();
while (listIterator.hasNext()) {
System.out.print(listIterator.next() + " ");
}
System.out.println();
System.out.print("Iterating using ListIterator (backward): ");
while (listIterator.hasPrevious()) {
System.out.print(listIterator.previous() + " ");
}
System.out.println();
Output:
Iterating using ListIterator (forward): Blueberry Cherry Blueberry
Iterating using ListIterator (backward): Blueberry Cherry Blueberry
Advanced Operations
LinkedList supports some advanced operations that take advantage of its doubly-linked structure:
1. push(E element) and pop()
These methods add an element to the front of the list and remove and return the first element, respectively. They're equivalent to addFirst() and removeFirst().
fruits.push("Apple");
System.out.println("After push('Apple'): " + fruits);
String popped = fruits.pop();
System.out.println("Popped element: " + popped);
System.out.println("After pop(): " + fruits);
Output:
After push('Apple'): [Apple, Blueberry, Cherry, Blueberry]
Popped element: Apple
After pop(): [Blueberry, Cherry, Blueberry]
2. offer(E element), offerFirst(E element), and offerLast(E element)
These methods add elements to the list and return a boolean indicating success. They're similar to add methods but are used in queue operations.
fruits.offer("Date");
fruits.offerFirst("Apricot");
fruits.offerLast("Elderberry");
System.out.println("After offer operations: " + fruits);
Output:
After offer operations: [Apricot, Blueberry, Cherry, Blueberry, Date, Elderberry]
3. poll(), pollFirst(), and pollLast()
These methods remove and return the first or last element of the list. They return null if the list is empty.
String polled = fruits.poll();
String polledFirst = fruits.pollFirst();
String polledLast = fruits.pollLast();
System.out.println("Polled: " + polled + ", Polled First: " + polledFirst + ", Polled Last: " + polledLast);
System.out.println("After poll operations: " + fruits);
Output:
Polled: Apricot, Polled First: Blueberry, Polled Last: Elderberry
After poll operations: [Cherry, Blueberry, Date]
Performance Considerations
While LinkedList offers efficient insertions and deletions at both ends and in the middle of the list, it has some performance drawbacks:
-
Random access: Accessing elements by index is O(n) time complexity, as the list must be traversed from the beginning or end to reach the desired index.
-
Memory overhead: Each element in a LinkedList requires additional memory for the next and previous references, which can be significant for large lists.
-
Cache performance: LinkedList elements are not stored in contiguous memory locations, which can lead to poor cache performance compared to ArrayList.
Here's a simple benchmark comparing ArrayList and LinkedList for different operations:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class ListPerformanceComparison {
public static void main(String[] args) {
int n = 1000000;
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();
// Add elements
long startTime = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.add(i);
}
long endTime = System.nanoTime();
System.out.println("ArrayList add time: " + (endTime - startTime) / 1000000 + " ms");
startTime = System.nanoTime();
for (int i = 0; i < n; i++) {
linkedList.add(i);
}
endTime = System.nanoTime();
System.out.println("LinkedList add time: " + (endTime - startTime) / 1000000 + " ms");
// Access elements
startTime = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.get(i);
}
endTime = System.nanoTime();
System.out.println("ArrayList access time: " + (endTime - startTime) / 1000000 + " ms");
startTime = System.nanoTime();
for (int i = 0; i < n; i++) {
linkedList.get(i);
}
endTime = System.nanoTime();
System.out.println("LinkedList access time: " + (endTime - startTime) / 1000000 + " ms");
// Remove elements from the beginning
startTime = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.remove(0);
}
endTime = System.nanoTime();
System.out.println("ArrayList remove time: " + (endTime - startTime) / 1000000 + " ms");
startTime = System.nanoTime();
for (int i = 0; i < n; i++) {
linkedList.remove(0);
}
endTime = System.nanoTime();
System.out.println("LinkedList remove time: " + (endTime - startTime) / 1000000 + " ms");
}
}
Output (Note: Results may vary depending on the system):
ArrayList add time: 31 ms
LinkedList add time: 85 ms
ArrayList access time: 5 ms
LinkedList access time: 70453 ms
ArrayList remove time: 5453 ms
LinkedList remove time: 14 ms
This benchmark demonstrates that:
- ArrayList is faster for adding elements at the end.
- ArrayList is significantly faster for random access operations.
- LinkedList is much faster for removing elements from the beginning of the list.
Conclusion
Java's LinkedList class provides a versatile implementation of a doubly-linked list, offering efficient insertions and deletions at both ends and in the middle of the list. It implements both the List and Deque interfaces, making it suitable for a wide range of applications, including stacks, queues, and general-purpose lists.
While LinkedList excels in certain scenarios, it's important to consider its performance characteristics when choosing between LinkedList and other List implementations like ArrayList. LinkedList is ideal for applications that frequently add or remove elements from the beginning or end of the list, or that require frequent insertions and deletions in the middle of the list. However, for applications that primarily involve random access or require minimal memory overhead, ArrayList might be a better choice.
By understanding the methods and behavior of LinkedList, you can leverage its strengths to build efficient and effective Java applications. Remember to always consider your specific use case and performance requirements when deciding which List implementation to use in your projects.
