Deque and the List Family in Java

You have already seen how a regular Queue works: things go in at the back and come out from the front, just like a line of people waiting. You have also seen PriorityQueue and how comparators work. Now it is time to go deeper into two of the most powerful parts of the Java collections framework: the Deque interface and the List family.

By the end of this article you will understand every method on Deque, why ArrayDeque beats the old Stack class, how List differs from Queue, every operation ArrayList provides, the infamous remove pitfall that trips up experienced developers, how ListIterator lets you walk a list backward, and exactly why Vector and Stack still exist even though modern Java rarely needs them.

---

The Deque Interface: A Queue That Works from Both Ends

A regular queue is strict about one thing: you add at the back and remove from the front. That is the whole rule. A Deque breaks that rule on purpose.

Deque stands for double ended queue. The name is pronounced "deck", like a deck of cards. The idea is simple: you can add an element at the front or the back, and you can remove an element from the front or the back. Both ends are fully open. That one small change makes Deque powerful enough to replace both Queue and Stack in modern Java.

Why Both Ends Matter

Think about a browser's history. When you visit a new page it goes to the back. When you hit the back button you are pulling from the most recently visited page, which is the front of the "back history" list. When you navigate forward you are pulling from a different end. A Deque models this naturally because you have full control over both sides.

The 12 Methods of Deque

Deque adds exactly twelve new methods on top of everything Queue already provides. These twelve methods fall into three categories: insert, remove, and examine. Each category has four methods: one for the front that throws on failure, one for the front that returns a safe value, one for the back that throws on failure, and one for the back that returns a safe value.

Here is the complete picture:

Operation	Front throws exception	Front returns null/false	Back throws exception	Back returns null/false
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

The pattern is consistent across all three categories. If you use add, remove, or get, you get exceptions on failure. If you use offer, poll, or peek, you get null or false instead of an exception. That is the same pattern you already learned in the regular Queue, just extended to both ends.

What Happens to the Old Queue Methods?

You might wonder what happens to the existing Queue methods like add, offer, poll, remove, and peek when you use a Deque. The answer is that they map directly to specific Deque methods. This is by design, so that a Deque can always be used as a plain Queue.

add internally calls addLast. offer internally calls offerLast. poll internally calls pollFirst. remove internally calls removeFirst. peek internally calls peekFirst.

This means adding goes to the back and removing comes from the front, which is exactly the normal queue behavior. If you use only the old Queue methods on a Deque, it behaves identically to a regular Queue. The new methods are only needed when you specifically want to work with the other end.

Using Deque as a Stack

Here is the more surprising use case. Because Deque allows you to add and remove from the front, you can use it as a stack. A stack follows last in first out: whatever you pushed last comes out first.

To use a Deque as a stack, always add at the front with addFirst and always remove from the front with removeFirst. The element you added most recently is sitting at the front, so removing from the front gives you last in first out behavior.

Deque even provides two dedicated methods that make this explicit: push and pop. Under the hood, push is just an alias for addFirst and pop is just an alias for removeFirst. There is no magic, just a friendlier name that makes your intent clear to anyone reading the code.

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeDemo {
    public static void main(String[] args) {

        // Using Deque as a Queue (FIFO behavior)
        Deque<Integer> queue = new ArrayDeque<>();
        queue.addLast(10);   // adds to back
        queue.addLast(20);
        queue.addLast(30);

        // Removes from front: 10 comes out first
        System.out.println(queue.pollFirst()); // 10
        System.out.println(queue.pollFirst()); // 20

        // Using Deque as a Stack (LIFO behavior)
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(100);  // same as addFirst(100)
        stack.push(200);  // same as addFirst(200)
        stack.push(300);  // same as addFirst(300)

        // Removes from front: 300 comes out first (last pushed)
        System.out.println(stack.pop());  // 300
        System.out.println(stack.pop());  // 200
        System.out.println(stack.peek()); // 100, just looks, does not remove
    }
}

---

ArrayDeque: The Concrete Implementation

Deque is an interface. It cannot be instantiated on its own. The class you use in practice is ArrayDeque, which provides a concrete implementation of all Deque methods.

Time Complexity of ArrayDeque

Inserting at either the front or the back takes amortized O(1) time. The word amortized is important here. Most insertions truly are O(1). But occasionally, when the internal array is full, ArrayDeque has to create a bigger array and copy all existing elements into it. That one copy operation is O(n). Because it happens rarely and the cost is spread across all the insertions that preceded it, the average cost per insertion is still O(1). With the default constructor it starts with room for 16 elements; while it is small (under 64) it roughly doubles when full, and after that it grows by 50%.

Deleting from either the front or the back is always O(1). There is no shifting of elements because you are always operating at the boundary.

Examining (peeking) the front or back element is always O(1) as well.

Space complexity is O(n) for n elements.

Is ArrayDeque Thread Safe?

No, ArrayDeque is not thread safe. If multiple threads are accessing the same ArrayDeque simultaneously, one thread might be adding while another is removing, leaving the structure in an inconsistent state. Do not use ArrayDeque in a multithreaded environment without external synchronization.

The thread safe alternative is ConcurrentLinkedDeque. It provides all the same methods as ArrayDeque but handles concurrent access correctly. If your Deque is being shared between threads, switch to ConcurrentLinkedDeque.

import java.util.concurrent.ConcurrentLinkedDeque;

ConcurrentLinkedDeque<Integer> safeDeque = new ConcurrentLinkedDeque<>();
safeDeque.addFirst(1);
safeDeque.addLast(2);
// safe to use from multiple threads

ArrayDeque Properties at a Glance

ArrayDeque maintains insertion order. Whatever order you add elements is the order they will be retrieved if you use consistent methods. It does not allow null elements. Attempting to add null will throw a NullPointerException. Duplicate elements are allowed.

Property	ArrayDeque
Thread safe	No
Insertion order maintained	Yes
Null elements allowed	No
Duplicates allowed	Yes
Thread safe alternative	ConcurrentLinkedDeque

---

The List Interface: Collections with Index Access

Now let us shift to the List family. You might wonder: a Queue is also a collection of objects, and it allows duplicates. So what makes List different?

The key difference is access. In a Queue, you can only add at the start or end, and you can only remove from the start or end. You cannot reach into the middle and grab element number three without going through elements zero, one, and two first. A List is different because it is built on top of an indexed array structure. You can insert at index five, remove from index two, or read what is sitting at index seven, all in one operation.

A List is an ordered collection of objects in which duplicate values can be stored, and where data can be inserted, removed, or accessed from any position using an index that starts at zero.

What List Adds on Top of Collection

List inherits everything from the Collection interface, which means add, remove, contains, size, isEmpty, and all the rest. But it also introduces methods that only make sense with indexed access.

add(int index, E element) inserts an element at the given index. If there is already an element at that position, it does not replace it. Instead it shifts that element and everything to its right one position to the right to make room. Think of it like inserting a new card into the middle of a hand of cards: everyone to the right scoots over.

addAll(int index, Collection c) does the same thing but inserts an entire collection starting at the given index. Everything that was at that index and beyond shifts right to accommodate the new elements.

set(int index, E element) replaces the element at the given index with the new element. Unlike add, it does not shift anything. The old element is overwritten and gone. This is a critical distinction that confuses many beginners.

get(int index) returns the element at the given index without removing it.

remove(int index) removes the element at the given index. Everything to the right of the removed element shifts left to fill the gap.

indexOf(Object o) returns the index of the first occurrence of the given object in the list. If the object is not in the list, it returns minus one.

lastIndexOf(Object o) returns the index of the last occurrence. This matters because List allows duplicates.

sort(Comparator c) sorts the list using the comparator you provide. You already learned how comparators work, so you can pass any ordering you want here.

replaceAll(UnaryOperator operator) applies a function to every element in the list and replaces each element with the result. It uses a functional interface, so you can pass a lambda expression.

subList(int fromIndex, int toIndex) returns a view of the portion of the list between fromIndex (inclusive) and toIndex (exclusive). Any changes you make to the subList are reflected in the original list. This is not a copy. It is a window into the same data.

listIterator() returns a special iterator with extra capabilities. We will cover this in detail shortly.

---

ArrayList: The Workhorse of the List Family

ArrayList is the most commonly used List implementation. It is backed by a plain Java array internally. When you create an ArrayList and start adding elements, it manages a raw Object[] array for you and handles all the resizing automatically.

How ArrayList Resizes

When you create an ArrayList without specifying a capacity, it starts with an internal array of capacity 10 the first time you add an element. When you add enough elements to fill that array and then try to add one more, ArrayList creates a new array that is 1.5 times the size of the old one, copies all existing elements into it, and continues. The formula looks like this:

// Inside ArrayList's grow method:
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // adds half again, so 1.5x growth

The capacity sequence looks like: 10, 15, 22, 33, 49, and so on. Each resize is expensive because copying takes O(n) time, but because the array grows by a significant percentage each time, resizing happens less and less frequently as the list grows. The amortized cost per insertion is O(1).

ArrayList in Practice: All the Key Methods

import java.util.ArrayList;
import java.util.List;

public class ArrayListDemo {
    public static void main(String[] args) {

        List<Integer> list = new ArrayList<>();

        // add(index, element) inserts and shifts right
        list.add(0, 100); // [100]
        list.add(1, 200); // [100, 200]
        list.add(2, 300); // index 2 == size, so it appends: [100, 200, 300]
        // list.add(5, 1); // index > size: IndexOutOfBoundsException
        list.add(2, 999); // inserts at index 2, shifts 300 right: [100, 200, 999, 300]

        // addAll(index, collection) inserts entire collection, shifts rest right
        List<Integer> extra = new ArrayList<>();
        extra.add(400);
        extra.add(500);
        extra.add(600);
        list.addAll(2, extra); // inserts 400,500,600 at index 2
        // result: [100, 200, 400, 500, 600, 999, 300]

        // replaceAll applies a function to every element
        list.replaceAll(value -> value * -1);
        // every element is now negated

        // sort using a comparator (ascending order)
        list.sort((a, b) -> Integer.compare(a, b));

        // get returns element at index without removing
        Integer element = list.get(2); // the element at index 2

        // set REPLACES element at index, does NOT shift
        list.set(2, -4000); // index 2 is now -4000, old value is gone

        // remove(int index) removes by position, shifts left
        list.remove(2); // removes element at index 2

        // indexOf returns first occurrence, -1 if not found
        int firstOccurrence = list.indexOf(-200);

        // lastIndexOf returns last occurrence
        int lastOccurrence = list.lastIndexOf(-200);

        System.out.println("Final list: " + list);
    }
}

The Critical Difference Between add and set

This trips up beginners constantly. When you call add(int index, E element), the existing element at that index is not lost. It shifts to the right. When you call set(int index, E element), the existing element at that index is replaced and gone.

If your list is [100, 200, 300] and you call list.add(1, 999), you get [100, 999, 200, 300]. The 200 moved over.

If your list is [100, 200, 300] and you call list.set(1, 999), you get [100, 999, 300]. The 200 is gone.

---

The remove Pitfall: Index vs Object

This is one of the most common bugs in Java code and it comes up frequently in interviews. The List interface has two overloaded remove methods:

• remove(int index) removes the element at the given index position
• remove(Object o) removes the first occurrence of the given object

When you have a List<Integer> and you call list.remove(1), Java sees the argument as a primitive int, so it calls remove(int index) and removes the element at position 1. If you wanted to remove the value 1 from the list, that is not what happened.

import java.util.ArrayList;
import java.util.List;

public class RemovePitfall {
    public static void main(String[] args) {

        List<Integer> numbers = new ArrayList<>();
        numbers.add(10); // index 0
        numbers.add(20); // index 1
        numbers.add(30); // index 2

        // You want to remove the VALUE 20.
        // This DOES NOT do what you think:
        // numbers.remove(20);
        // Java would try to remove the element at INDEX 20.
        // Since size is 3, this throws IndexOutOfBoundsException!

        // numbers.remove(1) would remove INDEX 1 (which is 20 here):
        // it looks right, but it removes by position, not by value.

        // The correct way to remove by VALUE is to wrap in Integer.valueOf:
        numbers.remove(Integer.valueOf(20));
        // Now Java calls remove(Object o) and finds and removes the value 20.

        System.out.println(numbers); // [10, 30]
    }
}

The fix is always Integer.valueOf(theValue) when you want to remove by value from a List<Integer>. Wrapping the value in Integer.valueOf forces Java to call remove(Object o) instead of remove(int index).

---

ListIterator: Walking a List in Both Directions

The regular Iterator interface lets you walk a collection forward with hasNext and next, and remove elements with remove. That is all it does. ListIterator is a child of Iterator that adds several more capabilities.

The most important addition is backward traversal. ListIterator exposes hasPrevious() and previous() so you can walk a list from back to front. It also adds nextIndex() which tells you the index of the element that next() would return, and previousIndex() which tells you the index of the element that previous() would return.

Beyond navigation, ListIterator adds set(E element) which replaces the last element returned by either next() or previous(), and add(E element) which inserts an element at the current cursor position.

Understanding the Cursor Position

The ListIterator cursor sits between elements, not on them. When you call next(), the cursor moves past the next element and returns it. When you call previous(), the cursor moves back past the previous element and returns it. The add method inserts immediately before what next() would return and immediately after what previous() would return. A subsequent call to next() is not affected by the insertion, but a call to previous() would return the newly inserted element.

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class ListIteratorDemo {
    public static void main(String[] args) {

        List<Integer> numbers = new ArrayList<>();
        numbers.add(-600);
        numbers.add(-500);
        numbers.add(-300);
        numbers.add(-200);
        numbers.add(-100);

        // Forward traversal
        ListIterator<Integer> forward = numbers.listIterator();
        while (forward.hasNext()) {
            int nextIndex = forward.nextIndex();
            int previousIndex = forward.previousIndex();
            int value = forward.next();
            System.out.println("Index coming: " + nextIndex
                + ", index behind: " + previousIndex
                + ", value: " + value);

            // When we reach -200, insert a new element between -200 and -100
            if (value == -200) {
                forward.add(-150); // inserts before -100, after -200
                // next() will still return -100, not -150
            }
        }
        // numbers is now: [-600, -500, -300, -200, -150, -100]

        // Backward traversal: start cursor at the end by passing list size
        ListIterator<Integer> backward = numbers.listIterator(numbers.size());
        while (backward.hasPrevious()) {
            int value = backward.previous();
            System.out.print(value + " ");

            // Replace -100 with -50 while going backward
            if (value == -100) {
                backward.set(-50); // replaces last returned element
            }
        }
        System.out.println();
        // numbers is now: [-600, -500, -300, -200, -150, -50]
    }
}

To start a backward traversal from the very end, you pass the list size to listIterator(int index). That positions the cursor at the end so the first call to previous() returns the last element.

---

ArrayList Time Complexity and Properties

Here is a clear summary of ArrayList performance:

Operation	Time Complexity	Why
Add at end	O(1) amortized	Simple array write; occasional resize is O(n) but rare
Add at index	O(n)	Must shift all elements to the right of the index
Remove at index	O(n)	Must shift all elements to the left of the index
Get by index	O(1)	Direct array access by position
Search by value	O(n)	Must traverse to find the value
Resize	O(n)	Creates new array and copies all elements

Space complexity is O(n) for n stored elements.

ArrayList is not thread safe. It maintains insertion order. It allows null elements and duplicates. The thread safe alternative is CopyOnWriteArrayList, which creates a fresh copy of the internal array on every mutating operation so that readers always see a consistent snapshot.

---

LinkedList: Both a List and a Deque

LinkedList is the most versatile class in the collections framework because it implements both the List interface and the Deque interface. That means a single LinkedList object can perform indexed operations like get(2) and add(3, element) and also perform Deque operations like addFirst, addLast, removeFirst, and removeLast.

The internal data structure is a doubly linked list. Each node holds the element, a pointer to the next node, and a pointer to the previous node. There is no array involved, which means there is no resizing and no shifting of elements when you insert or delete.

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {

        LinkedList<Integer> list = new LinkedList<>();

        // Using Deque capabilities
        list.addLast(200);  // [200]
        list.addLast(300);  // [200, 300]
        list.addLast(400);  // [200, 300, 400]
        list.addFirst(100); // [100, 200, 300, 400]

        System.out.println(list.getFirst()); // 100

        // Using List capabilities: indexed access
        // list is [100, 200, 300, 400]
        list.add(1, 150); // inserts 150 at index 1: [100, 150, 200, 300, 400]

        System.out.println(list.get(1)); // 150
        System.out.println(list.get(2)); // 200
    }
}

LinkedList Time Complexity

Inserting or removing at the front or back is O(1) because you just rewire a couple of pointers. Inserting or removing at a specific index requires two steps: first traverse to that index in O(n), then do the actual pointer rewiring in O(1). So the overall cost for indexed insertion or deletion is O(n).

Searching by value requires traversal from the head, so it is O(n).

The advantage over ArrayList shows up when you are inserting and removing frequently in the middle of the list. ArrayList must shift potentially thousands of elements; LinkedList just adjusts a few pointers. On the other hand, ArrayList wins for random reads because get(i) is O(1) in ArrayList and O(n) in LinkedList.

LinkedList is not thread safe. It maintains insertion order. It allows null elements and duplicates.

Property	LinkedList
Thread safe	No
Insertion order maintained	Yes
Null elements allowed	Yes
Duplicates allowed	Yes

---

ArrayList vs LinkedList: When to Use Which

Use ArrayList as your default. It is simpler, uses less memory per element, and is faster for random reads. Use LinkedList only when you are building something that specifically needs both List and Deque behavior from the same object, or when you are doing frequent insertions and deletions at both ends and rarely reading by index.

Operation	ArrayList	LinkedList
Random read by index	O(1)	O(n)
Add at end	O(1) amortized	O(1)
Add at front	O(n)	O(1)
Add at index	O(n)	O(n)
Remove by index	O(n)	O(n)
Memory per element	Low (one reference)	High (three references: value, next, prev)

---

Vector: The Synchronized ArrayList

Vector is almost identical to ArrayList. It is a resizable array that maintains insertion order, allows nulls and duplicates, and supports all the same indexed operations. The one difference is that every single method in Vector is synchronized. Adding, removing, getting, searching: each operation acquires a lock before proceeding and releases it after.

That synchronization makes Vector thread safe, but at a cost. Even in a single threaded program where there is absolutely no contention, Vector is slower than ArrayList because it pays the overhead of acquiring and releasing locks on every call.

import java.util.Vector;

Vector<String> vector = new Vector<>();
vector.add("first");   // synchronized
vector.add("second");  // synchronized
vector.get(0);         // synchronized
vector.remove(0);      // synchronized

In modern Java, if you need a thread safe list, the preferred approach is to use Collections.synchronizedList(new ArrayList<>()) for simple cases or CopyOnWriteArrayList for cases where reads far outnumber writes. Vector exists mainly for backward compatibility with older Java code.

Property	Vector
Thread safe	Yes (all methods synchronized)
Insertion order maintained	Yes
Null elements allowed	Yes
Duplicates allowed	Yes
Thread safe version	It is already thread safe

---

Stack: The Legacy Stack Class

Stack extends Vector. Because it extends Vector, Stack inherits all of Vector's synchronized methods and is therefore thread safe. It represents a last in first out collection with push, pop, and peek operations.

The obvious question is: why does Stack exist separately if Deque with addFirst and removeFirst already implements stack behavior? The answer is mostly historical. Stack has been in Java since version 1.0, long before Deque was introduced. It was the only stack option back then.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);  // synchronized
stack.push(2);
stack.push(3);
System.out.println(stack.pop());  // 3 (synchronized)
System.out.println(stack.peek()); // 2 (synchronized)

Because Stack extends Vector, every push and pop acquires a lock. That makes it safe for multiple threads but slower than necessary in single threaded code.

There is also a design problem. Because Stack extends Vector, a caller can call stack.add(0, element) which inserts at the bottom of the stack, completely bypassing the LIFO contract. The class is technically broken from an object oriented design standpoint because its superclass exposes operations that violate the subclass's purpose.

In modern Java, use ArrayDeque as your stack. It is faster than Stack, has no locking overhead in single threaded code, and its API makes it clear what you are doing. If you specifically need a thread safe stack, then Stack or ConcurrentLinkedDeque are your options.

Property	Stack
Thread safe	Yes (inherits Vector synchronization)
Insertion order maintained	Yes, but access order is LIFO
Null elements allowed	Yes
Duplicates allowed	Yes
Modern replacement	ArrayDeque (or ConcurrentLinkedDeque for threads)

Check yourself

1. What does Deque add over Queue? Which Deque methods do add, offer, poll, remove, peek map to?
2. How do you use a Deque as a stack?
3. Is ArrayDeque thread safe? What is the alternative? Does it allow null?
4. What is the difference between add(index, e) and set(index, e) on a List?
5. How does ArrayList grow when it is full?
6. What does ListIterator add over Iterator?
7. When is LinkedList better than ArrayList, and when is it worse?
8. What is the difference between ArrayList, Vector, and Stack? What should you use as a stack today?

Answers

1. Insert, remove and examine at both ends (addFirst, offerLast, pollFirst, peekLast, ...). add→addLast, offer→offerLast, poll→pollFirst, remove→removeFirst, peek→peekFirst.
2. push (= addFirst) and pop (= removeFirst), with peek to look at the top.
3. No; ConcurrentLinkedDeque. No, null throws NullPointerException.
4. add inserts and shifts later elements right; set replaces the element at that index.
5. It creates a new array 1.5 times the old size and copies the elements over (capacity 10, 15, 22, 33, ...).
6. Backward traversal (hasPrevious, previous), index methods (nextIndex, previousIndex), and set/add at the cursor.
7. Better for adding or removing at the ends (O(1)); worse for reading by index (O(n) versus O(1)).
8. Vector is a synchronized ArrayList; Stack extends Vector. Both lock on every call. Use ArrayDeque as a stack.