name: __________________________ login: _____________ name: __________________________ login: _____________ name: __________________________ login: _____________The code below is also accessible as file ListStuff.java, questions follow the code.
apple banana guava mango apple banana guava mango mango guava banana apple
copy
creates and returns a copy of the entire list passed to it.
array2linked
how many times does the expression
first == null
evaluate to true? Why?
hasDuplicates
whose header follows. The
method returns true if parameter list has any duplicates (words
occurring more than once) and false
otherwise. For example, for the list
( "apple", "guava", "cherry")hasDuplicates should return false, but it would return true for the list below since "guava" appears twice.
( "apple", "guava", "cherry", "guava")In writing
hasDuplicates
you must call the method
countOccurrences
shown below and your method must be either a
recursive function with no loop or a function with one loop. Either
version can include calls to countOccurrences
. You cannot use
any ArrayList, Set, etc. objects in your code.
hasDuplicates
and why?
hasDuplicates
method using, for example, a TreeSet
or
a HashSet
instead of calling countOccurrences
. Be sure
to indicate what the complexity of your solution is and why.
reverse
reverses a linked-list -- no new
nodes are created, the original order of the list is reversed as
shown in the diagrams below.
Here is the list before it is reversed, the parameter list
references the first node of the list.
The first recursive call passes a pointer to the "banana" node to
a method reverse
. This invocation of reverse
generates
the second recursive call
in which
parameter list
points at the third node, "guava", as shown
below.
This second invocation of reverse
results in
local variable revAfterFirst
pointing at the node
containing "mango". Briefly explain why.
Redraw the list just as the return statement
return
nodeAfterFirst
executes where that variable points
to "mango" as shown.
reverse
assume each
time the next
field of any node is referenced (to
see what it points to) a cost of one cent is incurred, and that
each time a value is assigned to a next field a cost of one cent
is incurred.
code | cost |
---|---|
making the call reverse(list.next)
| one cent |
the cost of executing/reversing the list with one node | one cent |
after the call, list.next.next = null
and list.next |
What is the cost of reversing a three node list and a five node list? Justify your answer.
addNodes
do -- specifically what is
printed by the last print
statement and why (if it executes)?