Data Structures Demystified (Demystified)

What is the maximum number of tries you d need to find your name in a list of a million names ? A million? No, not even close. The answer is 20 ”if you structure the list to make it easy to search and if you search the structure with an efficient searching technique. Searching lists is one of the many ways data structures help you manipulate data that is stored in your computer s memory. However, before you can understand how to use data structures, you need to have a firm grip on how computer memory works. In this chapter, you ll explore what computer memory is and why only zeros and ones are stored in memory. You ll also learn what a Java data type is and how to select the best Java data type to reserve memory for data used by your program.

A Tour of Memory

Computer memory is divided into three sections: main memory, cache memory in the central processing unit (CPU), and persistent storage. Main memory , also called random access memory (RAM), is where instructions (programs) and data are stored. Main memory is volatile; that is, instructions and data contained in main memory are lost once the computer is powered down.

Cache memory in the CPU is used to store frequently used instructions and data that either is, will be, or has been used by the CPU. A segment of the CPU s cache memory is called a register. A register is a small amount of memory within the CPU that is used to temporarily store instructions and data.

A bus connects the CPU and main memory. A bus is a set of etched wires on the motherboard that is similar to a highway and transports instructions and data between the CPU, main memory, and other devices connected to a computer (see Figure 1-1).

Figure 1-1: A bus connects the CPU, main memory, persistent storage, and other devices.

Persistent storage is an external storage device such as a hard disk that stores instructions and data. Persistent storage is nonvolatile; that is, instructions and data remain stored even when the computer is powered down.

Persistent storage is commonly used by the operating system as virtual memory. Virtual memory is a technique an operating system uses to increase the main memory capacity beyond the random access memory (RAM) inside the computer. When main memory capacity is exceeded, the operating system temporarily copies the contents of a block of memory to persistent storage. If a program needs access to instructions or data contained in the block, the operating system switches the block stored in persistent storage with a block of main memory that isn t being used.

CPU cache memory is the type of memory that has the fastest access speed. A close second is main memory. Persistent storage is a distant third because persistent storage devices usually involve a mechanical process that inhibits the quick transfer of instructions and data.

Throughout this book, we ll focus on main memory because this is the type of memory used by data structures (although the data structures and techniques presented can also be applied to file systems on persistent storage).