Java Reference ยท Collections
The LinkedList class
Reference for java.util.LinkedList: a doubly linked list that implements List and Deque, its costs, queue and stack methods, and when ArrayDeque is better.
LinkedList<E> stores each element in its own node that points to the previous and next node. It implements both List and Deque, so it can act as a list, a queue or a stack. Adding or removing at either end is a constant-time operation, and an insertion through an iterator that is already at the right spot does not shift anything.
The price is that reaching position i means walking the chain from the nearer end, so get(i) costs O(n). Each element also carries two extra references, which makes LinkedList heavier than ArrayList. In practice ArrayList is faster for most list work and ArrayDeque is faster for queues and stacks; LinkedList is worth a look when you remove elements through an iterator in the middle or need null elements in a deque.
LinkedList<String> list = new LinkedList<>(); list.addFirst("a"); list.addLast("z");
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Syntax
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
| Constructor | Description |
|---|---|
LinkedList() |
Empty list. |
LinkedList(Collection<? extends E> c) |
Elements of c in iteration order. |
| Method | Description |
|---|---|
addFirst(e) / addLast(e) / offerFirst / offerLast |
Insert at an end. |
getFirst() / getLast() |
Read an end; throw NoSuchElementException when empty. |
peekFirst() / peekLast() / peek() |
Read an end; return null when empty. |
removeFirst() / removeLast() / pop() |
Remove an end; throw when empty. |
pollFirst() / pollLast() / poll() |
Remove an end; return null when empty. |
push(e) |
Same as addFirst(e). |
descendingIterator() |
Iterator from last to first. |
get(int), set(int, E), add(int, E), remove(int) |
List operations, each O(n). |
Usage notes
- Complexity: ends
O(1); by indexO(n);containsO(n). - Looping with
get(i)is quadratic. Use a for-each loop or an iterator. - Allows
null, sopoll()returningnullcan be ambiguous.ArrayDequeforbidsnullfor that reason. - Prefer
ArrayDequefor plain stacks and queues: it uses less memory and has better cache behavior. - Not synchronized; iterators are fail-fast.
- Stack order:
pushandpopwork at the head, matching the order ofaddFirst. - Java 21:
reversed()returns a reverse-ordered view.
Related
- ArrayList, Deque, ArrayDeque, Queue, Iterator
- Lessons: LinkedList, Queues and deques