Java Reference
In-Depth Information
16.
List the steps necessary to remove a node from the doubly linked chain shown in Figure 14-12 when the node is
a.
First in the chain
b.
Last in the chain
c.
Between existing nodes in the chain.
P
ROJECTS
1.
Write a program that thoroughly tests the class
LList2
.
2.
Listing 3-5 of Chapter 3 shows the class
Node
as part of a package. Create another package that contains
Node
,
LList
, and
ListInterface
. Revise
LList
to use this version of
Node
.
3.
Create a Java interface that declares the following methods:
/** Adds a new entry to the beginning of this list. */
public void
addFirst(T newEntry)
/** Adds a new entry to the end of this list. */
public void
addLast(T newEntry)
/** Removes and returns the first entry in this list. */
public
T removeFirst()
/** Removes and returns the last entry in this list. */
public
T removeLast()
/** Returns the first entry in this list. */
public
T getFirst()
/** Returns the last entry in this list. */
public
T getLast()
/** Moves the first entry in this list to the end of the list. */
public void
moveToEnd()
Then define
DoubleEndedListInterface
by extending this interface and
ListInterface
. Write a class that
implements
DoubleEndedListInterface
. Represent the list's entries by using a chain of nodes that has both a
head reference and a tail reference. Write a program that thoroughly tests your class.
4.
Repeat the previous project, but do not use a tail reference.
5.
Adding nodes to or removing nodes from a linked chain requires a special case when the operation is at the begin-
ning of the chain. To eliminate the special case, you can add a
dummy node
at the beginning of the chain. The
dummy node is always present but does not contain a list entry. The chain, then, is never empty, and so the head
reference is never
null
, even when the list is empty. Modify the class
LList
, as presented in this chapter, by add-
ing a dummy node to the chain.
6.
In a circularly linked chain, the last node references the first node. Commonly, only one external reference—to the
last node—is maintained, since the first node is found easily from the last one.
Modify the class
LList
, as presented in this chapter, by using a circular linked chain and a tail reference.
7.
Implement as the class
Ring
the ADT ring that Project 3 of Chapter 1 described. Represent the ring as a chain of
linked nodes. Consider using a circular linked chain, as described in the previous project.
8.
Implement and test a class of lists using a doubly linked chain, as shown in Figure 14-12, to represent the entries
in the list. Use an inner class of nodes like the one that Exercise 12 of Chapter 3 asked you to define, but include
set and get methods.
