Time Complexity for Java ArrayList

java arrays data-structures arraylist abstract-data-type

63,034

The best resource is straight from the official API:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

63,034

Author by

dvanaria

I'm currently working for a telecommunications company in Colorado, doing some software development and systems integration work. I've been interested in programming from an early age, from about when I was 13 or so, programming on Apple II systems at school and eventually at home when my father bought me an Apple IIc. I loved picking up programming books from the public library and just picking out whatever interested me and trying it out first hand. I went on to learn C programming in college, then OpenGL graphics programming, Object Oriented Programming with Java, just about anything new to me I found interesting. Today I still work on my own programming projects (now usually in Python and C++), but I've always had great memories of how much fun it was to discover programming when I was a kid. I'm more interested these days in getting other people interested in computers and programming, maybe trying to inspire other people (especially kids) to get into it. I'm always going back to the basics and really trying to break concepts down so they are accessible and so I understand them better myself. My hope is to one day either write a programming book for kids, that recaptures some of that wonder and excitement, or develop a series of YouTube tutorials that may help newbies pick up programming in a way that is more accessible and easily understood. I think today's biggest barrier to entry in this field of interest is the complexity of today’s systems. It's not like the old days where you turned your computer on and it booted in a few seconds into a BASIC command prompt. Those systems were a lot of fun because you had to pick up programming right from the start in order to really do anything with them. Either way, this site (Stack Overflow) has been a tremendous help to me and a lot of fun to contribute to. Ideally, I would love to feel some kind of expertise with programming in general, and this site is a good step toward getting that kind of experience – the best way to learn anything, I’m convinced, is to teach others, to ask a lot of questions, and help out other people by answering their questions.

Updated on June 01, 2020

Comments

dvanaria almost 4 years
I found other entries for this question that dealt with specific methods, but nothing comprehensive. I'd like to verify my own understanding of the most often used methods of this data structure:

O(1) - Constant Time:
```
isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)
```
O(N) - Linear Time:
```
indexof(x)
clear()
remove(x)
remove(i)
```
Is this correct? Thanks for your help.