Linked List - Internal and External Storage - Example of Internal and External Storage

Example of Internal and External Storage

Suppose you wanted to create a linked list of families and their members. Using internal storage, the structure might look like the following:

record member { // member of a family member next; string firstName; integer age; } record family { // the family itself family next; string lastName; string address; member members // head of list of members of this family }

To print a complete list of families and their members using internal storage, we could write:

aFamily := Families // start at head of families list while aFamily ≠ null // loop through list of families print information about family aMember := aFamily.members // get head of list of this family's members while aMember ≠ null // loop through list of members print information about member aMember := aMember.next aFamily := aFamily.next

Using external storage, we would create the following structures:

record node { // generic link structure node next; pointer data // generic pointer for data at node } record member { // structure for family member string firstName; integer age } record family { // structure for family string lastName; string address; node members // head of list of members of this family }

To print a complete list of families and their members using external storage, we could write:

famNode := Families // start at head of families list while famNode ≠ null // loop through list of families aFamily := (family) famNode.data // extract family from node print information about family memNode := aFamily.members // get list of family members while memNode ≠ null // loop through list of members aMember := (member)memNode.data // extract member from node print information about member memNode := memNode.next famNode := famNode.next

Notice that when using external storage, an extra step is needed to extract the record from the node and cast it into the proper data type. This is because both the list of families and the list of members within the family are stored in two linked lists using the same data structure (node), and this language does not have parametric types.

As long as the number of families that a member can belong to is known at compile time, internal storage works fine. If, however, a member needed to be included in an arbitrary number of families, with the specific number known only at run time, external storage would be necessary.

Read more about this topic:  Linked List, Internal and External Storage

Famous quotes containing the words internal, external and/or storage:

    “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)

    “Merely external emancipation has made of the modern woman an artificial being.... Now, woman is confronted with the necessity of emancipating herself from emancipation, if she really desires to be free.”
    —Emma Goldman (1869–1940)

    “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)