Java Reference
In-Depth Information
5.
Define the method
getPosition
, as described in Exercise 2 of the previous chapter, for the class
LList
. Compare
the execution time required by this method with the version of
getPosition
defined in the class
AList
.
6.
Implement an
equals
method for the class
LList
that returns true when the entries in one list equal the entries in a
second list.
7.
Repeat Exercise 10 in the previous chapter, but use the class
LList
instead of
AList
.
8.
Suppose that a list contains
Comparable
objects. Implement a method that returns a new list of items that are less
than some given item. The header of the method could be as follows:
public
LList<T> getAllLessThan(Comparable<T> anObject)
Write an implementation of this method for the class
LList
. Make sure that your method does not affect the state
of the original list.
9.
Define the method
remove
, as described in Exercise 3 of the previous chapter, for the class
LList
.
10.
Repeat the previous exercise, but remove all occurrences of
anObject
from the list.
11.
Define the method
moveToEnd
, as described in Exercise 4 of the previous chapter, for the class
LList
.
12.
Implement a
replace
method for the class
LList
that returns the replaced object.
13.
Suppose that a list contains
Comparable
objects. Define the methods
getMin
and
removeMin
, as described in
Exercise 7 of the previous chapter, for the class
LList
.
14.
Consider an instance
arrayList
of
AList
, as given in the previous chapter. Let the list have an initial size of 10.
Also, consider an instance of
LList
called
chainList
.
a.
How large is the underlying array after adding 145 items to
arrayList
?
b.
How large is the underlying array after adding 20 more items to
arrayList
?
c.
How many nodes are in the chain after adding 145 items to
chainList
?
d.
How many nodes are in the chain after adding 20 more items to
chainList
?
e.
Each node in a chain has two references, so a chain of
n
nodes has 2
n
references. An array of size
n
, on the
other hand, has
n
references. Count the number of references in each of the situations described in Parts
a
through
d
.
f.
When will
arrayList
use fewer references than
chainList
?
g.
When will
chainList
use fewer references than
arrayList
?
15.
A doubly linked chain, like the one described in Exercise 12 and Figure 3-11 of Chapter 3, has nodes that each can
reference a previous node and a next node. In Chapter 3, the doubly linked chain has only a head reference, but it
can have both a head reference and a tail reference, as Figure 14-12 illustrates.
List the steps necessary to add a node to a doubly linked chain when the new node is
a.
First in the chain
b.
Last in the chain
c.
Between existing nodes in the chain
FIGURE 14-12
A doubly linked chain for Exercises 15 and 16 and Project 8
firstNode
lastNode