Skip to content
Tutorials Center
My learning

Topics

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.

Java
LinkedList<String> list = new LinkedList<>();
list.addFirst("a");
list.addLast("z");

Try it

Java LinkedList as a list, queue and stack

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.

Java Removing through an iterator

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

Java
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 index O(n); contains O(n).
  • Looping with get(i) is quadratic. Use a for-each loop or an iterator.
  • Allows null, so poll() returning null can be ambiguous. ArrayDeque forbids null for that reason.
  • Prefer ArrayDeque for plain stacks and queues: it uses less memory and has better cache behavior.
  • Not synchronized; iterators are fail-fast.
  • Stack order: push and pop work at the head, matching the order of addFirst.
  • Java 21: reversed() returns a reverse-ordered view.