Dynamic Memory Allocation

Creating and maintaining dynamic data structures requires dynamic memory allocationthe ability for a program to obtain more memory space at execution time to hold new nodes and to release space no longer needed. Remember that Java programs do not explicitly release dynamically allocated memory. Rather, Java performs automatic garbage collection of objects that are no longer referenced in a program.

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 disk space in a virtual-memory system. Often, the limits are much smaller, because the computer's available memory must be shared among many applications.

The declaration and class-instance creation expression

Node nodeToAdd = new Node( 10 ); // 10 is nodeToAdd's data

allocates the memory to store a Node object and returns a reference to the object, which is assigned to nodeToAdd. If insufficient memory is available, the expression throws an OutOfMemoryError.

The following sections discuss lists, stacks, queues and trees that all use dynamic memory allocation and self-referential classes to create dynamic data structures.