Java Reference
In-Depth Information
C
HAPTER
S
UMMARY
•
When a chain has only a head reference or has both head and tail references, the following are true:
•
Adding a node to the chain's beginning is a special case.
•
Removing the first node from the chain is a special case.
•
Adding or removing a node that is last in the chain requires a traversal of the entire chain.
•
Adding a node anywhere within a chain requires a change of at most two references.
•
Removing any node from a chain requires a change of at most two references.
•
When a chain has both head and tail references, the following are true:
•
Adding a node to an empty chain is a special case.
•
Adding a node to the chain's end is a special case.
•
Removing the last node from a chain is a special case.
•
Maintaining a reference to a chain's last node as well as to its first node eliminates the need for a traversal
when adding a node at the end of the chain. Thus, adding to the end of a list is faster when the chain has both
head and tail references than when it has only a head reference. For this reason, we have used a chain that
has both head and tail references to implement the ADT list.
E
XERCISES
1.
Add a constructor to the class
LList
that creates a list from a given array of objects. Consider at least two different
ways to implement such a constructor. Which way requires the least amount of work?
2.
Write a program that tests the first version of
LList
.
3.
Consider the definition of the
add
method that adds an entry to a list at a given position and appears in
Segment 14.11. Replace the statements that execute in case 1 with the following ones:
if
(isEmpty() || (newPosition == 1))
// case 1
{
firstNode = newNode;
newNode.next = firstNode;
}
a.
What is displayed by the following statements in a client of the modified
LList
?
ListInterface<String> myList =
new
LList<String>();
myList.add(1, "30");
myList.add(2, "40");
myList.add(3, "50");
myList.add(1, "10");
myList.add(5, "60");
myList.add(2, "20");
int
numberOfEntries = myList.getLength();
for
(
int
position = 1; position <= numberOfEntries; position++)
System.out.print(myList.getEntry(position) + " ");
b.
What methods, if any, in
LList
could be affected by the change to the method
add
when they execute?
Why?
4.
Suppose that you want an operation for the ADT list that adds an array of items to the end of the list. The header
of the method could be as follows:
public
void
addAll(T[] items)
Write an implementation of this method for the class
LList
.
