Dynamic Memory Allocation and Data Structures

Creating and maintaining dynamic data structures requires dynamic memory allocation, which enables a program to obtain more memory at execution time to hold new nodes. When that memory is no longer needed by the program, the memory can be released so that it can be reused to allocate other objects in the future. The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available virtual memory in a virtual memory system. Often, the limits are much smaller, because available memory must be shared among many programs.

The new operator takes as an argument the type of the object being dynamically allocated and returns a pointer to an object of that type. For example, the statement

Node *newPtr = new Node( 10 ); // create Node with data 10

allocates sizeof( Node ) bytes, runs the Node constructor and assigns the address of the new Node object to newPtr. If no memory is available, new throws a bad_alloc exception. The value 10 is passed to the Node constructor which initializes the Node's data member to 10.

The delete operator runs the Node destructor and deallocates memory allocated with newthe memory is returned to the system so that the memory can be reallocated in the future. To free memory dynamically allocated by the preceding new, use the statement

delete newPtr;

Note that newPtr itself is not deleted; rather the space newPtr points to is deleted. If pointer newPtr has the null pointer value 0, the preceding statement has no effect. It is not an error to delete a null pointer.

The following sections discuss lists, stacks, queues and trees. The data structures presented in this chapter are created and maintained with dynamic memory allocation, self-referential classes, class templates and function templates.