 |
| Link from The Legend of Zelda |
They say you will have a good social circle if you focus on the good in people and ignore the bad. Gratitude is the key to success and riches. But at the same time you need to find problems so that you will seek solutions and not seat around satisfied with what little you have. To help us with both these views, thank Gods we have with us today: Mr. Optimist as well as Mr. Pessimist. The thing is, these two lads can't talk to each other without biting teeth. This is how the discussion ended up while they were talking about our friend caterpillar last night over a few pitchers of beer which is the only thing they seem to enjoy together and agree on.
Mr. Optimist: My dear friend caterpillar eats happyly (Insertion in an array is easy).
Mr. Pessimist: Well only until you allow her to eat all the junk she gets her hands on (Insertion in a sorted array is not as easy). And by the way, there is an I in happiness.
Mr. Optimist: Well she knows where the stuff is going (Random access to any element of an array is easy-index based access). And by the way, you pessimist! What do you know about happiness? You are my tragedy queen.
Mr. Pessimist: I guess by know you know how hard it is to find where all the wrong stuff ended in her stomach the last time she munched on those chocolates (searching in an array is tough, so is deletion. Further, deletion involves moving elements to fill the place of a deleted element). And yeah, don't forget what a trouble it is to move things around in her belly.
Mr. Optimist: Yeah yeah, you don't have to care for her eating habits; I can take care of her. And by the way, she can eat only so much. She knows when she is full (Array size is fixed).
Mr. Pessimist: Yeah, that's another headache, sometimes we need to eat more just to finish what was served simply out of courtesy. But she is adamant and stubborn and arrogant. She won't take an extra bite.
Mr. Optimist: Go away you moron.
Mr. Pessimist: Shut up you .......
While Mr. Optimist and Mr. Pessimist fight over the good and bad of our cute caterpillar, let's introduce ourselves to a bit more sophisticated data structure and let's find out if it is worth extending our friendship to. Is it any better than our little caterpillar? I am even considering hanging out together with the Caterpillar and this new friend if it is worth it.
Please welcome majestic Mr. Link A.K.A Linked List.
Definition of a Linked List:
A linked list is a linear collection of data elements called nodes pointing to the next node. Each node has a reference to the next node. It is a data structure consisting of a group of items which together represent a sequence.
A Detour:
To imagine, understand and remember Linked list forever, we will use something unique but wonderful. With the help of this unique tool, we can remember not only the implementation of linked list, but also any list of items, tasks, states of a country or anything that comprises of items linked to each other.
You may not know (Hopefully you did not notice it in my blogs), but I always had difficulty in forming and remembering spellings for English words (I still do). I knew it and I wanted to change it. So I was searching for some wisdom, technique, procedure or steps that will help me conquer this difficulty. I browsed internet, went through blogs, read books but nothing quite convincing came across. Then one fine day, I got reference of this book called "The memory book" by Harry Lorayne and Jerry Lucas. This book changed the way I remembered everything.
This book has several memory techniques to help remember all kinds of things. One particular technique called "The link system" caught my eye as it helped me understand and remember the data structure Linked List.
The link system:
Suppose we have following list of items to remember:
- chocolate
- Apple
- Table
- Shoe
- Museum
Let's assume we remember chocolate easily because you like it. lolz, nope, but because it's the first item in the list. There is a way to make sure that we use a system to remember this first item as well but let's not go in those details as we are good with this assumption. Now, to remember rest of the items, we are going to link each item to the previous one in such a way that if we remember chocolate, we will remember apple and the apple will lead us to the next item in the list - table. The table will then remind us of shoe which will finally remind us of Museum.
The trick here is to make the first item a trigger to the memory of next item in the list.
As per our assumption, we already know the first item chocolate. Now, as per the system, our task is to link chocolate to apple. To achieve this, we need to associate chocolate to apple in some ridiculous way (Note: There is science, evolution and neurology behind the fact that a ridiculous imagination works. I would humbly avoid getting into those details at this moment.). Imagining that a huge chocolate is eating an apple instead of me does the trick for me. So the current state of my memory can be summarized as shown below.
The trick here is to make the first item a trigger to the memory of next item in the list.
As per our assumption, we already know the first item chocolate. Now, as per the system, our task is to link chocolate to apple. To achieve this, we need to associate chocolate to apple in some ridiculous way (Note: There is science, evolution and neurology behind the fact that a ridiculous imagination works. I would humbly avoid getting into those details at this moment.). Imagining that a huge chocolate is eating an apple instead of me does the trick for me. So the current state of my memory can be summarized as shown below.
Now, to link apple to the table I imagine that a huge table is sitting on a huge apple.
By continuing the same process for shoe and museum, we get the following in memory.
That's it. We have remembered the required list of items. Now you can recall it anytime you want. If you no longer want to remember it, no worries, it will gradually fade away as well. This system is really wonderful and it potentially lets you remember any list with ease no matter how long it is and how long you want to remember it.
If I need to add an item to the existing list, I just need to reimagine the new link
If we need to delete an item from this list, it's also a matter of some re-imagination and re-association.
Wasn't it easy and fun? This was nothing but a real life breathing and living example of a linked list data structure. Now, do go through the definition of linked list and the final image of your small memory map above. Aren't they similar? Now it's just a matter of putting it all together in your favorite programming language.
Implementation:
To implement linked list as a data structure let's redraw our list of items with some new labels.
Let's make it further data structurish:
Looking at the above diagram, to implement this linked list in java, we need following steps:
- A class called LinkedList.
- A reference (start) to the first element in the linked list. When this list is empty, start will be null.
- A class called Link which has two attributes:
- data - it is the actual data being stored.
- next - it is of type link again.
Insertion and deletion are a matter of some re-association as discussed for the list of items to be remembered.
I think the data structure linked list is now under your belt. Do let me know your views on the same.
As usual, comments/appreciation/criticism (a constructive one of course) everything is most welcome and appreciated.
Until then,
Happy Learning!
Banyan Bat
