JS, React, Redux, Ruby, Rails, SQL, Python
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?
The concept of a Linked List has at least two things:
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) end
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:)
Create your free account to unlock your custom reading experience.