First look at arrays

Yesterday, I was going through a couple of DS&A books that I had used during my student days. One particular book, written by Jean-Paul Tremblay and Paul G. Sorenson uses a very small point font and runs to over 700 pages. I don’t think I will be able to go through that book today. While the book is a great one, in today’s age of diminishing attention, I do not think that students will be able to patiently read it thoroughly. So I have decided to give very simple definitions, even if they are not complete in all respects.

First some simple definitions.

Data structures help us in arranging our data in ways that make accessing and manipulating them easy.

Algorithms are logical sequence of steps that access and manipulate data. Good algorithms take advantage of the structure of the data to make themselves more efficient.

Bad data structures lead to bad algorithms, though, I dare say, you can create bad algorithms even with good data structures.

As you can see, data structures and algorithms have to be individually good and compatible with each other to result in good programs.

Some real life examples of (data) structures.

The next time you go to a public swimming pool, take your eyes off the babes/hunks for a couple of minutes and look at the row of lockers meant for keeping your stuff in while you are swimming.

They are usually arranged one next to the other in single file. You typically go there, find an empty locker and shove your things in. If there are no empty lockers, you can’t do much about it until somebody empties one of the lockers.

Now, let us say, you are more than seriously eying one of the aforementioned babes/hunks. You might want to grab the locker next to theirs for yourself. If it is empty, you are in luck, but if it is not, what can you do?

If you are really desperate, you could find an empty locker (locker n) somewhere, take all the things from the locker(locker 1) you want and move it to the empty locker and put your stuff in locker 1. There – where luck fails, initiative triumphs.

But supposing, the empty locker (locker n) that you find is quite far away and you don’t want the original occupant to scream and create a scene, what can you do?

One way of solving this problem is to do as follows:

Assume that you have your stuff in your left hand. You could open the locker you want and take all the stuff in it in your right hand. Then you could take your stuff from your left hand and put into the locker. Initial goal achieved, but you have somebody else’s stuff in your right hand. You will need to get rid of that decently.

So, you move to the next locker and take the stuff out with your left hand. Then take what is in your right hand and put it into that locker. Continue down the row of lockers alternating hands until both your hands are free. Whew! That was tough.

In another way of going about it, you would probably start at the locker before the empty one (locker n-1) and transfer all the items in that into the empty one. Then you would move to the previous locker (locker n-2) and move the items in that into the currently empty one (locker n-1). You will keep doing this (quickly – before anybody comes in) until the locker you are interested in is empty. Then you can put your things in – mission accomplished and most probably no one will notice that their stuff has been shifted by one locker! The second approach required only one hand and had the added benefit of being able to look nonchalant and guilt free if anyone walked in while you were half way through the exercise!

That row of lockers we were discussing just now is what we call an array in our programming world and is one of the first data structures that you are likely to use. And each of the lockers is an element of that array.

There, now you know some of the basics about single dimension arrays. Henceforth, whenever we discuss operations on the array, we will see how it can be achieved on the row of lockers first before diving [these swimming pool similes are too much!] into programming. Ok so far?