Editing Reference (computer science) (section)

==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 memory allocation|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 [[Recursive data type|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 is 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 (programming language)|Java]], [[Smalltalk]], [[Python (programming language)|Python]], and [[Scheme (programming language)|Scheme]], do not support internal storage.  In these languages, all objects are uniformly accessed through references.