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:

    “We have our difficulties, true; but we are a wiser and a tougher nation than we were in 1932. Never have there been six years of such far flung internal preparedness in all of history. And this has been done without any dictator’s power to command, without conscription of labor or confiscation of capital, without concentration camps and without a scratch on freedom of speech, freedom of the press or the rest of the Bill of Rights.”
    —Franklin D. Roosevelt (1882–1945)

    “Nature predominates over the human will in all works of even the fine arts, in all that respects their material and external circumstances. Nature paints the best part of the picture, carves the best of the statue, builds the best part of the house, and speaks the best part of the oration.”
    —Ralph Waldo Emerson (1803–1882)

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