ArrayList

Question 1

What is a Array?

Answer 1

Arrays hold values of the same type at contiguous memory locations.

Question 2

What are we concerned about in a Array?

Answer 2

The position/index of an element and the element itself.

Question 3

Advantages

Answer 3

-Store multiple elements of the same type with one single variable name
-Accessing elements is fast as long as you have the index, as opposed to linked lists where you have to traverse from the head.

Question 4

Disadvanteges

Answer 4

-Addition and removal of elements into/from the middle of an array is slow because the remaining elements need to be shifted to accommodate the new/missing element. An exception to this is if the position to be inserted/removed is at the end of the array.
-For certain languages where the array size is fixed, it cannot alter its size after initialization. If an insertion causes the total number of elements to exceed the size, a new array has to be allocated and the existing elements have to be copied over. The act of creating a new array and transferring elements over takes O(n) time.

Question 5

Subarray

Answer 5

A range of contiguous values within an array.
Example: given an array [2, 3, 6, 1, 5, 4], [3, 6, 1] is a subarray while [3, 1, 5] is not a subarray.

Question 6

Subsequence

Answer 6

A sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.
Example: given an array [2, 3, 6, 1, 5, 4], [3, 1, 5] is a subsequence but [3, 5, 1] is not a subsequence

Question 7

Insertion

Answer 7

Insert O(n) Insertion would require shifting all the subsequent elements to the right by one and that takes O(n)

Question 8

Access , Search , Search (sorted array)

Answer 8

Access O(1)
Search O(n)
Search (sorted array) O(log(n))

Question 9

Insert (at the end)

Answer 9

O(1) Special case of insertion where no other element needs to be shifted

Question 10

Remove

Answer 10

O(n) Removal would require shifting all the subsequent elements to the left by one and that takes O(n)

Question 11

Remove (at the end)

Answer 11

O(1) Special case of removal where no other element needs to be shifted

Question 12

Why do we need arrays?

Answer 12

Arrays are best for storing multiple values in a single variable
Arrays are better at processing many values easily and quickly
Sorting and searching the values is easier in arrays