An Introduction to Data Structures - Java Concepts - page 952

null because first is null . The first field is set to the new node.
The result is a linked list of length 1.

4. It points to the element to the left. You can see that by tracing out the first
call to next . It leaves position to point to the first node.

5. If position is null , we must be at the head of the list, and inserting an
element requires updating the first reference. If we are in the middle of
the list, the first reference should not be changed.

6. You can focus on the essential characteristics of the data type without
being distracted by implementation details.

7. The abstract view would be like Figure 9 , but with arrows in both
directions. The concrete view would be like Figure 8 , but with references to
the previous node added to each node.

697
698

8. To locate the midde element takes n / 2 steps. To locate the middle of the
sub-interval to the left or right takes another n / 4 steps. The next lookup
takes n / 8 steps. Thus, we expect almost n steps to locate an element. At
this point, you are better off just making a linear search that, on average,
takes n / 2 steps.

9.

10. Stacks use a Ȓlast in, first outȓ discipline. If you are the first one to submit a
print job and lots of people add print jobs before the printer has a chance to
deal with your job, they get their printouts first, and you have to wait until
all other jobs are completed.