Introduction

If "merge" means creating one new collection that physically contains all elements from two existing collections, O(1) is not possible in normal Java collections. Copying n + m elements takes O(n + m). The only way to get something that looks like O(1) is to create a view, wrapper, or linked structure that defers iteration instead of copying data immediately.

A real merge requires touching the elements

Consider the usual merge operations:

1List<Integer> a = List.of(1, 2, 3);
2List<Integer> b = List.of(4, 5, 6);
3
4List<Integer> merged = new ArrayList<>(a);
5merged.addAll(b);

This is not O(1). It copies every element from a and b into a new list, so the cost grows with the size of the input.

The same argument applies to sets, queues, and most other concrete collections. If the result is independent and fully materialized, the runtime cannot stay constant.

O(1) is possible only for a view

You can, however, build a lightweight object that presents two lists as one logical list without copying either of them. Creating that wrapper is O(1) because it stores only references.

1import java.util.AbstractList;
2import java.util.List;
3
4public class ConcatenatedList<T> extends AbstractList<T> {
5    private final List<T> first;
6    private final List<T> second;
7
8    public ConcatenatedList(List<T> first, List<T> second) {
9        this.first = first;
10        this.second = second;
11    }
12
13    @Override
14    public T get(int index) {
15        if (index < first.size()) {
16            return first.get(index);
17        }
18        return second.get(index - first.size());
19    }
20
21    @Override
22    public int size() {
23        return first.size() + second.size();
24    }
25}

Using it:

1List<Integer> a = List.of(1, 2, 3);
2List<Integer> b = List.of(4, 5, 6);
3List<Integer> mergedView = new ConcatenatedList<>(a, b);
4
5System.out.println(mergedView.get(4));
6System.out.println(mergedView.size());

Constructing mergedView is O(1), but iteration over all elements is still O(n + m). You postponed the cost. You did not remove it.

Be honest about what complexity you are measuring

This topic often gets confused because there are several different operations involved:

• creating the merged object
• iterating through the merged contents
• random access into the merged structure
• mutating the merged structure independently

A wrapper can make creation constant time, but it cannot make total traversal constant time. If someone asks for an actual merged collection in O(1), the technically correct answer is no for standard Java collection semantics.

Views come with tradeoffs

A merged view shares underlying storage. That has consequences:

• changes to the original collections may affect the view
• the view cannot easily enforce all behaviors of every collection type
• mutation methods may need custom logic or may be unsupported

That means a view is a good tool when you need read-mostly access or lazy concatenation. It is not a drop-in replacement for a new ArrayList in every design.

Libraries also use the same idea

Third-party libraries sometimes offer concatenated iterables or collection views. Those utilities can make the code shorter, but they do not change the complexity story. They still rely on indirection rather than copying.

So if the interview or design question says O(1) merge, the right follow-up is: "Do you want a copied collection or a view over the originals?"

Linked structures are a special case

If you control the data structure itself, you can sometimes splice two linked lists together in constant time by reconnecting pointers. That is not how Java's standard List interface works in general, and it does not apply to immutable lists or array-backed lists such as ArrayList.

In other words, special data structures can make special operations cheap, but the generic Java collection question still has the same answer: materialized merge is not O(1).

Common Pitfalls

• Claiming addAll is O(1) because the code looks short.
• Confusing constant-time wrapper creation with constant-time full merge.
• Ignoring whether the result must be independent of the original collections.
• Assuming one special linked-list trick applies to all Java collection types.
• Forgetting that views inherit mutation and lifetime issues from the underlying collections.

Summary

• A real independent merge of two Java collections is not O(1).
• 'O(1) is possible only for a wrapper or view that stores references to the originals.'
• A concatenated view defers the cost of traversal instead of eliminating it.
• Be explicit about whether you need copying, random access, mutation, or only lazy iteration.
• For standard Java collections, complexity depends on the actual data structure and the exact merge semantics.