# Array Flashcards

1
Q

Provide a description of an array.

A

An array is a data structure with a FIXED SIZE which contains sequential VALUES.

2
Q

What can be stored in an array?

A

Anything, provided they are of the same type.

3
Q

What is a Parallel Array?

A

Two or more arrays which…
- Contain the same number of elements.
- Have corresponding values in the same position.

4
Q

Why are Parallel Arrays useful?

A

For storing different types of data about the same entity.

5
Q

What is an alternative to Parallel Arrays?

A

Storing the related data in a single container object in a single array.

6
Q

Can an array’s size be changed after instantiation?

A

No

7
Q

What is a NUMERICAL INDEX?

A

An integer which corresponds to an element’s position within an array.

8
Q

How do we get (access) an element that is stored within an array?

A

Use a numerical index.

9
Q

What is the first possible numerical index of an array?

A

0

Because we are at array_address + 0

10
Q

What is the last possible numerical index of an array?

A

array.size - 1

11
Q

What is a multi-dimensional array and give examples.

A

An array within an array. 2D array - Pixel image. Many nested arrays - Calendar.

12
Q

What is the BigO of ACCESSING an element in an Array?

A

O(1)

13
Q

How does an array achieve O(1) for access operations?

A

An array stores each element in contiguous blocks of memory. This allows for fast ACCESS as we can quickly calculate an elements location in memory using the array’s start memory address and adding to it the memory address of the supplied numerical index multiplied by an elements memory size. We can do this as arrays store only elements of equal size.

14
Q

What is the BigO of SEARCHING for an element in an UNSORTED Array?

A

O(n) as you will have to perform a linear search of (in worst-case scenario) every element in the array.

15
Q

What is the BigO of SEARCHING for an element in an SORTED Array?

A

O(log n) using a binary search.

16
Q

What is the BigO of INSERTING and DELETING an element in an array?

A

O(n)

17
Q

Why is the BigO of INSERTING an element into an array O(n)?

A

You need to shift every element that’s after the element you want to insert to the right by one index.

18
Q

Why is the BigO of DELETING an element into an array O(n)?

A

You need to shift every element that after the element you want to delete to the left by one index.

19
Q

What are the PROS of the array? (3)

A
1. Good for storing similar contiguous data.
2. Very fast ACCESS power. O(1).
3. Allows for simple (non-complex) code.
20
Q

What are the CONS of the array? (3)

A
1. Size cannot change once initialized.
2. INSERTING, DELETING (and searching when unsorted) are not efficient O(n).
3. Can lead to wasted storage space if the array is never fully populated.
21
Q

When should you an Arrayinstead of an Arraylist?

A

For smaller tasks, where you won’t be interacting or changing the data that often.

22
Q

Is an array Random or Sequential Access?

A

Random

23
Q

How do size and capacity differ?

A

size is the number of elements in an array
capacity is the total number of places in an array