ArrayList linear access time and time access

Question

I am learning Java SE 7 tips. I read an expression about ArrayList :

• Access is ongoing .
• Insert / delete is performed in linear time .

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

Answer 1

Constant time means that there is a hard link, how much time each operator will need.

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

In complexity analysis, we call this the designation of large O , and linear time O(n) , and constant time O(1)

---

The reason for this is:

• Access is an easy access to the array, and it is executed continuously in RAM (for example, on a PC).
• Insert / delete - if it is not in the last element, you need to shift all of the following elements: (Insert requirements shift to the right and delete on the left) - so you really need a linear OP number to perform input / delete (if this is not the last element)

Answer 2

Values:

• constant means that time is always the same, the list length does not matter.

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

• linear means that the larger the list grows, the longer it takes, and in a linear way, for example, to perform a linear operation on a list containing 20 elements. takes twice as much time required for a list with 10 items.

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

  Preliminary assessment: when comparing algorithms, the worst case performance is usually provided, so this means that the required time is less than or equal to linear.

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

The access time is constant, because when the program knows where the first element of the list is and how large each cell is, it can directly get the nth element using simple mathematics, for example:

 element_n_cell = element_1_cell + (cell_size * n) 

Insertions and deletions are more expensive for two reasons:

• When you insert or delete an item at a position, you must shift all of the following items.

• The array cannot be modified, so when creating a new array, ArrayList Java will create an array with a predetermined length s, and it will use the same array until it fits. When you add the (s + 1) th element, the program needs to create a larger array and copy all the elements in the new one.