JavaScript Data Structures - The Linked List
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.

Further Reading

JavaScript Books (2012)

 


JavaScript Data Structures 

Cover

Contents

  1. The Associative Array
  2. The String Object*
  3. The Array object
  4. Typed Arrays I*
  5. Typed Arrays II*
  6. Speed dating - the art of the JavaScript Date object
  7. Doing JavaScript Date Calculations*
  8. A Time Interval Object*
  9. Collection Object
  10. Stacks, Queue & Deque
  11. The Linked List*
  12. A Lisp-like list
  13. The Binary Tree
  14. Bit manipulation*
  15. Active Logic, Truthy and Falsey *
  16. 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, FacebookGoogle+ or Linkedin.

 
 

 

blog comments powered by Disqus

Banner


JavaScript Async - The Fetch API

There are a number of new features in JavaScript that make good use of promises and hence async and await. The Fetch API is a replacement for the XMLHttpRequest function and perhaps the jQuery Ajax fu [ ... ]



Getting Started with Node.js

By bringing JavaScript to the server, Node.js is something of a buzz in the wider JavaScript world. Here we look at the problem it solves and how to make good use of it.


Other Articles

datastruct

 

<ASIN:0470525932>

<ASIN:0596806752>

<ASIN:0321683919>

<ASIN:059680279X>

 

 



Last Updated ( Thursday, 27 July 2017 )
 
 

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