Java LinkedList: A Complete Guide with Examples and Exercises
In Java, the LinkedList class is part of the java.util package and provides a doubly-linked list implementation of the List and Deque interfaces. Unlike arrays and ArrayList, which store elements in contiguous memory locations, a LinkedList stores each element (node) separately, with a reference to the next (and possibly previous) node. This structure provides benefits in terms of efficient insertion and deletion operations, especially when working with large datasets. This guide will help you understand the LinkedList class, its methods, and provide exercises to reinforce your learning.
Table of Contents
- Introduction to LinkedList
- Creating and Initializing a LinkedList
- Commonly Used LinkedList Methods
- Iterating Over a LinkedList
- LinkedList vs ArrayList
- LinkedList as a Queue and Stack
- Exercises
1. Introduction to LinkedList
A LinkedList is a collection that is made up of nodes, where each node contains:
- A data element
- A reference (link) to the next node in the list
This linked structure provides several advantages:
- Efficient Insertions and Deletions: Adding or removing elements from the beginning or middle of a
LinkedListis more efficient than doing the same with anArrayList, especially for large lists. - Memory Efficiency: Nodes in a linked list can be scattered in memory (non-contiguous), so it avoids memory waste that might occur in an array with unused capacity.
However, accessing elements by index is slower in a LinkedList compared to an ArrayList since you need to traverse the list from the start or end.
Types of LinkedLists:
- Singly Linked List: Each node contains a reference to the next node.
- Doubly Linked List: Each node contains a reference to both the next and the previous nodes.
Java’s LinkedList class implements a doubly linked list, making it more versatile.
2. Creating and Initializing a LinkedList
You can create and initialize a LinkedList in various ways. Below are some of the most common methods.
Example 1: Creating an Empty LinkedList
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Create an empty LinkedList of Strings
LinkedList<String> fruits = new LinkedList<>();
// Adding elements to the LinkedList
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
// Printing the LinkedList
System.out.println(fruits);
}
}Example 2: Creating a LinkedList from Another Collection
You can initialize a LinkedList from an existing collection, such as an ArrayList.
import java.util.ArrayList;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
// Creating an ArrayList and initializing it with elements
ArrayList<String> list = new ArrayList<>();
list.add("Red");
list.add("Green");
list.add("Blue");
// Creating a LinkedList from an ArrayList
LinkedList<String> colors = new LinkedList<>(list);
System.out.println(colors);
}
}3. Commonly Used LinkedList Methods
Java’s LinkedList class comes with several useful methods that make it versatile for various operations. Here are some commonly used methods:
- 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 (same as
add). - remove(): Removes the first element of the list.
- removeFirst(): Removes the first element of the list.
- removeLast(): Removes the last element of the list.
- getFirst(): Retrieves the first element.
- getLast(): Retrieves the last element.
- peek(): Retrieves the first element without removing it.
- size(): Returns the number of elements in the list.
- contains(E e): Checks if the list contains the specified element.
Example: Using LinkedList Methods
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> animals = new LinkedList<>();
// Add elements
animals.add("Cat");
animals.add("Dog");
animals.add("Elephant");
// Add an element at the first position
animals.addFirst("Lion");
// Add an element at the last position (same as add)
animals.addLast("Tiger");
// Retrieve first and last elements
System.out.println("First animal: " + animals.getFirst());
System.out.println("Last animal: " + animals.getLast());
// Remove first and last elements
animals.removeFirst();
animals.removeLast();
// Print final list
System.out.println("Animals: " + animals);
}
}4. Iterating Over a LinkedList
There are several ways to iterate over the elements of a LinkedList:
Example 1: Using a for Loop
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> colors = new LinkedList<>();
colors.add("Red");
colors.add("Green");
colors.add("Blue");
// Iterate using a for loop
for (int i = 0; i < colors.size(); i++) {
System.out.println(colors.get(i));
}
}
}Example 2: Using a for-each Loop
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> colors = new LinkedList<>();
colors.add("Red");
colors.add("Green");
colors.add("Blue");
// Iterate using for-each loop
for (String color : colors) {
System.out.println(color);
}
}
}Example 3: Using Java 8 forEach Method
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<String> colors = new LinkedList<>();
colors.add("Red");
colors.add("Green");
colors.add("Blue");
// Iterate using forEach method
colors.forEach(color -> System.out.println(color));
}
}5. LinkedList vs ArrayList
LinkedList and ArrayList are both implementations of the List interface in Java, but they have different characteristics and use cases. Here are some important differences between them:
| Feature | LinkedList | ArrayList |
|---|---|---|
| Memory Usage | Uses more memory due to storing two pointers (next and previous) for each element. | Memory-efficient as it stores data contiguously. |
| Access Time | Slower for accessing elements by index due to traversal. | Faster for accessing elements by index (constant time). |
| Insertion/Deletion | Faster for adding/removing elements from the beginning or middle of the list. | Slower for adding/removing elements, especially in the middle. |
| Resizing | Does not require resizing as it is dynamically linked. | Resizes dynamically as the size increases, which can cause performance hits. |
| Use Case | Preferred when frequent insertions/deletions are required. | Preferred when fast access to elements is required. |
6. LinkedList as a Queue and Stack
LinkedList implements both the Queue and Deque interfaces, making it an ideal choice for queue and stack operations.
Queue Operations
A queue follows the FIFO (First In, First Out) principle. Elements are added at the end and removed from the front.
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
// Add elements to the queue
queue.offer("Alice");
queue.offer("Bob");
queue.offer("Charlie");
// Remove elements from the queue
System.out.println("Removed from queue: " + queue.poll());
System.out.println("Queue after removal: " + queue);
}
}Stack Operations
A stack follows the LIFO (Last In, First Out) principle. Elements are added and removed from the top of the stack.
import java.util.LinkedList;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Stack<String> stack = new Stack<>();
// Push elements onto the stack
stack.push("A");
stack.push("B");
stack.push("C");
// Pop elements from the stack
System.out.println("Popped from stack: " + stack.pop());
System.out.println("Stack after pop: " + stack);
}
}7. Exercises
Exercise 1: Create a LinkedList of Integers
Write a program that:
- Creates a
LinkedListof integers. - Adds 5 numbers to the list.
- Removes the first and last elements.
- Prints the remaining list.
Exercise 2: Implement a Queue with Linked
List
Write a program that:
- Implements a queue using a
LinkedList. - Enqueues 3 elements and dequeues 2 elements, printing the queue each time.
Exercise 3: Check for Element in LinkedList
Write a program that:
- Creates a
LinkedListof strings. - Checks if a specific string is present in the list and prints a message accordingly.
Solution for Exercise 1
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> numbers = new LinkedList<>();
// Add elements
numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);
numbers.add(50);
// Remove first and last elements
numbers.removeFirst();
numbers.removeLast();
// Print the list
System.out.println("Remaining numbers: " + numbers);
}
}Conclusion
The LinkedList class in Java is a versatile and powerful tool for managing collections of elements. Its dynamic, node-based structure allows for efficient insertions and deletions, especially when the collection size changes frequently. By practicing with the examples and exercises in this guide, you’ll become proficient in using LinkedList in various situations, including as a queue and stack.
