Answers to Self-Review Questions - Java Software Solutions: Foundations of Program Design - page 787

13.2 Dynamic Representations
SR 13.4 A dynamic data structure is constructed using references to link various
objects together into a particular organization. It is dynamic in that it
can grow and shrink as needed. New objects can be added to the struc-
ture, and obsolete objects can be removed from the structure at run time
by adjusting references between objects in the structure.
SR 13.5 To insert a node into a list, first find the node that comes before the new
node (let's call it beforeNode ). Then, set the new node's next pointer
equal to beforeNode 's next pointer. Then, set beforeNode 's next
pointer to the new node. A special case exists when inserting a node at
the beginning of the list.
SR 13.6 To delete a node from a list, first find the node that comes before the
node to be deleted (let's call it beforeNode ). Then, set beforeNode 's
next pointer to the deleted node's next pointer. A special case exists
when deleting the first node of the list.
SR 13.7 set count = 0;
current = first;
while current != null
count++;
current = current.next;
return count;

SR 13.8 Each node in a doubly linked list has references to both the node that
comes before it in the list and the node that comes after it in the list.
This organization allows for easy movement forward and backward in
the list, and simplifies some operations.
SR 13.9 A header node for a linked list is a special node that holds informa-
tion about the list, such as references to the front and rear of the list
and an integer to keep track of how many nodes are currently in the
list.

13.3 Linear Data Structures
SR 13.10 A queue is a linear data structure like a list, but it has more constraints

on its use. A general list can be modified by inserting or deleting
nodes anywhere in the list, but a queue only adds nodes to one end
(enqueue) and takes them off of the other (dequeue). Thus, a queue
uses a first-in, first-out (FIFO) approach.

SR 13.11 The contents of the queue from front to rear are: 72 37 15