The Missing Link
I like to start off Metaphysically then move down into the specifics of something. So then why are Linked Lists useful in software? Well I’ll answer with the question “Why have belongings if you have no place to store them?”; What good are your belongings if you cannot keep them anywhere? A Linked List is a “data structure”; a data structure is just a way to organize data; a way to organize your belongings metaphysically. There are the obvious built in data structures like objects and arrays and there are the modified data structures like Linked Lists. These lists are just POJOs in JavaScript or a POROs in ruby(yes I know everything in ruby is an object). But there has to be more to it than that, and there is. The concept of a Linked List has at least two things:
- it has a belonging (data)
- 2) it has pointers to other storage units.
Software tutorials often call the basic unit of storage a Node. I’ll call it a storage unit to make it real and fun. Our Storage Unit has data and it also has a map to other storage units; traditionally this is called the “next” node. It can tell us were the next storage unit (doubly linked lists have a map to the previous storage unit as well). There are many ways to implement this but lets code it out in ruby.
As I said our StorageUnit will need two things: a belonging object (data) and a map to the next or in code StorageUnit.next (pointer to the next node). When you write good software you should assign functions, objects, and classes methods that would make sense in the real world. Ask yourself is it a Storage Unit’s job to know about the other storage units? That would not make sense in the real world. In reality the Owner of a storage unit or a storage unit building itself would be in charge of that. We will essentially do the same and have our Linked List be in charge of adding, removing, and retrieving all the data from the storage unit. Now to be a true linked list each unit will have to know about the next unit so by definition each storage unit will know about the next:
We have a class StorageUnit which we will use as a node in our linked list. It has a data property and a next property. Now we will use this node to create a linked list.
class LinkedListattr_accessor :headdef initialize()@head = nilenddef add_to_head(data)new_head = StorageUnit.new(data)current_head = self.headif(!current_head)self.head = new_headelsenew_head.next = current_headself.head = new_headendenddef print_listcurrent_unit = self.headoutput = '<head> 'while(current_unit != nil)output << current_unit.data.to_s() + ' 'current_unit = current_unit.get_next_unit()endoutput << ' <tail>'puts outputendend
Our linked list has fundamental functionality where we can add to the head of the list. As this is a singly linked list we only have a head property. How do you think you could add to the end? Software has the same principles regardless of language you use. Adding to the beginning was simple. We just inserted a new head. We have this data structure of objects that all have a pointer to the next in line. What do you think about adding to the end?
What do you know? You have data and a head and a next. You could start at the head and traverse it with the next property until the next property is nil. At this point you have reached the end of the linked list.
Remember that you are very smart and software languages are all essentially the same; especially interpreted dynamically typed languages. These languages understand far less than you. When you run into problems remember this language is so dumb one little character will cause it to break. You just have to be as dumb as the computer to make it work!
Time for homework. Can you write a method to find a StorageUnit based on what is inside? Please do this to really seal the idea of a linked list in your brain. You have come this far already so I’m impressed. Good job coder, you make me smile:)
