Java中ArrayList.subList(startIndex, endIndex)方法的时间复杂度是多少？

Great question—this is one of those easy-to-mix-up details, especially with conflicting info floating around about different List implementations. Let's clear this up straight away:

The Short Answer #

ArrayList.subList(start, end) runs in O(1) time, regardless of how large your original ArrayList is (even with 1M elements!).

Why It's O(1) #

Here's the key detail most people overlook: the subList method doesn't create a new copy of elements from your original list. Instead, it returns an instance of an internal SubList class that acts as a view onto the original ArrayList. This view only tracks a few pieces of data:

• A reference to the original ArrayList
• The start and end indices you passed in
• A modification count to catch concurrent changes between the original list and the sublist

Every operation you perform on the sublist (like get(), set(), or size()) delegates directly to the original ArrayList, with quick checks to ensure you're only accessing elements within the sublist's bounds. No elements are copied during the subList call itself—just a handful of object initializations that take constant time, no loops over n elements required.

A Common Point of Confusion #

You mentioned finding answers about LinkedList's subList. For context, LinkedList's subList is also O(1) for the same reason (it returns a view, not a copy). The confusion might stem from operations on the sublist later—for example, iterating through a LinkedList sublist can be slower than an ArrayList sublist because of LinkedList's node-based structure—but the subList method call itself is still constant time for both implementations.

One Important Caveat #

If you later convert the sublist to a new ArrayList (like new ArrayList<>(myList.subList(start, end))), that operation will be O(n), where n is the size of the sublist. But that's because you're explicitly copying elements, not because the subList method itself is expensive.

内容的提问来源于stack exchange，提问作者Grace F.