Arrays

Question 1

What are arrays?

Answer 1

A type of object in Java used to store many values in one variable. Created to hold a specific number of values (any non-negative integer)

Question 2

What is the length of an array?

Answer 2

An array always knows how many values it contains: its length. The length can never change.

Question 3

What is an element?

Answer 3

An individual item stored in an array

Question 4

What is a subscript?

Answer 4

aka an index: each element has an index/subscript. The subscripts are always from 0 to length-1

Question 5

How do you create an array?

Answer 5

There are two parts:
1. declare the reference variable for the array. like int[] someInts;
2. instantiate the array and assign it to the reference variable. like someInts = new int[7];

Question 6

What are some things to be aware of when declaring an array?

Answer 6

• there is never a number inside the []
• This type can hold a reference to any array of that type of data
• declaring an array does not create an array object
• at first, the variable contains null

Question 7

What are some things to be aware of when instantiating an array?

Answer 7

• must use the ‘new’ keyword
• this allocates memory for an array object that can hold a specific number of elements
• instantiation gives you a reference to the newborn array
• the length can never change but the elements can change

Question 8

What does it mean for an array to be an Object?

Answer 8

• array reference variables are stored on the stack, array objects are stored on the heap
• the stack contains all primitive types and references to other data
• the heap contains all non-primitive data

Question 9

What does the ‘null’ reference mean?

Answer 9

“no object”. A new reference variable will always contain null if you don’t create an object and assign the object to the reference variable. You can set object reference variables to null, meaning that there is no address stored and the variable does not point to an object on the heap

Question 10

What are some things to keep in mind when literally instantiating an array?

Answer 10

• Literals do not require the new keyword to create the array but you can use it
• if you are using literal initialization but it’s declared on a different line you need the new

Question 11

How can you access the length of the array?

Answer 11

using myData.length. There is no (). You cannot change the length, only find its value

Question 12

How can you access the elements of the array?

Answer 12

Using myData[expression]; The expression must result in an integer from 0 to myData.length-1. You can freely access or change the elements anywhere you can use any other variable of that type

Question 13

How must you go about copying an array?

Answer 13

If you have two array variables of the same type, you can use assignment to ‘copy’, but this will be a shallow copy as it just copies the reference. For a deep copy that creates a new separate array you have to instantiate a new array of the same size, and loop through the original and copy each element into the second array

Question 14

What gets passed or returns when passing arrays?

Answer 14

Only the reference. The function gets a shallow copy. That means that any changes made to the elements of an array parameter inside a function will affect the original. However, if you overwrite the array parameter, it will now point to a new array and not change the address in the original array

Question 15

What are aliases?

Answer 15

Two array variables that point to the exact same array object (have the same reference)

Question 16

What are partially filled arrays?

Answer 16

Has data in some bins, but not all. Use a separate int variable to keep track of the current size. You can’t use literal array creation to create a partially filled array

Question 17

What are the two fundamental algorithms for searching an array?

Answer 17

Linear search and binary search

Question 18

What is a linear search?

Answer 18

• looks through the array one element at a time
• slow
• can handle any list

Question 19

What is the binary search?

Answer 19

• divides the list in half repeatedly
• fast
• requires the list to be sorted
• pick the middle of the list. If the value is larger, go left, and right if the value is smaller.
• mid = (lo+hi)/2
• change hi/lo value to ‘get rid’ of half the list
• you’ll know when you’ve run out of places to look when lo>hi

Question 20

How do you know if you should use a binary search?

Answer 20

• if you happen to have a sorted list already
• if you plan to do a lot of searching but the list doesn’t change often, so keeping it sorted is easy
• if you have lots of time to sort, but when they happen, the searches need to be fast

Question 21

What is ordered insertion?

Answer 21

One way to get a sorted list: add in order as you go. Work from the end of the list to the front, moving items one spot to the right, until the new item is bigger than the current item, then insert it

Question 22

What are impossible value partially filled arrays?

Answer 22

Partially filled arrays where instead of having all the empty bins at the end, they are marked with a constant defined to identify the impossible value. To insert an item, find the first empty bin.