Java's LinkedList class is a powerful and versatile data structure that implements the List interface. Unlike ArrayList, which uses a dynamic array under the hood, LinkedList is based on a doubly-linked list. This unique structure offers distinct advantages and use cases that every Java developer should understand.
Understanding Doubly-Linked Lists
Before diving into Java's LinkedList implementation, let's refresh our understanding of doubly-linked lists.
🔗 A doubly-linked list is a linear data structure where each element (node) contains:
- The actual data
- A reference to the next node
- A reference to the previous node
This bi-directional linking allows for efficient traversal in both directions, making certain operations more efficient compared to singly-linked lists or arrays.
[Prev | Data | Next] <-> [Prev | Data | Next] <-> [Prev | Data | Next]
Java LinkedList: Key Features
Java's LinkedList class offers several key features that make it a valuable tool in a developer's arsenal:
- 📊 Implements List and Deque interfaces
- 🔄 Allows duplicate elements
- 🆓 Permits null elements
- 🔢 Maintains insertion order
- 🚀 Not synchronized (thread-safe versions available through Collections.synchronizedList())
Creating a LinkedList
Let's start by creating a LinkedList and adding some elements:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> fruits = new LinkedList<>();
// Adding elements
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
System.out.println("Fruits: " + fruits);
}
}
Output:
Fruits: [Apple, Banana, Cherry]
Adding Elements to LinkedList
LinkedList provides several methods to add elements:
add(E element): Appends the element to the end of the listadd(int index, E element): Inserts the element at the specified positionaddFirst(E element): Inserts the element at the beginning of the listaddLast(E element): Appends the element to the end of the list (same as add(E element))
Let's see these in action:
LinkedList<String> colors = new LinkedList<>();
colors.add("Red");
colors.add(1, "Green");
colors.addFirst("Blue");
colors.addLast("Yellow");
System.out.println("Colors: " + colors);
Output:
Colors: [Blue, Red, Green, Yellow]
Removing Elements from LinkedList
LinkedList offers various methods to remove elements:
remove(): Removes and returns the first elementremove(int index): Removes the element at the specified positionremove(Object o): Removes the first occurrence of the specified elementremoveFirst(): Removes and returns the first elementremoveLast(): Removes and returns the last element
Example:
LinkedList<Integer> numbers = new LinkedList<>();
numbers.addAll(Arrays.asList(1, 2, 3, 4, 5, 2));
System.out.println("Original list: " + numbers);
numbers.remove();
System.out.println("After remove(): " + numbers);
numbers.remove(2);
System.out.println("After remove(2): " + numbers);
numbers.remove(Integer.valueOf(2));
System.out.println("After remove(Integer.valueOf(2)): " + numbers);
numbers.removeFirst();
System.out.println("After removeFirst(): " + numbers);
numbers.removeLast();
System.out.println("After removeLast(): " + numbers);
Output:
Original list: [1, 2, 3, 4, 5, 2]
After remove(): [2, 3, 4, 5, 2]
After remove(2): [2, 3, 5, 2]
After remove(Integer.valueOf(2)): [3, 5, 2]
After removeFirst(): [5, 2]
After removeLast(): [5]
Accessing Elements in LinkedList
LinkedList provides methods to access elements:
get(int index): Returns the element at the specified positiongetFirst(): Returns the first elementgetLast(): Returns the last element
Example:
LinkedList<String> animals = new LinkedList<>(Arrays.asList("Lion", "Tiger", "Bear", "Elephant"));
System.out.println("Animals: " + animals);
System.out.println("First animal: " + animals.getFirst());
System.out.println("Last animal: " + animals.getLast());
System.out.println("Animal at index 2: " + animals.get(2));
Output:
Animals: [Lion, Tiger, Bear, Elephant]
First animal: Lion
Last animal: Elephant
Animal at index 2: Bear
Iterating Through a LinkedList
There are several ways to iterate through a LinkedList:
- Using a for-each loop
- Using an Iterator
- Using a ListIterator (allows bi-directional traversal)
Let's explore each method:
LinkedList<String> cities = new LinkedList<>(Arrays.asList("New York", "London", "Tokyo", "Paris"));
// 1. Using a for-each loop
System.out.println("Using for-each loop:");
for (String city : cities) {
System.out.println(city);
}
// 2. Using an Iterator
System.out.println("\nUsing Iterator:");
Iterator<String> iterator = cities.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
// 3. Using a ListIterator (forward)
System.out.println("\nUsing ListIterator (forward):");
ListIterator<String> listIterator = cities.listIterator();
while (listIterator.hasNext()) {
System.out.println(listIterator.next());
}
// 3. Using a ListIterator (backward)
System.out.println("\nUsing ListIterator (backward):");
listIterator = cities.listIterator(cities.size());
while (listIterator.hasPrevious()) {
System.out.println(listIterator.previous());
}
Output:
Using for-each loop:
New York
London
Tokyo
Paris
Using Iterator:
New York
London
Tokyo
Paris
Using ListIterator (forward):
New York
London
Tokyo
Paris
Using ListIterator (backward):
Paris
Tokyo
London
New York
LinkedList as a Queue or Stack
LinkedList implements the Deque interface, which allows it to be used as a queue or stack:
LinkedList<String> tasks = new LinkedList<>();
// Using as a Queue (FIFO)
tasks.offer("Task 1");
tasks.offer("Task 2");
tasks.offer("Task 3");
System.out.println("Tasks queue: " + tasks);
System.out.println("Processing: " + tasks.poll());
System.out.println("Processing: " + tasks.poll());
System.out.println("Remaining tasks: " + tasks);
// Using as a Stack (LIFO)
LinkedList<String> stack = new LinkedList<>();
stack.push("Bottom");
stack.push("Middle");
stack.push("Top");
System.out.println("\nStack: " + stack);
System.out.println("Popped: " + stack.pop());
System.out.println("Popped: " + stack.pop());
System.out.println("Remaining stack: " + stack);
Output:
Tasks queue: [Task 1, Task 2, Task 3]
Processing: Task 1
Processing: Task 2
Remaining tasks: [Task 3]
Stack: [Top, Middle, Bottom]
Popped: Top
Popped: Middle
Remaining stack: [Bottom]
Performance Considerations
🚀 LinkedList offers O(1) time complexity for the following operations:
- Adding/removing from the beginning or end of the list
- Adding/removing a known node
However, it has O(n) time complexity for:
- Random access by index
- Searching for an element
⚖️ When choosing between ArrayList and LinkedList, consider:
- Use ArrayList if you frequently need random access to elements
- Use LinkedList if you frequently need to add/remove elements at the beginning or end of the list
Practical Example: Task Manager
Let's create a simple task manager using LinkedList to demonstrate its practical use:
import java.util.LinkedList;
import java.util.Scanner;
public class TaskManager {
private LinkedList<String> tasks = new LinkedList<>();
private Scanner scanner = new Scanner(System.in);
public void run() {
while (true) {
printMenu();
int choice = scanner.nextInt();
scanner.nextLine(); // Consume newline
switch (choice) {
case 1:
addTask();
break;
case 2:
completeTask();
break;
case 3:
viewTasks();
break;
case 4:
System.out.println("Exiting Task Manager. Goodbye!");
return;
default:
System.out.println("Invalid choice. Please try again.");
}
}
}
private void printMenu() {
System.out.println("\n--- Task Manager ---");
System.out.println("1. Add Task");
System.out.println("2. Complete Task");
System.out.println("3. View Tasks");
System.out.println("4. Exit");
System.out.print("Enter your choice: ");
}
private void addTask() {
System.out.print("Enter task description: ");
String task = scanner.nextLine();
tasks.addLast(task);
System.out.println("Task added successfully!");
}
private void completeTask() {
if (tasks.isEmpty()) {
System.out.println("No tasks to complete.");
return;
}
System.out.println("Completing the first task: " + tasks.getFirst());
tasks.removeFirst();
System.out.println("Task completed!");
}
private void viewTasks() {
if (tasks.isEmpty()) {
System.out.println("No tasks in the list.");
return;
}
System.out.println("Current Tasks:");
for (int i = 0; i < tasks.size(); i++) {
System.out.println((i + 1) + ". " + tasks.get(i));
}
}
public static void main(String[] args) {
new TaskManager().run();
}
}
This TaskManager demonstrates the use of LinkedList for managing a queue of tasks. It utilizes the addLast() method to add new tasks to the end of the list and removeFirst() to complete (remove) tasks from the beginning of the list, effectively implementing a First-In-First-Out (FIFO) queue.
Conclusion
Java's LinkedList class, based on the doubly-linked list data structure, offers a flexible and efficient solution for scenarios requiring frequent insertions and deletions at both ends of the list. Its implementation of both List and Deque interfaces makes it versatile enough to be used as a list, queue, or stack.
While LinkedList may not be the best choice for scenarios requiring frequent random access or searching, its unique properties make it an invaluable tool in a Java developer's toolkit. By understanding its strengths and weaknesses, you can make informed decisions about when to use LinkedList in your Java applications.
Remember, the key to efficient programming is choosing the right data structure for your specific needs. LinkedList shines in situations where elements are frequently added or removed from the ends of the list, making it perfect for implementing queues, stacks, and certain types of caches.
As you continue to develop your Java skills, experiment with LinkedList in various scenarios to gain a deeper understanding of its capabilities and limitations. Happy coding! 🚀👨💻👩💻
- Understanding Doubly-Linked Lists
- Java LinkedList: Key Features
- Creating a LinkedList
- Adding Elements to LinkedList
- Removing Elements from LinkedList
- Accessing Elements in LinkedList
- Iterating Through a LinkedList
- LinkedList as a Queue or Stack
- Performance Considerations
- Practical Example: Task Manager
- Conclusion
