| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

Full Javascript Implementation of a Singly Linked List

Page history last edited by Dr. Ron Eaglin 4 years, 11 months ago

 

 

This uses the implementation available at http://www.choskim.me/linked-list/ - here we analyze ALL elements of the Javascript code.

 

var makeLinkedList = function() {

  /*
   * Creates an object with its 
   * prototype referencing 
   * methodsOfLinkedList
   */
  var instanceOfLinkedList = Object.create(methodsOfLinkedList);

  /*
   * Sets the initial head of a 
   * list to null
   */
  instanceOfLinkedList.head = null;     

  /*
   * Sets the initial tail of a 
   * list to null
   */
  instanceOfLinkedList.tail = null;

  /*
   * Returns an instance of a 
   * linked list
   */
  return instanceOfLinkedList;
};

 

Here is a line by line analysis of the code;

 

var makeLinkedList = function() { 

You are defining a variable named makeLinkedList. In Javascript all variables are objects - in fact everything is an object. This means - a function is an object - and it can have a name and can be declared using the syntax shown here - where we say makeLinkedList is a function. A function can even be passed to another function (though we are not doing that here)
var instanceOfLinkedList = Object.create(methodsOfLinkedList);

We are creating ANOTHER var (another object) - this time called instanceOfLinkedList. This time we use a built-in Javascript method called Object.create there is a lot to learn about Javascript objects - get busy http://www.w3schools.com/js/js_objects.asp - Here we are creating an object and it will have the methods and properties of methodsOfLinkedList - more about that later.
instanceOfLinkedList.head = null;

We just set the head property of instanceOfLinkedList to null - I sure hope this is defined somewhere.
instanceOfLinkedList.tail = null;

We just set the tail property of instanceOfLinkedList to null - I sure hope this is defined somewhere.
return instanceOfLinkedList;

So if we call this function - it is a function - get it? It will return an actual instance of a linked list, the one you created inside the function.
   

 

OK - so that is half the battle, we also are depending on this magical methodsOfLinkedList and it needs to also be defined. So here is the code for that.

 

var methodsOfLinkedList = {  
  add: function(value) {

    /*
     * Creates a new instance of a 
     * node.
     */
    var newNode = makeNode(value);

    /*
     * If the list is empty, 
     * then assign the new node 
     * as the head of the list.
     */
    if (!this.head) {
     this.head = newNode;
    } 

    /*
     * If the list contains a 
     * tail, then assign the new 
     * node as the next node in 
     * the list.
     */
    if (this.tail) {
     this.tail.next = newNode;
    }

    /*
     * Assigns the new node as the 
     * tail of the list.
     */
    this.tail = newNode;
  },

  remove: function() {

    /*
     * Creates a variable that 
     * references the current 
     * head of a list.
     */
    var currentNode = this.head;    

    /*
     * Assigns the head of the 
     * list to the node next to 
     * the current head. 
     */
    this.head = currentNode.next; 

    /*
     * Sets the initial head of 
     * the list to null. 
     */
    currentNode = null; 
  },

  contains: function(value) {

    /*
     * Creates a variable that 
     * references the current 
     * head of a list.
     */
    var currentNode = this.head; 

    /*
     * Continues iteration while 
     * there is a node in the 
     * list.
     */
    while (currentNode) {

      /*
       * If the current node matches 
       * the target value, then 
       * return true. 
       */
      if (currentNode.data === value) {
        return true;
      }

      /*
       * Assigns currentNode to 
       * reference the next node 
       * in the list. 
       */
      currentNode = currentNode.next;
     }

     /*
      * Returns false if there are 
      * no matches in the list.
      */
    return false; 
  }
};

 

var methodsOfLinkedList = { 
OK - by now you have probably figured out we are defining a var - which is of course an object. 
 add: function(value) {
Look - this new object has a property called add - which is a function (yes properties can be functions! - this is Javascript - everything is an object). And look we have a new notation to soak up. The notation here is called JSON (Javascript Object Notation) - something new to learn http://www.w3schools.com/json/default.asp - It is used because it makes it REALLY EASY to define objects and understand what you are creating.
    var newNode = makeNode(value);



    if (!this.head) {
     this.head = newNode;
    } 


    if (this.tail) {
     this.tail.next = newNode;
    }

    this.tail = newNode;
  }

This is the rest of the add property (which is also an object and is also a function - get over it). Look - we create YET another Object - this time called newNode and we use yet another undefined function called nameNode. Great! something else we will have to define later.

 

Now we have something else we have never seen - this.head - OK this must be a reference to itself. Yes an object sometimes needs to refer to itself from inside itself - and it can do this using the this - which is by the way a keyword. The logic here is if this does not have a head (it is empty or null) then the head of this IS - yes you got it, the newNode you just created.

 

And... If this is the tail - well, it is not the tail any longer, now the newNode needs to be the tail, and of course it need to be added to the end of the List. Wait - where did next come from?!!!

 

BTW - the added newNode is always the tail, and of course if there is one node, it is both the head and the tail.

 

So the only thing we don't have defined here is next - that just came right out of the blue

remove: function() {

    var currentNode = this.head;    

    this.head = currentNode.next; 

    currentNode = null; 
  },

Chopping off the head - I'm sorry - this is actually remove - it removes the head and moves everybody up. Please note that there are few properties of a List that are not implemented in this example, have fun...
  contains: function(value) {

    var currentNode = this.head; 

    while (currentNode) {

      if (currentNode.data === value) {
        return true;
      }

      currentNode = currentNode.next;
     }

    return false; 
  }
By now you should be able to figure out what this one does - it is pretty basic - and remember these are ALL properties aka function aka objects within methodsOfLinkedList

 

We only have a little bit more to do - - we see that we have this newNode in the code, and we also know that it must have a property called next. Don't go any further until you are comfortable with what I just said from analyzing the code above. When you are ready - we will do the last object in one explanation.

 

var makeNode = function(value) {

  /*
   * Creates an object with the 
   * two properties of a node.
   */
  var instanceOfNode = {
    data: value, 
    next: null
  };

  /*
   * Returns an instance of a 
   * node.
   */
  return instanceOfNode; 
};

OK - this is getting repetitive. I created a variable/object which is a function - and it gets an argument (value) - which is going to be the value stored in the node. Remember - you are making these structures to store stuff!

 

 

 

 

The instanceOfNode has 2 properties, data (which is assigned the value passed to it) AND next (which is not defined until it is added to the list.

 

 

 

 

And - of course we return the instance of the node we just created.

 

OK - I am sure you want to create and play with this code so here is how to implement this Linked List - just give it a try - or use my Fiddle -http://jsfiddle.net/reaglin/f8y3w9zw/ 

 

var myLinkedList = new makeLinkedList;
myLinkedList.add('Yo - I am a Node');
myLinkedList.add('So am I');

alert(myLinkedList.head.data);

 

 

 

Comments (0)

You don't have permission to comment on this page.