This content originally appeared on DEV Community and was authored by William
Introduction
In the Java ecosystem, collections are fundamental for managing data efficiently. Two of the most common implementations of the List interface are ArrayList and LinkedList. Both allow storing ordered elements with support for duplicates and index-based access, but they differ significantly in their internal structure and performance. Choosing the right implementation can drastically impact an application’s performance, especially in scenarios involving high data volumes or frequent operations.
Key Differences
- ArrayList: Based on a dynamic array. Elements are stored in contiguous memory locations. When the array reaches its capacity, a new, larger array is created, and elements are copied (resize).
- LinkedList: Based on a doubly linked list. Each element is a node containing the value and references to the previous and next nodes. No contiguous allocation, allowing flexible expansion without massive copying.
Advantages and Disadvantages
ArrayList
- Advantages: Excellent for sequential iteration (via enhanced for-loop or iterator) and random access. More CPU cache-friendly due to memory locality.
- Disadvantages: Insertions and removals at the start or middle require shifting elements, which can be costly for large lists.
LinkedList
- Advantages: Constant-time operations at the start or end. Implements Queue and Deque, making it versatile for queues or stacks.
- Disadvantages: Slow random access due to list traversal. Higher memory usage.
When to Use ArrayList
- Frequent random access: If you need to access elements by index often (e.g., paginating results in an API).
- Read-heavy lists: Applications where the list is populated once and read/iterated multiple times, like configuration lists or query results.
- Fixed or predictable size: When the number of elements is stable, avoiding frequent resizes.
- Real-world examples: Product lists in an e-commerce system (access by ID), search query results, or static data caches. Avoid ArrayList if there are many insertions/removals in the middle, as the O(n) cost can degrade performance.
When to Use LinkedList
- Frequent insertions/removals at ends: Ideal for FIFO (Queue) or LIFO (Stack) scenarios, like task queues.
- Dynamic lists with constant changes: When order matters, but access is sequential or at the ends.
- Versatility as Queue/Deque: Useful for message queues, navigation histories, or asynchronous task processing.
- Real-world examples: Job queues in scheduling systems, media playlists (add/remove songs at ends), or stream processing buffers. Avoid LinkedList for large lists with random access, as the O(n) traversal can be inefficient.
Real-World Example
Let’s apply these concepts in a practical example: a simple REST API in Spring Boot for an e-commerce system. We’ll use:
- ArrayList for storing available products (frequent random access, e.g., lookup by ID).
- LinkedList for a queue of pending orders (FIFO: process in order of arrival, with insertions at the end and removals at the start).
Model Classes
public class Order {
private Long id;
private String description;
public Order(Long id, String description) {
this.id = id;
this.description = description;
}
// Getters and Setters
}
public class Product {
private Long id;
private String name;
public Product(Long id, String name) {
this.id = id;
this.name = name;
}
// Getters and Setters
}
Service Class
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import org.springframework.stereotype.Service;
@Service
public class EcommerceService {
private final List<Product> products = new ArrayList<>();
private final List<Order> orderQueue = new LinkedList<>();
public EcommerceService() {
products.add(new Product(1L, "Product A"));
products.add(new Product(2L, "Product B"));
products.add(new Product(3L, "Product C"));
}
public Product getProductById(Long id) {
int index = id.intValue() - 1; // Simulating mapping
if (index >= 0 && index < products.size()) {
return products.get(index); // Fast access O(1)
}
return null;
}
public void addOrder(Order order) {
orderQueue.addLast(order);
}
public Order processNextOrder() {
if (!orderQueue.isEmpty()) {
return orderQueue.removeFirst();
}
return null;
}
public List<Order> getOrderQueue() {
return new LinkedList<>(orderQueue);
}
}
Controller Class
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.*;
@RestController
@RequestMapping("/ecommerce")
public class EcommerceController {
@Autowired
private EcommerceService service;
@GetMapping("/product/{id}")
public Product getProduct(@PathVariable Long id) {
return service.getProductById(id);
}
@PostMapping("/order")
public String addOrder(@RequestBody Order order) {
service.addOrder(order);
return "Order added to queue!";
}
@GetMapping("/process")
public Order processOrder() {
return service.processNextOrder();
}
@GetMapping("/queue")
public List<Order> viewQueue() {
return service.getOrderQueue();
}
}
- ArrayList for Products: Used for static or semi-static items. The /product/{id} endpoint accesses directly by index (simulated), leveraging O(1) for fast lookups. In a real e-commerce system, this is efficient for large catalogs where users search products by ID or paginate results.
- LinkedList for Orders: Acts as a FIFO Queue. Orders are added at the end (addLast) via POST /order and processed from the start (removeFirst) via GET /process. This ensures order-of-arrival processing, ideal to prevent new orders from jumping ahead. In real systems, this could integrate with a message broker like Kafka, but here it’s a simple in-memory queue.
- Run the application
- Add orders via POST: Use Postman to send JSON { “id”: 1, “description”: “Urgent Order” } to http://localhost:8080/ecommerce/order.
- Process: GET http://localhost:8080/ecommerce/process.
- View queue: GET http://localhost:8080/ecommerce/queue.
- Fetch product: GET http://localhost:8080/ecommerce/product/1.
This content originally appeared on DEV Community and was authored by William