Chapter Review

Access types and dynamic data structures are used to create linked lists, which are an extremely important data structure in computing. Linked lists are found in nearly every kind of computer application: Spreadsheet processing, operating system modules, compilers, and many others commonly employ linked lists and other dynamic data structures.

New Ada Constructs in Chapter 14

The new Ada constructs introduced in this chapter are described in Table 14.1.

Table 14.1
Summary of New Ada Constructs


Statement				Effect

TYPE NodePointer IS ACCESS ListNode;	Declares an access (pointer)	
					type whose variables can point to
					values of type ListNode

P: NodePointer;				and two variables of the access type
Q: NodePointer;

PROCEDURE Dispose IS NEW		Instantiates a predefined generic
  Unchecked_Deallocation		procedure to give an operation to
  (Object => ListNode, Name => NodePointer);	return tree nodes to
						the storage pool

P := NEW ListNode;			Allocates a list node and stores a
					pointer to it in P

Q := P;					Copies one pointer value to another

Q.ALL := P.ALL;				Copies one record's contents 
					to the other

Review Questions

Differentiate between dynamic and nondynamic data structures.
Define a simple linked list. Indicate how the pointers are utilized to establish a link between nodes. Also indicate any other variables that would be needed to reference the linked list.
Write a procedure that links a node into an existing list. Parameters are a pointer to the head of the linked list and a pointer to the node to be inserted. Assume dummy sentinel records exist at the beginning and end of the linked list and there are no duplicate records.
Given the following type definitions, insert the new element, preserving ID order:
```
TYPE Node;
TYPE Ptr IS ACCESS Node;
TYPE Node IS RECORD
  ID : INTEGER;
  Name : String(1..10);
  GPA : NonNegFloat;
  Link : PTR
END RECORD;
```
Write an algorithm to remove a node (identified by TargetID) from an ordered list that does not contain a dummy record at the beginning.
Write the necessary procedures to duplicate all elements in one linked list that have a GPA of 3.5 or above in another linked list. The original list is ordered by ID number; the new list should be ordered by GPA. Do not remove nodes from the existing list. Assume the list nodes are type Node as described in question 3. Parameters will be a pointer to the head of the existing list and to the head of the new linked list (GPAHead).
Declare a node for a two-way, or doubly linked, list, and indicate how a traversal would be made in reverse order (from the last list element to the list head). Include any variables or fields that are necessary.

Programming Projects

Write a procedure which attaches one list to the end of another. Note that this procedure destroys the original lists.
Write a function which returns the concatenation of two lists L1 and L2, that is, a list containing copies of all the nodes of L1 followed by copies of all the nodes of L2. Note that this function does not destroy either L1 or L2.
Write a procedure which deletes from an ordered list L the first node containing a given word.
Write a procedure which deletes from an ordered list L the last node containing a given word.
Write a procedure which deletes from an ordered list L all nodes containing a given word.
Write a function which takes two ordered lists as inputs, then returns a list in which the two input lists are merged. That is, if L1 contains "ABC," "HIJ,"and "PQR" and L2 contains "DEF," "HIJ," "MNO," and "STU," the result list contains "ABC," "DEF," HIJ," "HIJ," "MNO," PQR," and "STU".
Complete the generic package given in Section 14.6, writing the body and the remaining operations. Also correct the design flaw in MakeEmpty and RemoveFront, so that the latter returns the discarded node to the storage pool and the former returns all nodes in the list to the storage pool. (Hint: MakeEmpty must loop through the list, returning each node one at a time.)
Sometimes a list node is declared to have two pointers, one to the next node and one to the previous node. Develop a package for such doubly linked lists, and write the operations so that advantage is taken of the fact that each node points to its predecessor as well as its successor. Specifically, how does having the extra pointers simplify operations like ordered insertion and deletion?
Modify your employee data base system from Chapter 10 so that the data base is represented as an instance of the generic list package from Section 14.6.