External and Internal Storage
In many data structures, large, complex objects are composed of smaller objects. These objects are typically stored in one of two ways:
- With internal storage, the contents of the smaller object are stored inside the larger object.
- With external storage, the smaller objects are allocated in their own location, and the larger object only stores references to them.
Internal storage is usually more efficient, because there is a space cost for the references and dynamic allocation metadata, and a time cost associated with dereferencing a reference and with allocating the memory for the smaller objects. Internal storage also enhances locality of reference by keeping different parts of the same large object close together in memory. However, there are a variety of situations in which external storage is preferred:
- If the data structure is recursive, meaning it may contain itself. This cannot be represented in the internal way.
- If the larger object is being stored in an area with limited space, such as the stack, then we can prevent running out of storage by storing large component objects in another memory region and referring to them using references.
- If the smaller objects may vary in size, it's often inconvenient or expensive to resize the larger object so that it can still contain them.
- References are often easier to work with and adapt better to new requirements.
Some languages, such as Java, Smalltalk, Python, and Scheme, do not support internal storage. In these languages, all objects are uniformly accessed through references.
Read more about this topic: Reference (computer Science)
Famous quotes containing the words external, internal and/or storage:
“The ideal of brotherhood of man, the building of the Just City, is one that cannot be discarded without lifelong feelings of disappointment and loss. But, if we are to live in the real world, discard it we must. Its very nobility makes the results of its breakdown doubly horrifying, and it breaks down, as it always will, not by some external agency but because it cannot work.”
—Kingsley Amis (1922–1995)
“Even if fathers are more benignly helpful, and even if they spend time with us teaching us what they know, rarely do they tell us what they feel. They stand apart emotionally: strong perhaps, maybe caring in a nonverbal, implicit way; but their internal world remains mysterious, unseen, “What are they really like?” we ask ourselves. “What do they feel about us, about the world, about themselves?””
—Augustus Y. Napier (20th century)
“Many of our houses, both public and private, with their almost innumerable apartments, their huge halls and their cellars for the storage of wines and other munitions of peace, appear to me extravagantly large for their inhabitants. They are so vast and magnificent that the latter seem to be only vermin which infest them.”
—Henry David Thoreau (1817–1862)