Computer memories are normally thought of as falling into two basic categories, internal and external. Which memory is used to store data depends on the trade-off of efficiency of access to data versus the cost of that efficiency.
The data structures and algorithms considered thus far are all appropriate to the internal memory of a computer. This memory is also referred to as main memory or random access memory. A program can process only information stored in its internal memory. If the program is to process information stored in external memory, that information must first be read into its internal memory. Except for the instructions involved in this transfer of information, all program instructions refer to variables that name internal memory locations.
By means of random access, it is possible to access any individual internal memory element in exactly the same length of time?/FONT>typically one-millionth of a second or less. This access time is independent of the past history of accessed elements. However, random access memory is expensive and, although available in increasingly larger sizes, is still relatively small in size compared to the storage needs of many applications.
External memory, also referred to as secondary storage, is so called because it is physically outside the computer itself. It is relatively inexpensive and is available in very large amounts, but access to an arbitrary record is slow compared to internal memory. Magnetic tapes, floppy disks, and magnetic disks (also known as hard disks) are the usual devices for external storage of data. The characteristics of these devices that are essential for efficient use of data structures are discussed in this chapter. Since the characteristics of secondary storage devices are different from those of internal memory, the data structures and algorithms required to process the data they store are distinct from those for internal memory. However, many of the same concepts and techniques of good design and implementation of algorithms are still applicable and form the basis for representing and operating on information stored in external memory.