Linked lists - Data Structures and Problem Solving Using Java - page 649

a. Write a method to cut and paste that is not a part of weiss

.nonstandard . What is the running time of the algorithm?

b. Write a method in the LinkedList class to do the cut and paste.

What is the running time of the algorithm?

The SortedLinkedList insert method uses only public iterator methods.
Can it access private members of the iterator?

17.11

Implement an efficient Stack class by using a LinkedList (either stan-
dard or nonstandard) as a data member. You need to use an iterator, but
it can be either a data member or a local variable for any routine that
needs it.

17.12

Implement an efficient Queue class by using (as in Exercise 17.12) a
singly linked list and appropriate iterators. How many of these itera-
tors must be data members in order to achieve an efficient imple-
mentation?

17.13

Implement retreat for singly linked lists. Note that it will take linear
time.

17.14

Implement the nonstandard LinkedList class without the header node.

17.15

PROGRAMMING PROJECTS
17.16

Implement a circularly and doubly linked list.

If the order that items in a list are stored is not important, you can fre-
quently speed searching with the heuristic known as move to front:
Whenever an item is accessed, move it to the front of the list. This
action usually results in an improvement because frequently accessed
items tend to migrate toward the front of the list, whereas less fre-
quently accessed items tend to migrate toward the end of the list. Con-
sequently, the most frequently accessed items tend to require the least
searching. Implement the move-to-front heuristic for linked lists.

17.17

Write routines makeUnion and intersect that return the union and inter-
section of two sorted linked lists.

17.18

Write a line-based text editor. The command syntax is similar to the
Unix line editor ed . The internal copy of the file is maintained as a
linked list of lines. To be able to go up and down in the file, you have to
maintain a doubly linked list. Most commands are represented by a
one-character string. Some are two characters and require an argument
(or two). Support the commands shown in Figure 17.31.

17.19