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 belongings (data)
- 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:
class StorageUnit
attr_accessor :data , :next
def initialize(data, next_node = nil)
@data = data
@next = next_node
end
def setNextUnit(data)
nextUnit = StorageUnit.new(data, nil)
current_unit = self;
if (nextUnit.instance_of? StorageUnit)
current_unit.next = nextUnit
else raise('must be a storage unit')
end
end
def get_next_unit
return self.next
end
end 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 LinkedList
attr_accessor :head
def initialize()
@head = nil
end
def add_to_head(data)
new_head = StorageUnit.new(data)
current_head = self.head
if(!current_head)
self.head = new_head
else
new_head.next = current_head
self.head = new_head
end
end
def print_list
current_unit = self.head
output = '<head> '
while(current_unit != nil)
output << current_unit.data.to_s() + ' '
current_unit = current_unit.get_next_unit()
end
output << ' <tail>'
puts output
end
end 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.
def add_to_tail(data)
new_tail = StorageUnit.new(data)
current_unit = self.head
while(current_unit.next != nil)
current_unit = current_unit.get_next_unit()
end
current_unit.setNextUnit(data)
endRemember 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:)