The Missing Link: Why Are Linked Lists Useful in Software? | Hacker Noon

Author profile picture

@SwordfishRandy

JS, React, Redux, Ruby, Rails, SQL

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: 

  1. It has a belongings (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: 

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:)

Tags

Join Hacker Noon

Create your free account to unlock your custom reading experience.

read original article here