Node:Dynamic data structures, Next:Lists and trees, Previous:Data structure diagrams, Up:Complex data structures

Dynamic data structures, Pointers and Dynamic Memory

For programs dealing with large sets of data, it would be a nuisance to have to name every structure variable containing every piece of data in the code -- for one thing, it would be inconvenient to enter new data at run time because you would have to know the name of the variable in which to store the data when you wrote the program. For another thing, variables with names are permanent -- they cannot be freed and their memory reallocated, so you might have to allocate an impractically large block of memory for your program at compile time, even though you might need to store much of the data you entered at run time temporarily.

Fortunately, complex data structures are built out of dynamically allocated memory, which does not have these limitations. All your program needs to do is keep track of a pointer to a dynamically allocated block, and it will always be able to find the block.

A complex data structure is usually built out of the following components:

nodes

Dynamically-allocated blocks of data, usually structures.

links

Pointers from nodes to their related nodes.

root

The node where a data structure starts, also known as the root node. The address of the root of a data structure must be stored explicitly in a C variable, or else you will lose track of it.

There are some advantages to the use of dynamic storage for data structures:

• As mentioned above, since memory is allocated as needed, we don't need to declare how much we shall use in advance.
• Complex data structures can be made up of lots of "lesser" data structures in a modular way, making them easier to program.
• Using pointers to connect structures means that they can be re-connected in different ways as the need arises. (Data structures can be sorted, for example.)