Module 3 A1

In Javascript we are going to create a doubly Linked List. If you need a little primer on creating objects and classes in Javascript see http://www.w3schools.com/js/js_object_definition.asp - if you know your object oriented code this will be relatively straightforward. Your List will be made up of Nodes. Each node will have the following properties; id - A simple id for the node itself, content - A value (String) next - A pointer to the next node in the List (null for the last node). last - A pointer to the previous node in the List Your List will have the following properties; head - Pointer to the first node in the list Length - Number of nodes in the list Here is a simple Javascript code that represents the concept using the analogy of a chain and links. It should be a good demonstration for you to use in writing your code. https://jsfiddle.net/reaglin/q46obht6/ You will make a List consisting of 5 nodes. You will also create a print function for the chain that will print the nodes in order. You will need to create some functions to support this functionality. If you have questions you MUST post to the bulletin board. All students who are in progress or working on this will be granted extensions if they are asking questions on the BB. Quizzes (Quiz Submission Instructions ) Quiz 1 - Complete quiz at http://geeksquiz.com/data-structure/linked-list/ Assignment Grading - This assignment is fundamental to the knowledge and operation of all the remaining data structures. You must be able to successfully implement your linked list. You must implement a function to the list to add nodes (on the end), and print the final list with all node values. You may use my code as a guideline - but should write this entire project from scratch. No grade will be assigned to this assignment until all functionality is implemented. Both objects coded correctly, implementation of a List print function and a List addNode function. Code to create the list by adding 5 nodes - must all work correctly. Your making a list - I'm checking it twice.

by Jenni Meiklejohn

HTML

Insertion <br/>
Add to List <input type="textbox" id="content"/>
<input type="button" id = "addToSortedList" onclick="addToList();" value = "Add to List"/>
<p id="list"></p><br/><br/>
 Random Generated List
<input type="button" id="generateRandomList" onclick="generateRandomList()" value="Generate Random List"/><br/><br/>
Bubble Sort Pass
<input type="button" id="bubbleSort" onclick="bubbleSort()" value="Demonstrate bubble sort"/><br/><br/>
<br/>
<p id="steps"></p>

JavaScript

var SortedLinkedList = function() {
  this.first = null;
}

var SortedLinkedListNode = function(_content) {
  this.content = _content;
  this.next = null;
}

SortedLinkedList.prototype.add = function(_content) {
  var node = new SortedLinkedListNode(_content);
  
  // no head - make head
  if (this.first == null) {
     this.first = node;
     return this;
     }
  
  // make new head if less than head   
  if (node.content < this.first.content) {
       node.next = this.first;
       this.first = node;
       return this;
     }
  
  this.first.add(this.first, node);
  return this;
}

SortedLinkedListNode.prototype.add = function(p, n){
   // put in front if less than
   if (n.content < this.content) {
     p.next = n;
     n.next = this;
     return this;
   }
     
   // put at tail if greater than and no next
   if (this.next == null) {
     p.next = this;
     this.next = n;
     return this;
   }
   
    // pass to next node if greater than and next exists
   return this.next.add(this, n); 
}

SortedLinkedListNode.prototype.sort = function() {
     
// sorts this.next with this.next.next
    if (this.next == null) {return null;}
    if (this.next.next == null) {return null;}

    var a = this.next;
    var b = this.next.next;
      
    if (b.content < a.content) {
     
     this.next = b; 
     a.next = b.next;
     b.next = a; 
  }
}

SortedLinkedList.prototype.bubbleSort = function() {

  if (this.first == null) {return this;}
  
  var a = this.first;
  var b = this.first.next;
  var c = this.first.next;
  
  if (b.content < a.content) {
     
     document.getElementById("steps").innerHTML += 
      "Swapping " + a.content + " and " + b.content + "</br>";          
     a.next = b.next;
     b.next = a; 
     this.first = b;
  }  
  
  var current = this.first;
  while (current.next != null && current.next.next != null) {
  current.sort();
  current = current.next;
  }
  
}

SortedLinkedList.prototype.create = function(n) {
for (var i = 1; i < n; i++)...