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

The Head and the Tail of it - Lisp Lists

There is another way to build a list structure as a two part data type that stores the head of the list i.e. the first element and the tail of the list i.e. the rest of the list. This is the approach used by Lisp and by many functional languages. It is entirly equivalent to the approach using pointers but it often looks very different. The difference is that instead of considering the node the basic element of the list we work in terms of a list composed ot a head element and a pointer to the rest of the list. Of course the rest of the list has a head element and a pointer to the rest of the list.

You can see that this sort of definition of a list is idea if you want to implement recursive functions. However it is very easy to write methods that give you the head and tail of a list from the sort of data structure described here.

For more information see:  JavaScript data structures - a Lisp-like list

 

When To Use a List

Linked lists are generally good at representing data when the fundamental operations are insertion or deletion at the start or end. In this sense they are very like the stack - indeed you can use a linked list to implement a stack. However they are also very good at inserting and deleting elements in the middle of the list. What they are not so good at is finding an element or finding the fifth, sixth or nth element. They are basically sequential access data structures.

In JavaScript you can generally avoid using lists by using the Array object either as an array or as a stack. Inserting and item in the middle of an array requires you to move a lot of data to create a free space. Insertion in the middle of a list only involves the manipulation of two pointer. This is the key observation concerning when you should use a list. If the data being stored is "big" and moving it around would take a lot of time then use a linked list. If the data is "small" then you might as well use a simpler data structure. Notice that "big" and "small" here really refer to the amount of data you are moving in a typical operation.

Listing

The complete code for the List constructor is:

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

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

 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;
   }
 };

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

 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;
   }
  };

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

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

 

If you would like the code for this project then register and click on CodeBin.

If you would like to be informed about new articles on I Programmer you can either follow us on Twitter, on Facebook , on Digg or you can subscribe to our weekly newsletter.

Further Reading

JavaScript Books (2012)

 

See also:

 

 

Banner


Just JavaScript - Object Construction

Object creation is fundamental to all object-oriented languages, but in JavaScript is is left to the programmer to work out how best to do it and often the practice that you encounter isn't the best b [ ... ]



Just JavaScript - The Object Expression

As in most programming languages the expression is an important part of JavaScript, but it isn't quite the same. This is where the idea that JavaScript has some weird type conversions arises. But Java [ ... ]


Other Articles

<ASIN:0470525932>

<ASIN:0596806752>

<ASIN:0321683919>

<ASIN:059680279X>

 

 



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.