Array

Question 1

Provide a description of an array.

Answer 1

An array is a LIST with a FIXED SIZE which contains SIMILAR VALUES.

Question 2

What can be stored in an array?

Answer 2

Anything, provided they are of the same type.

Question 3

What is a Parallel Array?

Answer 3

Two or more arrays which…

• Contain the same number of elements.
• Have corresponding values in the same position.

Question 4

Why are Parallel Arrays useful?

Answer 4

For storing different types of data about the same entity.

Question 5

What is an alternative to Parallel Arrays?

Answer 5

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

Question 6

Can an array’s size be changed after instantiation?

Answer 6

No

Question 7

What is a NUMERICAL INDEX?

Answer 7

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

Question 8

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

Answer 8

Use a numerical index.

Question 9

What is the first possible numerical index of an array?

Answer 9

0

Question 10

What is the last possible numerical index of an array?

Answer 10

array.size - 1

Question 11

What is a multi-dimensional array and give examples.

Answer 11

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

Question 12

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

Answer 12

O(1)

Question 13

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

Answer 13

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 a single data type and so we know the size of each element. This is an example of Pointer Arithmetic.

Question 14

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

Answer 14

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

Question 15

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

Answer 15

O(log n) using a binary search.

Question 16

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

Answer 16

O(n)

Question 17

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

Answer 17

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

Question 18

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

Answer 18

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

Question 19

What are the PROS of the array? (3)

Answer 19

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

Question 20

What are the CONS of the array? (3)

Answer 20

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.

Question 21

When should you an Arrayinstead of an Arraylist?

Answer 21

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

Question 22

Is an array Random or Sequential Access?

Answer 22

Random