Seekers Guide To Linked List

You know you’re a total Potterhead when you start writing about a data structure based on Harry Potter series.

I may not be as great as a writer as JK Rowling. Heck, I am no writer. I am just a developer with a huge love for HP series who has just lost her mind after learning all the data structures in a week. Whose brain is playing tricks to her by mixing real, reel and programming life.

So, hang on tight, prepare for more adventures in this Potterverse.

Ahoy, Hogwardians!
YOU ARE INVITED FOR SPECIAL CANDIES HUNT AT HARRY’S BIRTHDAY BASH
On winning you’d be considered worthy of a Chocolate Frog card
See you there if you dare!

 

Ronald Weasley considered being put on a chocolate frog card as greatest achievement for any wizard. Challenge accepted, he muttered under his breath and sent an owl out for the confirmation of being part of this majestic quest.

The D-day arrived.

Harry started explaining the rules to his fellow Hogwardians.

The hunt is quite simple, he said.You will all get your first clue and one candy. This clue will help you to find next clue/candy and your chance to be part of chocolate frog card.

Once you crack the first one and you get there, Boom, Acid Pops candy with another clue. This clue there will tell you how to get to the next candy & clue combo. You go there and there’s a Chocolate Cauldrons candy with another clue. Eventually, you find a Chocolate Frogs in the Red Wrapper that doesn’t have a clue with it. That’s the end of the candies hunt.

So, did Ron get on a Famous Witches and Wizards card?

Yes, he did get his treat and so did you!

Confused?

Accio, Linked List!

A linked list is a collection of multiple nodes where each node stores a reference to a data, as well as a reference to the next node of the list

Yes, Yes…I hear you screaming at me. Let me rephrase the definition with keywords from our above hunt example.

Candy + Clue = Combo (Node)

Candy Bar = Combo’s Data part (Data attached to the node)

Clue = Combo’s Reference Part (Pointer that tells you the address of the next node)

A linked list is a collection of multiple candy & clue combo(nodes) where each candy & clue combo (node) stores an candy bar (data), as well as a clue (reference to the next node) of the list.

The first and last candy & clue combo are known as the head and tail of the list. By starting at the first combo, and moving from one combo to another by following/cracking each combo’s clue, we can reach the Chocolate Frogs candy(tail of the list).

Simple, right?

Bunch of nodes each storing data and address of next node. Kind of work which our beloved array can do quite easily. Why bother studying linked list then?

Linked List Vs Array 

An array is like a fixed-size Harry Potter novel. The moment J.K. Rowling ran out of available space to write in the book, she put up remaining contents in next book. Linked List would be a dynamic-size Harry Potter novel powered by Undetectable Extension Charm( remember, Hermione’s beaded handbag?) which will never make her run out of space.

Well someone pointed it out to me that I’ve forgotten to add Bertie Bott’s Jelly Beans into candies hunt.

No issues. I’ll just put it into third candy & clue combo and make second combo clue give reference to it. Thank you linked list for making my life simple. But if you want to subject someone to Umbridge level detention, ask them to do the same with an array. I must not insert random elements in an array. Why? Moving each and every single candy to make room for new one is painful.

Hey, wait before I start shuffling the nodes in my linked list, can you help me with what candy was at position 3? Umm, does word position rings a bell? Wasn’t that array? But we are dealing with linked list? Wait do we have indexing here?

Nopety, nope!

So you have to read the first clue to find the second clue which then tells you where the third clue is. No shortcuts, no indexing. (I hear life with arrays is so so comforting). This is a  major disadvantage of all the advantages of Linked list.

(shitiest drawing you’d see on Internet today. Things I do to amuse myself.)

Hope this article was as informative as The Daily Prophet.

There, there! It’s not really goodbye, after all. I will be back with articles which will cover following things

  1. Time complexities
  2. Different types of Linked List.

Stay tuned!

Image Courtesy: HpStuffshttp

Get new blog posts delivered straight to your inbox. No Spam. I Promise.

Email *


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *