Assignment 4 – Lists
Objective
Demonstrate the structure and produce code to implement a List
Supports Outcomes:
1. Describe both complex and simple data structures.
3. Implement data structures and algorithms in computer code.
Summary
Lists are one of the most fundamental data types. Your ability to understand lists as an Abstract Data Type (ADT) and implement lists is key to your understanding of all the more complex data structures. In this module, you should first completely review Topic – Basic Data structures which cover lists. Once complete, you should be ready to tackle some of the challenging assignments available in this module.
Lectures
Before you start, you should watch
1. Arrays and Lists (BrightCove | Youtube ) and
2. Creating a Linked List (Brightcove | Youtube )
Please review all lecture materials at All Course Lectures – these are all there to help.
By this point, you should have completed the entire Javascript tutorial at W3 Schools or be familiar with Javascript.
Assignment
In Javascript, we are going to create a Doubly Linked List. (A Singly Linked List is another example of a type of List – they do the same thing). 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;
Node 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
List 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. It should be a good demonstration for you to use in writing your code. https://jsfiddle.net/reaglin/q46obht6/ This code should help you get started, but you should build your List and Node objects from scratch.
Next – you will populate your list with an initial node with the content “First Node.” You will also create a print function for the list to print the nodes in order. You will need to create some functions to support this functionality.
You will now need to write an interface to allow the user to add nodes to the end of the list. There should be a single text box to enter the Node content and a button “Add to List.” When the user adds a node to the list, then you should add the node with the content to the end of the list and print the new list.
If you have questions, you MUST post them 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.
Submission Instructions
You will submit a link to your code in JSFiddle.
Information
Note that I use the underscore ( _ ) to differentiate between passed variables to a function and properties of the function. So I pass _content to the function and then set the property of the function equal to the passed value. In the example below, value is a property of the function, _value is a passed variable to the function.
function Afunction(_value) {
this.value = _value;
}
The reason for the underscore is simply a coding convention, you should always employ consistent conventions to make reading your code easy when you have to come back to it later.
To define a Node object in JavaScript with the properties required by the assignment – the following code will create the object.
function Node(_content) { // Implementation of a doubly linked list (last and next pointers)
this.content= _content; // The value stored
this.last = null; // A pointer to the previous link
this.next = null; // a pointer to the next link
return this; // returns the created node
}
|
To define a List object in Javascript with the properties required by the assignment – the following code will create the object.
function List(_content) { // We will define the list with the first link defined
this.length = 1; // Technically the list does NOT need a length property
this.head = new Node(_content); // Creates the first Node
this.last = this.head; // When created - head and last are the same. Note - technically a List does not need a pointer to the last node
return this; // Return a pointer to the newly created List
}
|
To Instantiate (Create) a Node Object named aNode with content _content.
Note: You need to understand the difference between creating (defining) an Object and Instantiating an Object. If you do not – immediately do some research and get help (discussion boards might help here). YOU MUST UNDERSTAND THIS CONCEPT.
var aNode = new Node("Node A"); // Instantiates a Node object named aNode with passed content "Node A"
|
To Instantiate a List Object named aList (this List will be created containing one node with content _content). You MUST MUST MUST understand the difference between defining objects and instantiating objects, or you will be hopelessly lost the entire class.
var aList = new List("Node A"); // Instantiates a List object named aList
|
This should be sufficient code to help you get started. You are welcome to use my code examples which do vary from the code I have given you here. You should definitely watch the video segments on Lists at All Course Lectures
Assignment Grading – This assignment is fundamental to the knowledge and operation of all the remaining data structures. You must be able to implement your linked list. You must implement a function to the list to add nodes (onto the end of the list), 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, implementing a List print function and a List addNode function. Code to create the list by adding the first node – must all work correctly.
You’re making a list – I’m checking it twice.
Note: You will be using this code for Assignments 5, 6, 7, and 8. It is pretty important to understand the code you are writing and be able to modify it to do what you want it to do.