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

• Ian Elliot is the author of  Just JavaScript: An Idiomatic Approach; JavaScript Async; Just jQuery: The Core UI and Just jQuery: Events, Async & AJAX which are part of the I Programmer Library published by I/O Press.

Further Reading

JavaScript Books (2012)

JavaScript Data Structures 

Contents

1. The Associative Array
2. The String Object
3. The Array object
4. Speed dating - the art of the JavaScript Date object
5. Doing JavaScript Date Calculations
6. A Time Interval Object
7. Collection Object
8. Stacks, Queue & Deque
9. The Linked List
10. A Lisp-like list
11. The Binary Tree
12. Bit manipulation
13. Typed Arrays I
14. Typed Arrays II
15. Master JavaScript Regular Expressions
    * First Draft

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:1871962579>

<ASIN:1871962560>

<ASIN:1871962501>

<ASIN:1871962528>