Meet the Caterpillar....Data Structures Begins...

"And whats a butterfly? At best, He is but a caterpillar, at rest." - John Grey

"To become a butterfly, you must first start as a caterpillar."

You must be wondering, why the hell is he writing about caterpillars and butterflies in a post that claims to talk about data structures. I believe there are a few things about the caterpillar that will help us understand and remember today's data structure.

First of all, isn't the caterpillar cute? The caterpillar does not even know that its going to become something else entirely and the world out there is going to compare it with its own next stage, the butterfly. I believe the caterpillar enjoys being a caterpillar as much as it will enjoy being a butterfly. 

The caterpillar is a perfect example of the fact:

"Some things which look like miracles, might just be a result of patience and perseverance. What looks like impossible today may eventually be nothing more than a few steps taken one at a time."

Okay, enough of philosophy.

Lets get started, So why caterpillar anyway? Consider the following few features of a caterpillar:

• The caterpillar has those beautiful scales( or segments), our caterpillar for example has 6 scales.
• The number of scales the caterpillar has is not going to change now, or is it? The number is fixed.
• Go ahead and watch a video of this cute creature walk. No I mean it, really watch it. Its fun, isn't it? When this cute creature walks, you can literally see all its scales moving forward/backward. And the first thing you will notice is: Damn, its slow!!

With this introduction to our cute caterpillar, can you guess our first data structure? Yes, you guessed it right.

Ladies and gentlemen, Please welcome the cute little master Array. 

Master Array:

"We are Arrays.. We are Arrays... you can feed us chocolates, you can feed us berries.. we are arrays.. we are arrays"

Banyan Bat: Stop singing!! So what exactly are you? And by the way, why would I feed you chocolates?

Master Array:

"Dude, come on, I am a data structure.........didn't you see the picture?

 Give me some chocolates........, I will keep them each on its own place!!!

its not gonna be so much fun ....if you try to snatch one..."

(An Array is a data structure consisting of a collection of elements, each identified by at least one array index or key. A simple array of size 7 holding 5 integers(elements) can be represented by the following diagram.)

I know I know, we will get back to the why caterpillar question in a while.

As you can see, an array has a fixed size. You can't attach a scale to a caterpillar. Can you? You can add stuff until you reach the max size. come on, this must have rang some bells… what? ...it did not??

The following diagram shows the usual basic fun activities (operations) that we will be focusing on while discussing any (data structure - come on!! Do I really need to say data structure) creature/character/Movie/Superhero - you name it. 

Basic Data Structure Operations

(Feed me!!! I am Hungryyyy) Insertion: 

Although our cute Caterpillar mostly eats the green leaves and obviously through his mouth, in an Array, insertion happens at the first empty place available. So in the above diagram, its the index 5.

Google (Oh well, back in the history, it used to be called Search): 

To search an element in an array, you just walk by each place (Index), checking for your element, if you find it, Holla!!!! you return it’s index. You can refer the diagram below if you wish.

If after reaching the last element you do not find your element, usually you return -1 indicating an invalid index representing the fact that the element you were searching was not found.

(Snatch that chocolate) Deletion:

Do you really think snatching that chocolate from the caterpillar would be any easy? Try doing that to a baby and you will know it. They are more powerful than you think :)

To delete a specific element from an array though, we follow the following steps:

1. Google the element (you know how it works),
1. If the element is not found, there is nothing to delete. Your job is done.
2. Otherwise go to step 2 below:
2. Delete this element. (You know the index of the element as a result of that google step). And move all the elements after this element one index backwards - this is what really sucks. Everything moves one step back to fill the newly emptied scale. 

The process can be better explained with examples and figures:

Here you go:

Delete from Array

The search we discussed above is called a linear search, because it goes over the array elements, one at a time in a sequential manner. Hence, the amount of time required to find an element will vary depending on the actual index of the element to search and will be proportional to the length of the array. Consider the worst scenario (I am not talking Worst Case - that's a terminology of  data structures and algorithms. I would love to keep away as far as I can) in which, the element could be the last element in the array.

Now, do you get why the caterpillar is our cute friend? Dose it ring any bells finally? I think I should leave you with this question and move on. I should let the arrays and caterpillar marinate in your head and move on with the discussion. Don’t eat the marinated caterpillar. I don’t know how it would taste. If it did ring bells in your head, do comment and let me know, otherwise, at the end of this post, under Post Scriptum-1, you will find my answer to this question.

So, now we have a basic data structure (Array) under our belt. This would be a powerful asset for us throughout our study of data structures and algorithms. 

After all, 

The caterpillar does all the work but the butterfly gets all the publicity. - George Carlin

We know how to feed a caterpillar, snatch something from it and yeah do some googling on it. Whenever we use this data structure, we will end up searching elements a lot. If our array is large, our leaner search will take quite some time.

Is there a way we can improve this search? Sleep over this thought and do comment if you find the answer.

We will try to explore this in our next post.

As usual, comments/appreciation/scoldings everything is most welcome and appreciated.

Until Then,

Happy Learning!

Banyan Bat

Post Scriptum

1: Do you really think I will write the answer to that question here? Tell me you don’t.

2: I know for most of you this post might have been a breeze and even boring because Array is the most studied data structure. But I have written this post to establish a continuous tone and to make sure that if someone really new to data structures starts reading this blog, they really get some value out of it.

3: I have deliberately left code and formal algorithms out, because I believe the internet is flooded with amazingly beautiful and powerful implementations. And my drop in the ocean will hardly make any point. Instead, I am trying to focus on the understanding and remembering part of it hoping to help you retain what you will grasp by reading all those wonderful books out there. 

Last but not the list, I hope that the caterpillar gave a new funny and interesting image to an otherwise considered trivial and boring data structure.