Chapter 15 Data Structure

1. Self-referential classes contain members called links that point to objects of
   the same class type.

2. Self-referential classes enable many class objects to be linked together in 
   stacks, queues, lists, and trees.

3. Dynamic memory allocation reserves a block of bytes in memory to store an 
   object during program execution.

4. A linked list is a linear collection of Self-referential class objects.

5. A linked list is a dynamic data structure - the length of the list can 
   increase or decrease as necessary.

6. Linked lists can continue to grow until memory is exhausted.

7. Linked list provide a mechanism for simple insertion and deletion of data by 
   pointer manipulation.

8. A singly-linked-list begins with a pointer to the first node and each node 
   contains a pointer to the next node "in sequence". This list terminates with 
   a node whose pointer member is 0. A singly-linked-list may be traversed in 
   only one direction.

9. A circular, singly-linked-list begins with a pointer to the first node and 
   each node contains a pointer to the next node. The pointer in the last node 
   points back to the first node, thus closing the "circle"

10. A doubly-linked-list allows traversals both forwards and backwards. each 
    node has both a forward pointer to the next node in the list in the forward 
    direction, and a backward pointer to the next node in the list in the 
    backward direction.

11. Stacks and queues are constrained versions of linked lists.

12. The stack nodes are added to a stack and removed from a stack only at the 
    top of the stack. For this reason, a stack is referred as a last-in, 
    first-out (LIFO) data structure.

13. The link member in the last node of the stack is set to null (0) to indicate 
    the bottom of the stack.

14. Two primary operations used to manipulate a stack are push and pop. The push 
    operation creates a new node and places it on the top of the stack. The pop 
    operation removes a node from the stack, delete the memory that was 
    allocated to the popped node, and returns the popped value.

15. In queue data structrue, nodes are removed from the head and added to the tail. 
    For this reason, a queue is referred as a first-in, first-out (FIFO)  data 
    structure. The add and remove operations are known as enqueue and dequeue.

16. Trees are two-dimensional data structures requiring two or more links per 
    node.

17. Binary trees contains two links per node.

18. The root node is the first node in the tree.

19. Each of the pointers in the root node refers to a child. The left child is 
    the first node in the left subtree, the the right child is the first node in 
    the right subtree. The children of a node are called siblings. Any tree node 
    that does not have chiuldren is called a leaf node.

20. A binary search tree has the characteristics that the value in the left 
    child of a node is less than the value in its parent node, and the value in 
    the right child of a node is greater than or equal to the value in its 
    parent node. If there are no duplicate data values, the value in the right 
    child is simply greater than the value in its parent node.

21. A inoder traveral of a binary tree traverse the left subtree inorder, 
    processes the value in the root node, then traverses the right subtree 
    inorder. The value in a node is not processed until the value in its 
    left subtree are processed.

22. A preoder traveral of a binary tree, processes the value in the root node,
    then traverse the left subtree preorder,  then traverses the right subtree 
    preorder. The value in a node is processed as the node is encountered.

21. A postoder traveral of a binary tree traverse the left subtree postorder, 
    traverses the right subtree postorder, then processes the value in the root 
    node. The value in a node is not processed until the value in both its 
    subtrees are processed.

22. An array can be declared to contain more elements than the number of items 
    expected, but this can waste memory. Linked memory can provide better memory 
    utilization in these situations. Linked lists allow the program to adapt at 
    run time.

23. The elements of an array are stored contiguously in memory. This allows 
    immediate access to any array because the address of any element can be 
    calculated directly based on its position relative to the beginning of the 
    array. Linked list do not afford such immediate "direct access" to their 
    elements.

24. Using dynamic memory allocation instead of arrays of data structures that 
    grow and shrink at execution time can save memory. keep in mind, however, 
    that pointers occupy space, and that dynamic memory allocation incurs the 
    overhead of function calls.