Dynamic Data Structure A data structure that can expand and contract during execution.
Dynamic Linked List A linked list composed of dynamically allocated nodes that are linked together by pointers.
External (Head) Pointer A pointer variable that points to the first node in a dynamic linked list.
To create a dynamic linked list, we begin by allocating the first node and saving the pointer to it in the external pointer. We then allocate a second node and store the pointer to it into the link member of the first node. We continue this process-allocating a new node and storing the pointer to it into the link member of the previous node-until we have finished adding nodes to the list.
Let's look at how we can use C++ pointer variables to create a dynamic linked list of float values. We begin with the declarations
NodePtr head; // External pointer to list
NodePtr currPtr; // Pointer to current node
NodePtr newNodePtr; // Pointer to newest node
The order of these declarations is important. The Typedef for NodePtr refers to the identifier NodeType, so the declaration of NodeType must come first. (Remember that C++ requires every identifier to be declared before it is used.) Within the declaration of NodeType, we would like to declare link to be of type NodePtr, but we can't because the identifier NodePtr hasn't been declared yet. However, C++ allows forward (or incomplete) declarations of structs, classes, and unions:
