A List Object

Of course manually creating  node each time you need one and manually adding it to the list isn't really the best way to do things. A much better idea is to create a List object that can be used without much information about its inner workings. That is the List object stores and retrieves data from a linked list.

Obviously as we are going to want to create perhaps multiple List objects we are going to have to implement a constructor

function List(){

We also need an easy way to create a node and one possible way is to provide the constructor function List with a makeNode method:

List.makeNode=function(){
 return {data:null,next:null};
};

If this seems strange to you recall that a function is also an object and can have methods and properties. This approach is similar to providing class or static methods and properties.

We need some properties to record the start and end of the list:

this.start=null;
this.end=null;

It is possible to avoid having to record the end of the list by performing a traverse of the entire list each time you need to access the end - but in most cases storing a reference tot he end of the list is more economical.

Next we need an add instance function. This uses the static makeNode function and has to set the start, end and next references correctly. If the list has just been started then start and end will be null and we need to set them:

this.add=function (data){
 if(this.start===null){
   this.start=List.makeNode();
   this.end=this.start;
 }

You can see that in this case all you have to do is set the start and end to reference the new node.

If the list has already had some nodes added you need to add the new node to the end of the list and update end and the next property of the previous end node:

 else{
  this.end.next=List.makeNode();
  this.end=this.end.next;
 };

And finally we can set the data in the new node:

this.end.data=data;
};

Using the add method we can create a linked list with as many nodes as we care to use. For example:

var list=new List();
for(var i=1;i<=10;i++){
 list.add(i);
};

creates a list with ten nodes containing data 1 to 10.

Traversing the List From Start to End

At this point we could add lots of different methods that access and modify the list. Most of these would do their tasks by traversing the list and making changes to the next "pointers" to reorganize the list.

The key idea is the loop that traverses the list:

var current = this.start;
while (current !== null) {
 do something which the current node
 current = current.next;
}

Of course traversing the list the other way round is far less easy. It is so difficult that if you want to do it then you really need to implement a doubly linked list. A doubly linked list has an additional reference that "points" to the previous node. This allows you to start from end and work your way up the list to the start. It also means that you can move easily in either direction from the current node.

Insert As First

One of the basic list operations is inserting a node at the start of the list.  This is fairly easy and a good introduction to working with lists in terms of their "pointers". In this case all we have to do is create a new node, set its next to point to the current start and set the current start to the new node:

this.insertAsFirst = function(d) {
 var temp = List.makeNode();
 temp.next = this.start;
 this.start = temp;
 temp.data = d;
};

Delete Node

A more complicated "pointer" operation is deleting an element from from a list.

For example to delete the first node with a particular item of data you would need to find a node that matched and then simply set the previous node's next to "point" at the matched node's next. That is to delete node B:

A->B->C

you change A to point at C:

A--->C
B

You don't have to explicitly delete B because as soon as it has no references to it the JavaScript garbage collector will delete it.

The only irritation with this algorithm is that what you do is different if you want to delete the first node because you need to update the start pointer and if the node is the last node you need to update the end pointer.

this.delete = function(data) {
 var current = this.start;
 var previous = this.start;
 while (current !== null) {
  if (data === current.data) {
   if (current === this.start) {
    this.start = current.next;
    return;
  }
  if (current == this.end) this.end = previous;
  previous.next = current. next;
  return;
 }
 previous = current;
 current = current.next;
 }
};

The while loop scans the list from the first to the last node. Two variables are used to keep track of the current node being examined and the previous node.

Keeping the references in the list is a matter of book keeping - but book keeping that can be hard to get right. Always check that your methods work for the first and last elements of the list as well as the typical elements in the core of the list.

<ASIN:1871962579>

<ASIN:1871962560>