Name: _____________________ Netid: _________________ Name: _____________________ Netid: _________________ Name: _____________________ Netid: _________________In all these problems assume that the inner class Node exists as shown below. You'll write methods in a class
LinkStuff
for your solutions. You'll snarf a skeleton version of the code to write
solutions in a group and then view them during recitation. You cannot
use instance variables, all variables must be local to the
methods you write.
specialCount
whose header follows.
The method specialCount
returns a count of the number of nodes
whose info field has a value which is special as determined
by the method isSpecial
.
isSpecial
returns true) and "bear", "coyote", and "fox"
are not special, and list
is represented by:
("apple", "bear", "apple", "orange", "coyote", "fox", "orange", "pear")the call
specialCount(list)
should evaluate to 5 since there are
five special strings.
Write the function makeReversed
whose header follows. The
function returns a list in which for each number
k in the range [1..n], there are k nodes containing
k, and the nodes are in reverse order: n, n-1, ..., 3, 2, 1
When creating nodes, use a string like "3" for the number 3, so nodes still contain strings.
For example:
Doubly linked lists are implemented using the declaration
below.
For example, if
Note that it's possible that the original first node is moved and that
no nodes are moved. You should not create any new nodes, just move
pointers/references.
For full credit your code must run in O(n) time for an n-node
list. You might want to create a pointer to a list containing the
moved nodes, update that list, then link the entire moved-node
list to the end.
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
frequency
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 frequency
. You cannot use
any ArrayList, Set, etc. objects in your code.
hasDuplicates
and why?
remove
that removes all nodes
with a specific value from a doubly-linked list with no header
node. It's much easier to write this recursively.
list
is
("aardvark", "cat", "dog", "cat")
then the statement
list = remove(list, "cat");
should make list
be ("aardvark", "dog").
/**
* @return list with all copies of target removed
*/
public static DNode remove(DNode list, String target)
Be sure to change all links appropriately.
moveToBack
which moves each node whose
info field is equal to target
to the end of the list.
The nodes are doubly-linked.
The relative order of the unmoved nodes
doesn't change (from the original order in the list).
A pointer to the modified
list is returned.