ArrayList Constant-time and Linear Time Access

Question

I have been learning the tips of Java SE 7. I have read a statement about ArrayList:

• Access is performed in constant time.
• Insertion/deletion is performed in linear time.

I would like to know what is constant and linear time access?

Solution 1

constant time means there is a hard bound how much time each op will take to perform.

Linear time means the longer the ArrayList is (more object it contains) the longer time the op will take. The connection is linear, i.e. time(op) <= CONST * #elements

In complexity analysis, we refer it as big O notation and linear time is O(n), and constant time is O(1)

---

The reason for it is:

• Access is plain array access, and it is done in constant time in RAM machine (such as out PCs).
• Insertion/Deletion - if it is not in the last element, requires shifting all following elements: (Insertion requries shifting to the right, and deletion to the left) - thus you actually need a linear number of OPs to perform insertion/deletion (unless it is the last element)

Solution 2

The meanings are:

• constant means that the time is always the same, it doesn't matter the length of the List.

  [constant time is also called O(1) in Big-O notation]

• linear means that the more the List grows, the longer is the time, but in a linear way, so for example to perform a linear operation on a list that contains 20 elements it will take two times the time needed for a list with 10 elements.

  [linear time is also called O(n) in Big-O notation]

  A precisation: when comparing algorithms is normally provided the worst case performance, so it means that the time needed is less or equal than linear.

In your case the implementation of the List is based on arrays (so the name ArrayList) like this:

The access time is constant because when the program knows where the first element of the list is and how big is every cell, it can directly get the n-th element using simple math like:

element_n_cell = element_1_cell + (cell_size * n)

Insertions and deletions are more time-expensive for two reasons:

1. When you insert or delete an element in a position, all the following elements need to be shifted.

2. An array can't be resized, so when you instantiate a new ArrayList, Java will create an array with a pre-defined length s, and it will use the same array as long as it fits. When you add the (s+1)-th element, the program needs to create a bigger array and copy all the elements in the new one.

Comments

[amit]

This is not the reason for linear time. Though it explains only worst case, dynamic arrays have linear rime armotized complexity as well, because inserting or deleting element in the middle requires shifting all following elements to the right or left. This makes it O(n) for armotized analysis as well, not only worst case

[enrico.bacis]

Yes, you're right! I was thinking about appending :D I'll fix it! Thanks