Array Data Structure in Java Explained Simply | DSA for Beginners

Here's a question. You have an array with one million numbers. Reading the very first number takes one step. How many steps does it take to read the last one?

Also one step. Not a million. Just one.

But if you add a new number at the front of that same array, Java has to move all one million numbers. Same array. One action is instant, the other is slow.

By the end of this video, you'll know exactly why. And it's simpler than you think.

Welcome back to Compiled Canvas. This is Episode Seven of our DSA series, and the start of Module One: arrays. In Episode Six, we played with bits. Today, we slow down, and really understand the most important data structure of all.

Here's the plan. What an array really is. Why reading any position is instant. Looping through an array. Searching for a value. Adding and removing values. What happens when an array is full. Reversing an array in place. A simple cheat sheet. And an easy quiz at the end.

Let's go.

First, what is an array?

Think of a row of lockers in a school corridor. Every locker is the same size. They sit side by side, with no gaps. And every locker has a number on the door.

An array is exactly that. A row of boxes, all the same size, sitting next to each other in memory. Each box holds one value.

In Java, you create one like this: int array, equals new int of five. That gives you five boxes, and each one starts at zero.

The number on each box is called the index. And here's the part that confuses beginners: the first index is zero, not one. So five boxes have the indexes zero, one, two, three and four. The last index is always the length minus one.

Why start at zero? Because the index means "how many boxes to skip from the start". The first box needs zero skips. The second box needs one skip. That's all it is.

Now, the most important idea in this video.

Imagine a street where every house is exactly ten metres wide. The first house is at the corner. Where is house number seven? You don't need to walk past every house. You just do one sum: seven times ten metres. You go straight there.

An array works the same way. Java knows where the first box starts. And it knows how big each box is. An int takes four bytes. So to find box number seven, it does one sum: start, plus seven times four. Then it jumps straight there.

That's why reading arr of zero, and reading arr of nine hundred thousand, take the same time. One sum, one jump. We call that O of one.

The same goes for changing a value. arr of three equals fifty jumps straight to box three, and puts fifty inside. Also O of one.

Look at this graph. Along the bottom, the array gets bigger and bigger. Up the side, the time it takes. Reading by index is a flat line. Ten boxes or ten million, it never goes up.

So remember this: reading or writing by index is instant, no matter how big the array is.

Next, looping. Very often you need to visit every box, one by one.

The most common loop is a for loop. Start i at zero, keep going while i is less than the length, and add one to i each time. Inside the loop, arr of i is the current value.

Let's add up the numbers three, eight and five. Start with a sum of zero. Visit the first box: the sum becomes three. The second box: eleven. The third box: sixteen. Done.

Finding the biggest number works the same way. Remember the biggest so far. Look at each box, and if the value is bigger, remember that one instead.

If the array has n boxes, the loop visits n boxes. So the time is O of n. Twice as many boxes, twice as much work. On our graph, that's a straight line going up.

And when you don't need the index, Java has a shorter loop: for int x, colon, arr. It gives you each value in order, one at a time.

Now, searching. Say you want to know: is the number forty in this array?

The array can't tell you where forty is. It only knows positions, not values. So you check the boxes one by one, from the start. Is this forty? No. Is this forty? No. Is this forty? Yes! Found it at index two.

This is called linear search. If you're lucky, forty is in the first box, and you're done in one step. If you're unlucky, it's in the last box, or it's not there at all, and you check every box.

We always plan for the unlucky case. So linear search is O of n.

There's a much faster way when the array is sorted. It's called binary search, and it gets its own episode later in this series. For now, just remember: searching an unsorted array means checking every box, and it's O of n.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now, adding and removing. This is where arrays get slow.

Picture people sitting in a row of cinema seats, with no empty seats between them. A new person arrives, and wants to sit in the second seat. What happens? Everyone from the second seat onwards has to stand up and move one seat to the right. Only then can the new person sit down.

An array works the same way. Say the array holds ten, twenty, thirty and forty, and you want to add fifteen at index one. First, forty moves right. Then thirty moves right. Then twenty moves right. Now index one is free, and fifteen goes in.

The more values after the spot, the more moves. Adding at the front moves everything. So adding in the middle or at the front is O of n.

Removing works the same way, in the other direction. Take out the value at index one, and everything after it slides one seat to the left, to close the gap. Also O of n.

But here's the good news. Adding or removing at the end moves nothing. There's nobody to the right. So working at the end is O of one.

Here's the graph for both. Adding at the end stays flat, no matter how big the array gets. Adding at the front climbs, because every extra box is one more move.

Simple rule: the end is cheap. The front and the middle are expensive.

Next, a big limit of arrays. Their size is fixed. Once you create five boxes, you have five boxes forever.

So what if you need a sixth? You have to make a brand new, bigger array, copy every value across, and then add the new one. Copying n values is O of n.

That sounds painful. That's why Java gives you ArrayList. It's an array that grows by itself. When it fills up, it quietly makes a bigger array, about one and a half times the size, and copies everything across for you.

Here's what that looks like. The ArrayList starts with room for ten. When it's full, it jumps to fifteen. Then twenty-two. Then thirty-three. Each jump is a copy, but the jumps get further and further apart.

Does all that copying make ArrayList slow? Not really. The copies happen rarely, because each new array has lots of spare room. So on average, adding to the end of an ArrayList is still O of one.

So here's when to use which. If you know the size from the start, use a plain array. If the size changes as you go, use an ArrayList.

Now let's use what we've learned to solve a real problem: reverse an array.

The easy way is to make a second array, and fill it from the back. That works, but it uses n extra boxes of memory.

The smart way needs no extra array. Use two pointers. One starts at the first box, called left. The other starts at the last box, called right.

Swap the two values. Then move left one step forward, and right one step back. Swap again. Keep going until the two pointers meet in the middle.

Let's try it on one, two, three, four, five. Swap one and five. Swap two and four. Now both pointers are on three, the middle, so we stop. The array is now five, four, three, two, one.

Each value moves once, so it's O of n time. And we used no extra array, so the extra memory is O of one. When you change an array without making a copy, we say you did it in place.

So, here's the whole array in one cheat sheet. Pause and screenshot this.

Reading or changing a value by its index: O of one.

Looping through every value: O of n.

Searching for a value in an unsorted array: O of n.

Adding or removing at the end: O of one.

Adding or removing at the front or in the middle: O of n, because the other values have to shift.

And growing a full array: O of n, because everything is copied. ArrayList does it for you.

Okay, quiz time. Three easy questions. Pause the video, think, and then hit play.

Question one. An array has ten boxes. What is the index of the last box?

Question two. Which is faster: reading arr of zero, or reading arr of nine hundred thousand?

Question three. Is adding a value at the front of an array O of one, or O of n?

Ready?

Question one: nine. Indexes start at zero, so the last one is the length minus one.

Question two: neither. They take the same time. Java does one sum and jumps straight there. That's O of one.

Question three: O of n. Every value has to move one place to the right, to make room at the front.

How many did you get right? Tell me in the comments: three out of three, two, or one.

Let's recap. An array is a row of same-size boxes, sitting side by side in memory. Indexes start at zero, and the last index is the length minus one. Reading or changing any box is O of one, because Java jumps straight there. Looping and searching visit every box, so they're O of n. Adding or removing at the end is cheap. At the front or in the middle, values shift, so it's O of n. And to reverse an array in place, use two pointers, and swap.

Your homework. Solve Reverse String on LeetCode, using the two pointer swap from this video. Then try Concatenation of Array. Both are easy, and both use exactly what you learned today. And tell me in the comments: in an array of twenty boxes, what is the last index?

Next episode, we learn the prefix sum. It's a simple trick that answers "what's the sum from here to there?" in just one step, instead of adding everything up again.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.