Detailed Explanation
Before covering arrays, it’s important to understand what a data structure is to begin with.
Data structures are a way to store data efficiently inside a computer component called Random Access Memory (RAM). RAM is often simply referred to as memory. Let’s understand how an array is stored in RAM.
An array is an ordered collection of contiguous elements, for example [1, 3, 5]. But computers only understand data in terms of bits, i.e., 0s and 1s.
Most computers today have gigabytes (GBs) of RAM. The computer you’re using to view this course might have 8 GB (109 bytes) of RAM. One byte of RAM is composed of exactly 8 bits.
Binary Representation
Back to our integers, each of [1, 3, 5] has a binary representation, which means they can be represented as 0s and 1s. If we used a single byte to store each, then the integer 1 could be represented as 00000001, 3 as 00000011, and 5 as 00000101.
Important: When we store an array in RAM, each element is stored contiguously in order.
Integer Storage
Integers commonly take up 4 bytes (32 bits) in memory. An address and a value are associated with an integer when storing it in RAM. An address is simply a distinct location where each of the values is stored. Each value is stored contiguously in RAM, just like an array.
Each integer takes 4 bytes of space, therefore addresses are spaced by 4 bytes.
Character Storage
Instead of integers, we could also store characters in an array.
Each character takes 1 byte of space, therefore addresses are spaced by 1 byte.
The size or the data type we store doesn’t really matter, as long as the address increments relative to the size of the data type. Most of the time this knowledge is abstracted away from us as developers, but it’s relevant for understanding many algorithms and data structures. It’s also extremely important in systems design.
Key Concepts
- Byte: Basic unit of memory composed of 8 bits
- Address: Specific location in memory where a value is stored
- Contiguity: Elements are stored one after another in memory
- Data type: Determines how many bytes each element occupies
Common Data Type Sizes
| Data Type | Size | Bits |
|---|---|---|
| char | 1 byte | 8 bits |
| int | 4 bytes | 32 bits |
| float | 4 bytes | 32 bits |
| double | 8 bytes | 64 bits |
Conclusion
RAM is fundamental to understanding how data structures work. Key concepts include:
- Contiguous storage: Array elements are stored one after another
- Memory addresses: Each element has a unique location in RAM
- Data types: The type’s size determines spacing between addresses
- Binary representation: Everything is stored as bits (0s and 1s)
Although this knowledge is often abstracted away in modern programming, understanding how data is stored in memory is essential for optimizing algorithms and designing efficient systems. The following chapters will focus on practical concepts about array operations.