Java Reference
In-Depth Information
(b) L2.append(10);
L2.append(20);
L2.append(15);
L2.moveToStart();
L2.insert(39);
L2.next();
L2.insert(12);
4.3 Write a series of Java statements that uses the List ADT of Figure 4.1 to
create a list capable of holding twenty elements and which actually stores the
list with the following configuration:
h 2; 23 j 15; 5; 9 i:
4.4 Using the list ADT of Figure 4.1, write a function to interchange the current
element and the one following it.
4.5 In the linked list implementation presented in Section 4.1.2, the current po-
sition is implemented using a pointer to the element ahead of the logical
current node. The more “natural” approach might seem to be to have curr
point directly to the node containing the current element. However, if this
was done, then the pointer of the node preceding the current one cannot be
updated properly because there is no access to this node from curr . An
alternative is to add a new node after the current element, copy the value of
the current element to this new node, and then insert the new value into the
old current node.
(a) What happens if curr is at the end of the list already? Is there still a
way to make this work? Is the resulting code simpler or more complex
than the implementation of Section 4.1.2?
(b) Will deletion always work in constant time if curr points directly to
the current node?
In particular, can you make several deletions in a
row?
4.6 Add to the LList class implementation a member function to reverse the
order of the elements on the list. Your algorithm should run in (n) time for
a list of n elements.
4.7 Write a function to merge two linked lists. The input lists have their elements
in sorted order, from lowest to highest. The output list should also be sorted
from lowest to highest. Your algorithm should run in linear time on the length
of the output list.
4.8 A circular linked list is one in which the next field for the last link node
of the list points to the first link node of the list. This can be useful when
you wish to have a relative positioning for elements, but no concept of an
absolute first or last position.
Search WWH ::




Custom Search