List and iterators

Question 1

Give the code to remove an element from a List ADT that uses an arraylist.

Answer 1

E temp = data[i];
for (int k=i; k < size−1; k++) // shift elements to fill hole
data[k] = data[k+1];
data[size−1] = null; // help garbage collection
size−−;
return temp;

Question 2

All operations of an arrays & arrayList are O(1)? T/F

Answer 2

False, add and remove are O(n) because of all the shifting that has to take place

Question 3

Give the code to add an element from a List ADT that uses an arraylist.

Answer 3

if (size == data.length) // not enough capacity
throw new IllegalStateException(“Array is full”);
for (int k=size−1; k >= i; k−−) // start by shifting rightmost
data[k+1] = data[k];
data[i] = e; // ready to place the new element
size++;

Question 4

@ what index will add & remove of an array/arraylist be running @ O(1) and @ O(n)

Answer 4

when i ==0, O(n) for removal and addition. When i == n-1 then O(1) for both operations

Question 5

In the case of add(Element e) do we add e to the front or the end of the array and in the case that the array is now full, what happens?

Answer 5

We add at the end of the array and if the array is full, we replace the list with a bigger one

Question 6

What two methods of increasing the size of an array do we have and how do they work?

Answer 6

1. incremental strategy works by increasing the array by a constant each time it is full
2. Doubling works by doubling the size of the array each time it is full

Question 7

In what case would one be more suitable than the other for incremental vs doubling?

Answer 7

Incremental would be more suitable in the case where the array just needs to be +/- c cells bigger. So when we have just a few elements to add instead of doubling and having a lot of cells that were actually not needed

Doubling would be best if we need to add a lot of elements into the cells, otherwise we might find ourselves incrementing lots of times.

Question 8

What is the Big Oh of the doubling strategy?

Answer 8

T(n) = O(n) and to add a single element is O(1)

Question 9

Big Oh of the incremental strategy?

Answer 9

T(n) = O(n^2) but a single add operation in the worst case is O(n)

Question 10

why are postions preferable over indexes

Answer 10

Positions do not change even after elements shift due to deletion or insertion. The position is relative and not absolute. Even if the elemnent itself changes, the position will not

Question 11

What is the only way that a position in Position ADT is altered?

Answer 11

When the position and its element are explicitly removed

Question 12

Why would we want to get a position returned

Answer 12

to use it to traverse through the list
Safer because we don’t want the list altered
We shouldn’t be returning nodes

Question 13

What single method does a Position ADT have

Answer 13

element()

Question 14

Why would one want to use positions instead of indices for accessing elements?

Answer 14

Positions are relative and not absolute, meaning that even if we remove or add elements on to the data structure, the position will remain the same.

Question 15

What are the properties/benefits of storing something in a positional list?

Answer 15

• referring to a place without an index
• add after and addbefore(v)
• resitricts acess to the methods that can change our references to other nodes, safe
• not using encapsulation a lot because we expose too much of our implementation detail to the use

Question 16

What are the properties of iterators?

Answer 16

~ it hides away the complexity of traversing through nodes/cells/positions
~ Can check if a next exists and go to the next
~ traversal is independent of collection implementation

Question 17

What do you need to implement an iterator in an array vs LL

Answer 17

Array: array and index
LL: pointer to current position, DLL

Question 18

What are some properties of Arraylists?

Answer 18

~ elements stored in linear order
~ alias list/seq.
~ index referenced elements

Question 19

In what case would add and remove in an array list at the front run in O(1)?

Answer 19

Case the array is circular

Question 20

What methods do iterators have?

Answer 20

next and hasnext()

Question 21

Snapshot vs Dynamic

Answer 21

Snapshot: maintains a private copy of the sequence of elements at the time the iterator object was made

Dynamic: does not maintain the sequence but instead change with the data structure/sequence of elements

Question 22

When would a for-each loop be ideal to use?

Answer 22

1. you don’t know how many elements are in a iterable collection
2. you need to access each element of an iterable collection without using an index

Question 23

Position iterators

Answer 23

have positions() that will bring back an iterable object to be used to iterate through the positions
2. keeps the newest iterator as the valid one to avoid collisions

Question 24

Properties of a seq.?

Answer 24

~ multiple inheritence because it implements lists and array
~ access via indexes and positions
~ union of arraylists and positional lists
~ bridge methods: atIndex(i), indexOf(p)