JavaScript Data Structures - The Linked List
Written by Ian Elliot   
Monday, 14 January 2013
Article Index
JavaScript Data Structures - The Linked List
Traversing the list
When to use a list

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.

Insert After

Another very common list operation is to insert a new element or indeed a complete list into an existing list. For data structures such as an array inserting data involves moving a block of data to free up some space for the items being inserted. In a linked list you don't have to do this because all you have to do is change some links.

For example to insert x into the list

A->B->C

after B all you have to do is create x and point it at what B was pointing at and set B to point at x:


A->B->x->C

This is fairly easy to program as long as you remember to keep the end pointer correct.

For example a method that inserts a new item of data following a node which stores a specified item of data is just:

 

this.insertAfter = function(t, d) {
 var current = this.start;
 while (current !== null) {
  if (current.data === t) {
   var temp = List.makeNode();
   temp.data = d;
   temp.next = current.next;
   if (current == this.end) this.end = temp;
   current.next = temp;
   return;
 
  }
  current = current.next;
 }
};

Notice that you only have to fix up the end pointer when the item is inserted at the end and you don't have to fix the start pointer because this method can't insert something before the first node.

Indexing

Where the linked list suffers is when you need to refer to nodes by an index value. That is when you want to pretend that a linked list is an array. The only way of retrieving say the fifth element in the list is to traverse the list and stop at the fifth element.

There are many ways to keep a count of how many elements you have retrived, here is just one:

this.item=function(i){
 var current = this.start;
 while (current !== null) {
  i--;
  if(i===0) return current;
  current = current.next;
 }
 return null;
};

 

You could also use a for loop but if so you would need to check that the index was in the range of the list or include a test for the end of the list.

Notice that this indexing routing returns the entire node and not just the data. In most cases it would probably be better to return the data but then you would need an item get and an item set method.

Each

As a final example a useful method and one that is in line with functional thinking is the each method which applies a function to each element of the list.

this.each = function(f) {
 var current = this.start;
 while (current !== null) {
  f(current);
  current = current.next;
  }
};

 

For example you could use this to display the entire list using an alert function:

list.each(function(item) {
 alert(item.data);
});

Banner

<ASIN:0596517742>

<ASIN:0470647833>

<ASIN:0980285844>

<ASIN:0321572602>

 



Last Updated ( Tuesday, 15 January 2013 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.