Part 1

Question 1

What is a recursive data structure?

Answer 1

A data structure that contains a reference or pointer to another object of the same type

Question 2

A linked list is a _______ data structure

Answer 2

Recursive

Question 3

What does the cons operation do with a linked list?

Answer 3

Take a list and a data item and construct a new list by adding the specified data item to the front of the list

Question 4

What does the head operation do with a linked list?

Answer 4

Returns the first item (the front item) of the list

Question 5

What does the tail operation do to a linked list?

Answer 5

Return the whole list, except the head

Question 6

How is an empty reference represented in java?

Answer 6

null

Question 7

What is the difference between a doubly linked list and a linked list?

Answer 7

Doubly linked list cells have a reference to the previous cell as well as the next one

Question 8

for a generic class, do you need <t> in the constructor method name?</t>

Answer 8

No

Question 9

What are the advantages of using doubly linked lists over singly linked lists?

Answer 9

More efficient traversal in both directions, can add and remove at both ends

Question 10

What is the disadvantage of using doubly linked lists over singly linked lists?

Why is this often not a concern?

Answer 10

More memory space

Not usually a concern because it will only use an extra int (4 bytes) per item which is usually insignificant next to the data structures the list is referencing.

Question 11

What is the disadvantage of using Object to allow generic classes, rather than <t>?</t>

Answer 11

Using object you have to downcast whenever you want to use the object, also allows objects to be mixed types which is probably not good

Question 12

When writing generic static methods, it is necessary to

Answer 12

include < T > in the signature after the word static

e.g. public static < T > void addCopies(T s, LList< T > ll, int numcopies)