Data Structures in Java: List, Stack, Queue and Set

Push 1, 2 and 3 onto a java.util.Stack and print it: you get [1, 2, 3]. Do the same with an ArrayDeque and you get [3, 2, 1]. Both are used as stacks, yet the output is reversed. To avoid this kind of confusion, learn the data structures themselves first, and only then the Java classes that implement them.

A data structure is a way to organize a group of elements together with rules for accessing them: by index, only the most recently added element, only the oldest one, or without duplicates. The basic data structures in Java fall into four kinds: the list, the stack, the queue and the set. The map (dictionary) for key–value pairs stands apart. All of them are implemented in the Collections Framework, whose interfaces and classes are covered in the lesson Java Collections Framework.

List

A list is an ordered sequence of elements in which every element has an index (its position, starting from 0) and the same value may appear more than once. You can read any element by its index, insert a new element at any position, or remove one.

A list is also called a sequence. The abstract list says nothing about how elements are stored. Java has two main implementations: ArrayList keeps elements in an internal array, while LinkedList keeps them in nodes, each referring to the next and the previous element. That difference makes get(i) fast in one and slow in the other — see the performance table in Choosing an implementation.

In the diagram below, the letters A, B, C, A, A are added to a list. The letter A appears three times, which a list allows. Each letter is marked with its index.

Stack (LIFO)

A stack is a data structure that removes elements in Last-In-First-Out (LIFO) order: the element added last comes out first. Only the top element is accessible, and both adding (push) and removing (pop) happen at the same end. A stack allows duplicate elements.

Think of a stack of plates. The top plate was put on last (Last-In), but it is the first one you can take (First-Out). The bottom plate went in first and comes out only after all the plates above it are removed. You cannot pull a plate out of the middle without lifting the ones on top.

The JVM call stack works the same way: the method called last finishes first. Typical uses of a stack are undo history, checking that brackets are balanced, and depth-first search.

Queue (FIFO)

A queue is a data structure that removes elements in First-In-First-Out (FIFO) order: elements are added at the tail (enqueue) and taken from the head (dequeue). As a result, elements leave the queue in the same order in which they were added.

Like a stack, a queue gives no access to an arbitrary element — only to its ends. The difference is which ends: a stack adds and removes at the same end, a queue at opposite ends, just like a line at a checkout or items on a conveyor belt. A queue allows duplicates. Queues are used for work processed in arrival order: print jobs, incoming requests, breadth-first search.

In Java, a queue is described by the Queue interface, and a double-ended queue, which can also work as a stack, by Deque. Its usual implementations are ArrayDeque and LinkedList. A special kind of queue, where the element that comes out first is the one with the highest priority rather than the oldest one, is PriorityQueue.

Set

A set is a collection of elements without duplicates: each element occurs in it at most once, and elements have no indexes. The main operation of a set is a fast check whether it contains an element; adding an element that is already there changes nothing.

A good example of a set is the cars in a parking lot: every car has a unique licence plate, two cars with the same plate cannot be there at once, and the order in which they are parked does not matter.

The abstract set is unordered, but Java also has implementations with an order: HashSet does not guarantee any order, LinkedHashSet keeps insertion order, and TreeSet keeps its elements sorted. How a HashSet decides that two objects are equal depends on equals() and hashCode().

Map (dictionary)

A map (also called a dictionary or associative array) is a data structure that stores key–value pairs: keys are unique, like the elements of a set, and a value is found by its key rather than by an index. A phone book is a map: you look up a number by a name.

In Java, a map is described by the Map interface with the HashMap, LinkedHashMap and TreeMap implementations. Map is a separate branch of the collection hierarchy and does not extend Collection.

Java data structures compared

Java data structures differ in three properties: which elements you can access, whether duplicates are allowed, and whether elements have indexes. These properties tell you which Java interface and class fit a task.

Which implementation to use by default and how fast each class performs its operations in Big O notation is shown in the table Choosing an implementation.

The same data in four structures

Add the same letters A, B, C, A, D to a list, a stack, a queue and a set, and each structure gives the data back in its own way: the list by index, the stack from the end, the queue from the beginning, and the set simply rejects the duplicate. What does this code print?

import java.util.*;

public class DataStructuresDemo {
    public static void main(String[] args) {
        String[] letters = {"A", "B", "C", "A", "D"};

        List<String> list = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        Queue<String> queue = new ArrayDeque<>();
        Set<String> set = new HashSet<>();

        for (String s : letters) {
            list.add(s);     // to the end of the list
            stack.push(s);   // onto the top of the stack
            queue.offer(s);  // to the tail of the queue
            set.add(s);      // the second "A" is ignored
        }

        System.out.println("List: " + list + ", get(3) = " + list.get(3));
        System.out.println("Stack: pop() = " + stack.pop() + ", then " + stack.pop());
        System.out.println("Queue: poll() = " + queue.poll() + ", then " + queue.poll());
        System.out.println("Set: size() = " + set.size() + ", add(\"A\") = " + set.add("A"));
    }
}

Output:

List: [A, B, C, A, D], get(3) = A
Stack: pop() = D, then C
Queue: poll() = A, then B
Set: size() = 4, add("A") = false

The list keeps all five letters, including the duplicate. The stack returns the last added D and C, the queue returns the first added A and B. The set holds four elements: the second A was never added, and another add("A") returns false. On an empty stack or queue, pop() throws NoSuchElementException, while poll() returns null.