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:
“A State, in idea, is the opposite of a Church. A State regards classes, and not individuals; and it estimates classes, not by internal merit, but external accidents, as property, birth, etc. But a church does the reverse of this, and disregards all external accidents, and looks at men as individual persons, allowing no gradations of ranks, but such as greater or less wisdom, learning, and holiness ought to confer. A Church is, therefore, in idea, the only pure democracy.”
—Samuel Taylor Coleridge (1772–1834)
“The real essence, the internal qualities, and constitution of even the meanest object, is hid from our view; something there is in every drop of water, every grain of sand, which it is beyond the power of human understanding to fathom or comprehend. But it is evident ... that we are influenced by false principles to that degree as to mistrust our senses, and think we know nothing of those things which we perfectly comprehend.”
—George Berkeley (1685–1753)
“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)