A List Implementation That Links Data - Data Structures and Abstractions with Java - page 363

9.

When the method add calls the method isEmpty , isEmpty will return false because numberOfEntries incorrectly
is not zero. Thus, the method getNodeAt will be invoked. The second assert statement in getNodeAt will cause
an AssertionError , because currentNode is null .

10.

Either version of the while statement would control the loop in toArray correctly, assuming the rest of the class is
correct. Testing both index and currentNode in the while statement guards against a mistake somewhere else in
the class.

11.

The version of toArray that calls getNodeAt performs much more work than the original version. Each call to
getNodeAt results in a traversal of the chain of nodes from its first node to the desired node. The original version
of toArray traverses the chain only once.

12.

a. The method getEntry in the class AList retrieves any entry from a list in O(1) time, because the list's entries
are stored in an array. The corresponding method in LList must traverse a chain of linked nodes to retrieve a
list entry. It is an O( n ) operation.
b. Instead of calling getEntry , we invoke the method toArray to get all of the list's entries.
public static void displayList(ListInterface<String> list)
{

int numberOfEntries = list.getLength();
System.out.println("The list contains " + numberOfEntries +
" entries, as follows:");
Object[] listArray = list.toArray();
for ( int index = 0; index < listArray.length; index++)
{

System.out.print(listArray[index] + " is entry " + (index + 1));
} // end for
System.out.println();
} // end displayList

13.

If the list is empty, numberOfEntries is zero. Thus, (givenPosition >= 1) && (givenPosition <= 0) is always
false, and the method would then return null . The only way the body of the first if statement can execute is if the
list is not empty.

14.

The method replace given in this chapter performs more work than an array-based replace because it must tra-
verse the chain to locate the entry to replace. An array-based replace can locate the desired entry directly, given
its array index.

15.

The methods clear , both add methods, and the method remove would need to be revised to accommodate the
addition of a tail reference.

16.

The first assertion should be
assert (firstNode == null ) && (lastNode == null );
The second assertion should be
assert (firstNode != null ) && (lastNode != null );

17.

O( n ).

18.

O(1) when removing the first entry, or O( n ) otherwise.

19.

O(1) when replacing the first entry, or O( n ) otherwise.

20.

O(1) when retrieving the first entry, or O( n ) otherwise.