UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 5.1 Free with a free account
How Arrays Store Data
Data Structures and Algorithms · Chapter 5: ArraysSection 5.1 · lesson 16 of 8713 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Data Structures and Algorithms.
Lesson complete
Earn the 3 college credits for Data Structures and Algorithms
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Rearranging Elements Within a Fixed-Size Collection →← Inner Classes That Depend on Their Enclosing ObjectNext lesson: Rearranging Elements Within a Fixed-Size Collection →
In this lesson
How Java arrays store elements and why indexing takes constant time.
- Declare, create and initialize arrays and predict their default values
- Explain how contiguous storage makes indexing a constant-time operation
- Traverse arrays with index and for-each loops while avoiding out-of-bounds errors
- Weigh the strengths and limits of arrays, including growing one with Arrays.copyOf
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,859 words). Read along, or search it.
Opening Question
Thousands of Readings, One Variable
A weather station logs the temperature once a minute. By the end of one day, that's 1,440 readings. Nobody writes 1,440 separate variables. Programs keep many values of one kind together, and Java's simplest way to do that is the array. Here's a puzzle to keep in mind. Reading the four-millionth value of an array takes exactly as long as reading the third. Why?
Analogy
Arrays as Rows of Numbered Lockers
Picture a row of school lockers. They're the same size, they sit side by side, and each has a number painted on its door. To fetch your jacket, you don't search the whole hallway. You walk straight to your number. An array works the same way. Each slot is called an element, and the number on its door is its index. Here's an array named scores, with five elements. The first index is 0, so the last one is 4.
Key Features
Same Type, Fixed Length, Zero-Based
Four features define every array. Same type: every element holds the same kind of value, such as all whole numbers. So every slot is the same size. Fixed length: the number of slots is chosen when the array is created, and it never changes. Zero-based index: the first slot is index 0, and the last is the length minus 1. Index 5 is the sixth slot, not the fifth. And the length is known. The array reports it as scores.length, with no parentheses, so a loop knows where to stop.
Syntax
Declare, Create and Initialize
Setting up an array takes three steps, and Java lets you write them on three lines, or on one. First, declare it. int, square brackets, scores gives the variable a name, and says its elements are whole numbers. No slots exist yet. Second, create it. new int, five, reserves memory for five slots, and every slot starts at a default value. Third, initialize it: store the values you want. scores, index 0, equals 90, puts 90 in the first slot. Declaring and creating usually share one line. And when you already know the values, list them in braces. Java counts them, and sets the length for you.
Default Values
Zeros, False and Null in New Slots
Java never leaves a new slot undefined. Each one starts at a default value that depends on the element type. Whole numbers start at 0, decimals at 0.0, and true-or-false values at false. A char slot holds the character with code 0, which prints as an invisible mark. And text, along with every other kind of object, starts as null, which means no object here yet. That's the trap. A new array of strings holds null, not empty text. Ask a null slot for its length, and the program stops with an error. Store a real value first.
Memory Layout
One Contiguous Block of Memory
Now, the puzzle from the start. A computer's memory is a long strip of numbered locations, and each location has an address. When an array is created, Java reserves one unbroken stretch of them for all its slots. That's called a contiguous block: side by side, with no gaps. The array variable remembers where the block starts. And because every slot is the same size, any slot's address is one calculation. The address of slot i is the start address, plus i times the size of one slot. Say the block starts at address 1000, and each whole number takes 4 bytes. Slot 0 is at 1000, slot 1 at 1004, and slot 3 at 1000 plus 12: 1012. These addresses are only an illustration. Java manages the real ones, and never shows them to you.
Constant Time
Why Any Index Costs the Same
Look at that calculation again. To reach slot 3, the computer does one multiplication and one addition. To reach slot four million, it does exactly the same two operations. The work doesn't depend on the index, or on how many elements the array holds. Computer scientists call this constant time, and write it O(1). It only works because every slot is the same size. Even an array of text keeps that promise: each slot holds a small, fixed-size reference to the text, not the text itself. Compare a collection you must walk, starting at the first element and moving one at a time. The farther the target, the more steps it takes.
Quick Check
Address of the Element at Index Six
Quick check, with a new array. A block of decimal numbers starts at address 2000, and each one takes 8 bytes. Where does the element at index 6 live? Is it 2006, 2048, or 2056? Pause, and decide. It's 2048: 2000, plus 6 times 8 bytes. 2056 comes from counting from 1. Index 6 is the seventh slot, but it sits only six slots past the start. And 2006 forgets that each slot is 8 bytes wide, not 1.
Traversal
Summing With an Index Loop
Traversal means visiting every element once, usually to read the values, or add them up. Java gives you two loops for it. The index loop uses a counter, i, that walks through 0, 1, 2, and so on. It keeps going while i is less than the length. Each pass adds scores of i to the total: 90, then 165, 253, 315, and finally, 415. Then i becomes 5. Five is not less than 5, so the loop ends, right after the last valid index. The total is 415.
For-Each Loop
Finding the Highest Score
When you only need each value, and not its position, the for-each loop is shorter, and harder to get wrong. Read the colon as in: for each int s, in scores. Here, it finds the highest score, 100. One catch. The variable s receives a copy of each value. So s equals s plus 5 changes only the copy, and scores of 0 is still 90.
Decision Guide
Index Loop or For-Each
So which loop? To read every value from first to last, use for-each. There's no index to manage, so there's no chance of an off-by-one mistake. When you need the position of each element, use the index loop, because the counter i is the position. To change the stored values, use the index loop too. Only scores of i equals something changes the array itself. And to go backward, skip elements, or visit only part of the array, the index loop lets you control the start, the end, and the step.
Runtime Error
Index Out of Bounds
An array of length 5 has exactly five valid indexes: 0, 1, 2, 3, and 4. Any other index points to a slot that doesn't exist. Java checks every index while the program runs. Ask for scores of 5, and the program stops with an array index out of bounds exception. The message names the bad index and the actual length: Index 5 out of bounds for length 5. That's usually enough to find the mistake.
Quick Check
A Loop That Starts at One
Quick check, with a new loop. An array holds four temperatures, and a loop sets each one to 20. The loop starts i at 1, and runs while i is less than or equal to the length. What happens? Does every slot become 20, with no error? Do three slots become 20, and then an error? Or does the compiler reject the loop? Pause, and decide. B. Slots 1, 2 and 3 get 20. Then i reaches 4, and Java stops: index 4, out of bounds for length 4. Slot 0 is never touched, so it keeps its default, 0. That's two mistakes in one loop: counting from 1, and less than or equal, instead of less than. And it does compile, because the compiler doesn't know what value an index will have. The error appears only when the program runs.
Common Causes
Four Ways to Leave the Array
Those are two of the four usual causes: less than or equal in the loop test, and counting from 1. The third is an empty array. new int of 0 has no valid index at all, so check the length before you read slot 0. The fourth is a negative index, such as i minus 1, calculated when i is 0. When an index comes from user input or a calculation, guard it. If it's at least 0 and less than the length, use it. Otherwise, report that there's no such position.
Strengths
Where Arrays Shine
Now the balance sheet. Where do arrays shine? Access is instant: any element is one calculation away. They're compact: the slots sit together, with almost no extra memory. They're fast to traverse, because neighboring slots are neighbors in memory, so a loop moves through them smoothly. And they're simple. The idea is easy to understand, and easy to reason about.
Limitations
Where Arrays Struggle
And where they struggle. The size is fixed: the length is chosen at creation, and can't change. There's one type only: every element must have the same type. Insertion can be costly, because making room in the middle means moving other elements. And the size is a guess. A guess that's too big wastes memory, and one that's too small runs out.
Growing an Array
Copying Into a Larger Array
Take the fixed size first. The array of five scores is full, and a sixth score arrives. There's no free slot. And the memory just past the block may already belong to something else, so the block can't simply stretch. The only option is a new, larger array, with the old values copied across. Arrays dot copyOf does it in one line, once import java dot util dot Arrays sits at the top of the file. Ask for 8 slots, and the extra three take default values: 90, 75, 88, 62, 100, then 0, 0, 0. Copying isn't free, though. The work grows with the number of elements copied.
Cost Summary
Rough Cost of Common Tasks
Here's the rough cost of common tasks. Reading or changing the element at an index is constant: one address calculation. Adding at the end is constant too, when a free slot exists. Visiting every element grows with the number of elements. So does adding to a full array, because every value must be copied. And inserting in the middle, or at the front, grows with the number of elements that have to move over. That shifting gets a lesson of its own.
Worked Example
Total, Average and Highest Score
Here's everything together: store five quiz scores, then report the total, the average, and the highest. One for-each loop adds each score to the total, and keeps the highest so far. Two details are worth noticing. The loop never mentions the number 5. It relies on the array, so a sixth score in the braces would still work. And double, in parentheses before total, converts the total to a decimal first. Without it, Java divides two whole numbers and drops the fraction. The results: Total: 415, Average: 83.0, and Highest: 100.
Key Takeaways
Arrays in Summary
To sum up. An array stores a fixed number of same-type elements, numbered from 0, and new slots start at 0, 0.0, false, or null. The elements sit in one contiguous block, so any slot's address is one calculation. That's why indexing takes constant time. Use an index loop when you need positions or changes, and for-each to read every value. Valid indexes run from 0 to the length minus 1. And an array can't grow: a bigger one must be created, and filled.
Think About It
Contacts in a Fixed-Size Array
Something to think about. A friend says: I'll keep my contacts in an array, because I never know how many I'll have, and arrays are the simplest collection. Which array limit makes that a risky choice? And what would the program have to do, each time the array fills up?
About Data Structures and Algorithms at UPI Study
Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms
Why take it here
Why students take Data Structures and Algorithms with UPI Study
Where the credit goes
Universities that work with NCCRS
Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About How Arrays Store Data
Why is array access O(1) in Java?
What are the default values of a new array in Java?
What causes an ArrayIndexOutOfBoundsException?
How do you make an array bigger in Java?
About the Data Structures and Algorithms course
How many college credits is Data Structures and Algorithms?
How much does Data Structures and Algorithms cost and what is included?
Which universities accept UPI Study credits?
How long does Data Structures and Algorithms take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Data Structures and Algorithms.
87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →