LinkedList

LinkedList is another implementation of the List interface, but where ArrayList is backed by a resizable array, LinkedList is backed by a doubly-linked list — a chain of nodes where every node holds a reference to both the node before it and the node after it. That single structural difference changes almost everything about when you would reach for it.

Creating a LinkedList

Java

import java.util.LinkedList;
import java.util.List;

List<String> names = new LinkedList<>();
names.add("Ravi");
names.add("Meera");
names.add("Ken");

System.out.println(names);

[Ravi, Meera, Ken]

How the Internal Structure Shapes Performance

Every element in a LinkedList is wrapped in a node object that stores the value plus two pointers (previous and next). Adding or removing an element at either end of the list is a constant-time operation — O(1) — because it only involves rewiring a couple of pointers, with no shifting of other elements required.

The same is true for insertion or removal in the middle of the list, but only once you already hold a reference to the node at that position (for example, through a ListIterator). Getting to an arbitrary index, however, is a different story.

Random access is O(n)

A LinkedList has no way to jump directly to index i the way an array can. Calling get(i) or set(i, value) must walk the chain of nodes one link at a time, starting from whichever end is closer, until it reaches the target position. For a list of a million elements, repeatedly calling get(i) in a loop can be dramatically slower than the same loop over an ArrayList.

Fast at the ends, slow in the middle by index

Java

import java.util.LinkedList;

LinkedList<Integer> numbers = new LinkedList<>();
numbers.add(10);
numbers.add(20);
numbers.add(30);

numbers.addFirst(5);   // O(1) — no shifting needed
numbers.addLast(40);   // O(1)

System.out.println(numbers);
System.out.println(numbers.get(2)); // O(n) — must traverse from an end

[5, 10, 20, 30, 40]
20

LinkedList Implements List AND Deque

Unlike ArrayList, LinkedList doesn't just implement List — it also implements Deque (double-ended queue), which means it comes with a full set of methods for adding, removing, and peeking at both ends: addFirst, addLast, removeFirst, removeLast, peekFirst, and peekLast. That dual identity is exactly why LinkedList can be used as a stack or a queue, a technique covered in detail on the Queue & Deque and Stack pages.

ArrayList vs LinkedList

Aspect	ArrayList	LinkedList
Backing structure	Resizable array	Doubly-linked list of nodes
Access by index (get/set)	O(1)	O(n) — must traverse
Insert/remove at the ends	O(1) amortized	O(1)
Insert/remove in the middle	O(n) — elements must shift	O(n) to find the spot, O(1) once there
Memory overhead per element	Low — just the array slot	Higher — each node stores 2 extra references
Implements	List, RandomAccess	List, Deque, Queue

Tip

ArrayList is the right default for the vast majority of use cases — most programs read far more often than they insert or remove in the middle, and ArrayList's cache-friendly contiguous memory layout tends to outperform LinkedList even for many insertion workloads. Reach for LinkedList specifically when your program repeatedly adds and removes elements at the front or back of a large list — for example, implementing a queue that both enqueues and dequeues frequently.

Note

Because a LinkedList doesn't implement the RandomAccess marker interface, well-written generic code that traverses a List will typically prefer an iterator over an indexed for-loop when it can't assume the underlying implementation — iterating a LinkedList with an iterator is O(n) overall, while iterating it with get(i) in a loop is O(n²).

Backed by a doubly-linked list of nodes, not an array
O(1) insertion and removal at both ends
O(n) access by index — avoid get(i) in tight loops
Implements both List and Deque, so it can act as a stack or queue
ArrayList remains the better general-purpose default