انتقل إلى المحتوى
أمين أبوزيد
Englishالعربية
منشورBEG-040-L01

المصفوفات في الذاكرة

  • الدرس 1 من 7
  • 12 دقيقة قراءة
  • مبتدئ
في هذا الدرس 11 موضوعات

هذا الدرس متاح حاليًا باللغة الإنجليزية فقط، ولم تُنشر نسخته العربية بعد.

Lesson Overview

You have used arrays since the early modules of this course, and you met ArrayList in the Collections Framework module. This lesson opens the box and shows what an array actually is inside RAM, and why a[3] is so fast. That one fact explains most of what follows in this module.

We use a picture: a row of lockers in a corridor. All lockers are the same size, they sit side by side, and they are numbered from 0. By the end you will be able to say, with reasons, which array operations are cheap and which are expensive.

Why this matters: nearly every list, buffer, and table a backend uses is built on arrays. Knowing their costs tells you why some code scales and some code slows down as data grows.

This lesson builds on RAM (Module 1), Java arrays, and Big O notation from "Big O notation" and "Analyzing loops and nested loops" (BEG-039).

Learning Objectives

By the end of this lesson you will be able to:

  • Describe an array as equal-sized slots stored side by side in memory.
  • Explain why reading or writing a[i] is O(1), using the address calculation.
  • Explain why the size of an array is fixed once it is created.
  • Insert into and remove from the middle of an array by shifting items, and state that this costs O(n).
  • Search an unsorted array and state that this costs O(n).
  • Distinguish an array's length from the number of items you have actually stored.

Written Explanation

A row of lockers

When Java creates new int[5], it asks for one block of memory big enough for five int values in a row. Think of five lockers, numbered 0 to 4, each exactly the same size.

text
index:   0     1     2     3     4
       +-----+-----+-----+-----+-----+
       | 10  | 20  | 30  | 40  | 50  |
       +-----+-----+-----+-----+-----+
 start address                  ^ jump straight here for a[3]

Two facts make arrays special:

  1. The slots are contiguous: no gaps, they touch.
  2. The slots are equal-sized: every int takes the same number of bytes.

Java's official tutorial puts it plainly: an array's length is established when it is created, and after that its length is fixed. Items are numbered from 0, so the 9th element of an array has index 8.

Why a[i] is O(1)

Because the slots are equal-sized and touch each other, the computer does not search for item i. It computes where it is:

text
address of a[i] = start address + i * size of one item

If an array of int starts at address 1000 and each int takes 4 bytes, then a[3] is at 1000 + 3 * 4 = 1012. One multiplication and one addition, whether the array holds five items or five million. The cost does not grow with n, so it is O(1). The numbers above are illustrative; real addresses are managed by the JVM and you never see them.

For an array of objects, such as String[], each slot holds a reference to an object, and all references have the same size, so the same arithmetic works. The objects themselves live elsewhere on the heap, which you will study in the memory module (BEG-038 covers the picture of stack and heap).

Java also checks the index before it touches memory. If i is below 0 or not less than the length, Java throws ArrayIndexOutOfBoundsException instead of reading someone else's memory. That check is a cheap comparison, so access stays O(1).

The size is fixed

The lockers are built in one block. If the locker next to the last one belongs to someone else, you cannot just glue another locker on the end. To get a bigger array you must ask for a new, larger block and copy everything across. Lesson 2 builds on exactly that idea. For now remember: int[] a = new int[5] can never become 6 long.

A new array is also filled with defaults at creation: 0 for numbers, false for boolean, and null for object references. So a freshly created array of length 8 is "full" of default values even though you have stored nothing meaningful yet.

Length versus size

a.length is the number of lockers. It says nothing about how many hold real data. A program that fills only part of an array has to keep its own counter, usually called size:

java
int[] a = new int[8];   // length 8
int size = 0;           // nothing stored yet

Positions 0 to size - 1 are the real items; positions from size onward are spare lockers. Every list class in the JDK, and every one you build in this module, is a wrapper around an array and a size counter.

Insert in the middle: shift

Suppose the first four lockers hold 5, 6, 8, 9 and you want 7 between 6 and 8, at index 2. The locker at index 2 is occupied, and you may not push it out of the way, because there is no "between" in a row of lockers. You must shift every later item one place to the right, starting from the last item (otherwise you overwrite something you still need), then write the new value.

text
before: 5 6 8 9 _ _ _ _
shift:  5 6 8 8 9 _ _ _   (9 moved, then 8 moved)
write:  5 6 7 8 9 _ _ _

In the worst case you insert at index 0 and move all n items. The cost is O(n). Removing from the middle is the mirror image: shift later items one place left to close the gap. Inserting or removing at the end shifts nothing, so it is O(1) as long as there is a spare locker.

Search an unsorted array: scan

To find a value you do not have an index for, you start at index 0 and check each locker until you find it or run out. If the value is last or missing, you check all n items. That is O(n), also called linear search. The array's speed advantage applies only when you already know the index. Finding the value is a different question, and without extra structure the answer is a scan. (Later modules show structures that find values faster.)

The cost table

Operation on an array with n itemsCostWhy
Read or write a[i]O(1)Address is computed
Insert or remove at the end (spare room)O(1)Nothing shifts
Insert or remove at the start or middleO(n)Items shift
Search for a value (unsorted)O(n)Scan item by item
Grow beyond its lengthO(n)New block plus copy

Examples

Example 1: indexing, defaults, and the bounds check (simple)

java
int[] lockers = {10, 20, 30, 40, 50};
System.out.println(lockers[3]);
System.out.println(lockers.length);
int[] fresh = new int[3];
System.out.println(Arrays.toString(fresh));
System.out.println(lockers[5]);   // index 5 does not exist

Output from a real run on JDK 21 (the last line is the exception message, which the program printed from a catch block):

text
40
5
[0, 0, 0]
Index 5 out of bounds for length 5

The jump to lockers[3] is direct. Index 5 is rejected because valid indexes are 0 to 4.

Example 2: insert in the middle by shifting (practical)

java
static int[] insertAt(int[] a, int size, int index, int value) {
    for (int i = size; i > index; i--) {
        a[i] = a[i - 1];          // shift right, last item first
    }
    a[index] = value;
    return a;
}

int[] a = new int[8];
a[0] = 5; a[1] = 6; a[2] = 8; a[3] = 9;
insertAt(a, 4, 2, 7);
System.out.println(Arrays.toString(a));

Output:

text
[5, 6, 7, 8, 9, 0, 0, 0]

The loop runs from the last stored item backward. If it ran forward, a[3] = a[2] would copy 8 over 9 and the 9 would be lost. The loop body runs size - index times, so inserting near the front is expensive.

Example 3: searching and counting the work (realistic)

A small service keeps recent order ids in an array and asks "did we already see this id?".

java
static int indexOf(int[] a, int size, int target) {
    int checks = 0;
    for (int i = 0; i < size; i++) {
        checks++;
        if (a[i] == target) {
            System.out.println("found after " + checks + " checks");
            return i;
        }
    }
    System.out.println("not found after " + checks + " checks");
    return -1;
}

int[] ids = {41, 7, 93, 15, 62, 8};
indexOf(ids, ids.length, 15);
indexOf(ids, ids.length, 99);

Output:

text
found after 4 checks
not found after 6 checks

Looking for a missing id always costs n checks. With six ids that is nothing; with ten million it is a real delay on every request. The work grows with the data, which is exactly what O(n) means.

Backend Insight

Arrays are the foundation under much of what a backend does: the buffer that holds bytes read from a network connection, the rows a database page keeps together, and the list your code returns from a query. Two habits follow from this lesson.

  • Index when you can. If you have a way to get an item by position (or later, by a key in a map), do that rather than scanning a long list on every request.
  • Be suspicious of the front. Code that repeatedly inserts or removes at the start of an array-backed structure does O(n) work each time. Spotting that pattern in a code review is a real, practical skill.

Arrays also tend to be friendly to the processor because their items sit together in memory, but do not turn that into a performance claim without measuring your own code.

Common Mistakes

Mistake 1: Confusing length with the number of stored items

  • Incorrect: looping for (int i = 0; i < a.length; i++) over a partly filled array and treating the default 0 or null values as real data.
  • Correct: loop to your own size counter.

Mistake 2: Off-by-one in the last index

An array of length n has indexes 0 to n - 1. a[a.length] always fails with ArrayIndexOutOfBoundsException.

Mistake 3: Shifting in the wrong direction

When inserting, shift from the end toward the insertion point. When removing, shift from the gap toward the end. Doing it the other way round copies one value over many places.

Mistake 4: Thinking "O(1) access" means "O(1) everything"

Fast a[i] says nothing about inserting at the front or searching for a value. Cost depends on the operation, not on the structure alone.

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. An int[] starts at (imaginary) address 2000 and each int takes 4 bytes. At what address is a[6]?

أظهر الحل A1

A1. 2000 + 6 * 4 = 2024.

A2. In one sentence, why is reading a[i] O(1) and not O(n)?

أظهر الحل A2

A2. The address is computed from the start address and the index with one multiplication and one addition, so no items are scanned and the cost does not depend on n.

A3. int[] a = new int[4]; What does Arrays.toString(a) print, and what is a.length?

أظهر الحل A3

A3. It prints [0, 0, 0, 0] and a.length is 4. New int slots default to 0.

Level B: Application

B1. Write static int max(int[] a, int size) that returns the largest of the first size items (assume size >= 1). What is its cost?

أظهر الحل B1

B1.

java
static int max(int[] a, int size) {
    int best = a[0];
    for (int i = 1; i < size; i++) {
        if (a[i] > best) best = a[i];
    }
    return best;
}

It looks at each item once, so it is O(n). For {4, 9, 2, 7, 5} it returns 9 (verified by running it).

B2. Write static int removeAt(int[] a, int size, int index) that removes the item at index by shifting left and returns the new size. Show the array after removing index 1 from {4, 9, 2, 7, 5}.

أظهر الحل B2

B2.

java
static int removeAt(int[] a, int size, int index) {
    for (int i = index; i < size - 1; i++) {
        a[i] = a[i + 1];
    }
    a[size - 1] = 0;   // clear the spare slot
    return size - 1;
}

After removing index 1 from {4, 9, 2, 7, 5} the array is [4, 2, 7, 5, 0] and the new size is 4 (real run).

B3. An array holds 1,000 items. How many items shift when you insert at index 0? At the end (with spare room)?

أظهر الحل B3

B3. Inserting at index 0 shifts all 1,000 items. Inserting at the end shifts none.

Level C: Challenge

C1. Write static void reverse(int[] a) that reverses the array in place, with no second array. How many swaps for length 5? What is the cost in Big O?

أظهر الحل C1

C1.

java
static void reverse(int[] a) {
    for (int i = 0, j = a.length - 1; i < j; i++, j--) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

Length 5 needs 2 swaps (the middle item stays). Each swap handles two items, so the work is about n/2 swaps, which is O(n). Running it on [4, 2, 7, 5, 0] gave [0, 5, 7, 2, 4].

C2. A teammate says: "Arrays are fast, so keeping a million user names in an array and checking contains on every request is fine." Explain what is true and what is wrong in that sentence.

أظهر الحل C2

C2. True: reading by index is fast. Wrong: contains does not have an index; it scans, which is O(n), so with a million names each request may check up to a million items. A structure designed for lookup by key (the Map from the Collections module) is the better tool.

Mini Challenge

Make a "locker log" for an array of 10 int slots with a size counter. Write insertAt, removeAt, and a print method that shows only the first size items. Then:

  1. Add the values 3, 1, 4, 1, 5 at the end.
  2. Insert 9 at index 0.
  3. Remove the item at index 3.
  4. Print after each step and write the Big O of each method in a comment above it.

Check your work: print never shows spare slots, insertAt shifts from the end backward, and removeAt clears or ignores the freed slot.

Summary & Next Lesson

Key takeaways

  • An array is a block of equal-sized slots side by side; index i is found by start + i * item size, so access is O(1).
  • The length is fixed at creation; to grow, you allocate a bigger array and copy.
  • Insert or remove in the middle or at the front shifts items: O(n). At the end with spare room: O(1).
  • Searching an unsorted array scans item by item: O(n).
  • length is the number of slots; your own size is the number of real items.

Next lesson

Next is "Dynamic arrays and resizing". It builds on the fixed-size problem from this lesson and shows how a list like ArrayList hides the grow-and-copy step, and why appending still averages out to O(1).

Self-check

  1. Why is a[i] O(1)?
  2. Why can an array not simply grow by one slot?
  3. What is the cost of inserting at index 0 of an array holding n items?
  4. How do you search an unsorted array, and what does it cost?
  5. What is the difference between a.length and a size counter?
أظهر الإجابات
  1. The position is computed from the start address and i; nothing is scanned.
  2. The array is one fixed block and the memory after it may not be free, so a bigger array means a new block and a copy.
  3. O(n), because all n items shift one place right.
  4. Check each item from index 0; O(n).
  5. a.length is how many slots exist; size is how many of them hold real data.

References

  • Oracle, The Java Tutorials, Arrays. Supports: array length is fixed once created, and numbering starts at index 0.
  • Oracle, Java SE 21 API, java.util.Arrays. Supports: Arrays.toString for printing and Arrays.copyOf creating a new array of another length (used from Lesson 2).
  • The address formula, default values, and the bounds-check behavior were confirmed by running the examples on JDK 21; the exact bytes per int and real memory addresses are illustrative and depend on the JVM, which this lesson does not verify. The memory-friendliness remark is hedged and not backed by a source here.

التطبيق

طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.

المختبر والتمارين الاختبار

تعليم الدرس كمكتمل اختياري ويمكنك التراجع عنه في أي وقت. يبقى تقدمك محفوظًا في هذا المتصفح.

تابع إلى الدرس التالي

اكتب للبحث في المستويات والمراحل والوحدات والدروس.