LinkedList in Java

LinkedList in Java is a class that stores its elements in a doubly linked list. It is used when elements are often added or removed at the beginning or end of a sequence. Each element is kept in a small object called a node, which also holds a link to the previous node and a link to the next node. LinkedList implements both the List and the Deque interfaces, so it can be used as a list, a queue or a stack. In this lesson, you will learn how LinkedList stores data, its methods, and when to use it.

Declaration

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, Serializable

How LinkedList Stores Elements

• The list remembers its first and last node.
• Each node keeps the element plus a prev and a next link.
• Adding or removing at either end only changes a couple of links, so it is fast.
• Getting the element at index i means walking from the nearer end, node by node, so it is slow for large lists.

Features of LinkedList

• Doubly linked: it can be walked forward and backward.
• Maintains insertion order and allows duplicates and null.
• Fast at the ends: addFirst, addLast, removeFirst, removeLast take constant time.
• Slow random access: get(i) must walk through the nodes.
• Not synchronized.

Methods of LinkedList

It also has all the List methods: add, get, set, remove, indexOf and so on.

Example: Using LinkedList as a List

Let's see an example of the end operations.

import java.util.LinkedList;
 
public class LinkedDemo {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Srihitha");
        names.addFirst("Navika");
        names.addLast("Advitha");
        System.out.println(names);
 
        System.out.println("First: " + names.getFirst());
        System.out.println("Last: " + names.getLast());
 
        names.removeFirst();
        names.add(1, "Anamaneni");
        System.out.println(names);
    }
}

[Navika, Srihitha, Advitha]
First: Navika
Last: Advitha
[Srihitha, Anamaneni, Advitha]

Explanation: addFirst puts Navika in front of Srihitha, and addLast puts Advitha at the end. removeFirst deletes Navika. add(1, ...) works too, because LinkedList is a full List.

Example: Using LinkedList as a Queue and a Stack

Because LinkedList implements Deque, the same class can act as a queue (first in, first out) or a stack (last in, first out):

import java.util.LinkedList;
 
public class QueueStack {
    public static void main(String[] args) {
        LinkedList<String> queue = new LinkedList<>();
        queue.offer("Navika");
        queue.offer("Srihitha");
        queue.offer("Advitha");
        System.out.println("Served: " + queue.poll());
        System.out.println("Waiting: " + queue);
 
        LinkedList<String> stack = new LinkedList<>();
        stack.push("page1");
        stack.push("page2");
        stack.push("page3");
        System.out.println("Back to: " + stack.pop());
        System.out.println("History: " + stack);
    }
}

Served: Navika
Waiting: [Srihitha, Advitha]
Back to: page3
History: [page2, page1]

Explanation: offer adds to the end and poll removes from the front, so Navika, who came first, is served first. push adds to the front and pop removes from the front, so the last page pushed is the first popped.

Common Mistakes

Looping with for (int i...) list.get(i) over a big LinkedList. Each get walks from an end, which makes the loop very slow; use a for-each loop.

Choosing LinkedList because "insertion in the middle is O(1)". Finding the middle position is O(n) first.

Calling getFirst() on an empty list. It throws NoSuchElementException; peekFirst() returns null instead.

Practice

1. Easy: Use a LinkedList to model a printing queue: add four documents, print two of them with poll, and show what is left.
2. Harder: Use a LinkedList as a stack to check whether the brackets in a string such as "{[()]}" are balanced.

Key Takeaways