Thursday, April 16th, 2009

Giving you that CompSci 101 feeling with JavaScript

Category: JavaScript

<>p>Nicholas Zakas is taking a break from performance posts as he starts a computer science in JavaScript repository.

First up in the “remember that data structures weeder Comp Sci class?” moment is the linked list:

It consists of a sequence of nodes, each containing arbitrary data fields and one or two references (”links”) pointing to the next and/or previous nodes. The principal benefit of a linked list over a conventional array is that the order of the linked items may be different from the order that the data items are stored in memory or on disk, allowing the list of items to be traversed in a different order. A linked list is a self-referential datatype because it contains a pointer or link to another datum of the same type. Linked lists permit insertion and removal of nodes at any point in the list in constant time, but do not allow random access.

The academic exercise for Nicholas ended with:

javascript
< view plain text >
  1. /*
  2. * Linked List implementation in JavaScript
  3. * Copyright (c) 2009 Nicholas C. Zakas
  4. * See LICENSE for details on license.
  5. */
  6.  
  7. /**
  8. * A linked list implementation in JavaScript.
  9. * @class LinkedList
  10. * @constructor
  11. */
  12. function LinkedList() {
  13.  
  14.     /**
  15. * The number of items in the list.
  16. * @property _length
  17. * @type int
  18. * @private
  19. */
  20.     this._length = 0;
  21.    
  22.     /**
  23. * Pointer to first item in the list.
  24. * @property _list
  25. * @type Object
  26. * @private
  27. */
  28.     this._head = null;
  29. }
  30.  
  31. LinkedList.prototype = {
  32.  
  33.     //restore constructor
  34.     constructor: LinkedList,
  35.    
  36.     /**
  37. * Appends some data to the end of the list. This method traverses
  38. * the existing list and places the value at the end in a new item.
  39. * @param {variant} data The data to add to the list.
  40. * @return {Void}
  41. * @method add
  42. */
  43.     add: function (data){
  44.    
  45.         //create a new item object, place data in
  46.         var node = {
  47.                 data: data,
  48.                 next: null
  49.             },
  50.            
  51.             //used to traverse the structure
  52.             current;
  53.    
  54.         //special case: no items in the list yet
  55.         if (this._head === null){
  56.             this._head = node;
  57.         } else {
  58.             current = this._head;
  59.            
  60.             while(current.next){
  61.                 current = current.next;
  62.             }
  63.            
  64.             current.next = node;
  65.         }
  66.        
  67.         //don't forget to update the count
  68.         this._length++;
  69.    
  70.     },
  71.    
  72.     /**
  73. * Retrieves the data in the given position in the list.
  74. * @param {int} index The zero-based index of the item whose value
  75. * should be returned.
  76. * @return {variant} The value in the "data" portion of the given item
  77. * or null if the item doesn't exist.
  78. * @method item
  79. */
  80.     item: function(index){
  81.    
  82.         //check for out-of-bounds values
  83.         if (index > -1 && index < this._length){
  84.             var current = this._head,
  85.                 i = 0;
  86.                
  87.             while(i++ < index){
  88.                 current = current.next;
  89.             }
  90.        
  91.             return current.data;
  92.         } else {
  93.             return null;
  94.         }
  95.     },
  96.    
  97.     /**
  98. * Removes the item from the given location in the list.
  99. * @param {int} index The zero-based index of the item to remove.
  100. * @return {variant} The data in the given position in the list or null if
  101. * the item doesn't exist.
  102. * @method remove
  103. */
  104.     remove: function(index){
  105.    
  106.         //check for out-of-bounds values
  107.         if (index > -1 && index < this._length){
  108.        
  109.             var current = this._head,
  110.                 previous,
  111.                 i = 0;
  112.                
  113.             //special case: removing first item
  114.             if (index === 0){
  115.                 this._head = current.next;
  116.             } else {
  117.        
  118.                 //find the right location
  119.                 while(i++ < index){
  120.                     previous = current;
  121.                     current = current.next;
  122.                 }
  123.            
  124.                 //skip over the item to remove
  125.                 previous.next = current.next;
  126.             }
  127.        
  128.             //decrement the length
  129.             this._length--;
  130.        
  131.             //return the value
  132.             return current.data;
  133.        
  134.         } else {
  135.             return null;
  136.         }
  137.    
  138.     },
  139.    
  140.     /**
  141. * Returns the number of items in the list.
  142. * @return {int} The number of items in the list.
  143. * @method size
  144. */
  145.     size: function(){
  146.         return this._length;
  147.     },
  148.    
  149.     /**
  150. * Converts the list into an array.
  151. * @return {Array} An array containing all of the data in the list.
  152. * @method toArray
  153. */
  154.     toArray: function(){
  155.         var result = [],
  156.             current = this._head;
  157.        
  158.         while(current){
  159.             result.push(current.data);
  160.             current = current.next;
  161.         }
  162.        
  163.         return result;
  164.     },
  165.    
  166.     /**
  167. * Converts the list into a string representation.
  168. * @return {String} A string representation of the list.
  169. * @method toString
  170. */
  171.     toString: function(){
  172.         return this.toArray().toString();
  173.     }
  174. };

Related Content:

Posted by Dion Almaer at 6:33 am
11 Comments

++---
2.1 rating from 28 votes

11 Comments »

Comments feed TrackBack URI

linked lists have no significance in javascript

Comment by robertlovescss — April 16, 2009

@robertlovescss: that kind of thinking won’t take you far :P

Comment by andysky — April 16, 2009

This speaks a little badly for the JavaScript community that this is news, since this is a little… obvious. You’d hope anyone who has used JavaScript for more than a few hours could reproduce this from scratch with little trouble.

I’d also not recommend doing this for any reason other than an educational exercise. In the real world, it’s a bad idea to try and fight against a language that revolves around high-level constructs, and it’ll likely be no better in terms of speed or memory usage than embracing the obvious Array.prototype.push and Array.prototype.pop solution instead.

That said, perhaps it’ll become a useful resource if the author goes onto more complex data structures.

Comment by Halo — April 16, 2009

I myself wrote a such class ages ago simply because I needed it, and it didn’t take me more than two hours (and I wasn’t very adapt at JavaScript at the time). Whenever I was wondering if I did something wrong, a quick google would give me several websites talking about making a linked list in JavaScript, full of examples, and comments talking about various aspects of the implementation.

So, I agree with Halo. This can’t really be called news even by a stretch of imagination.

It doesn’t help that this linked list isn’t even Doubly-circular.

Comment by Drakim — April 16, 2009

“This speaks a little badly for the JavaScript community that this is news, since this is a little… obvious. You’d hope anyone who has used JavaScript for more than a few hours could reproduce this from scratch with little trouble.”

You are assuming that the JavaScript is being written by people with a formal CS background. This is sometimes true, but IMO, JavaScript is mostly being written by people whose job is to do something else – be that backend folks or frontend folks.

For the most part, frontend folks aren’t going to have a clue what a linked list is to begin with.

Comment by cancelbubble — April 16, 2009

I just got done writing a BST implementation in JavaScript, partly to see what it was like to code up something like that, partly because maybe it will come in handy someday to have a set implementation that can be iterated in order. Plus with JavaScript’s functional capabilities you can do some cool stuff, like passing a key function to the constructor, which for example lets you order a tree of strings in a case-insensitive manner. So while a linked list implementation may not be that useful, it might be nice to see this type of stuff more common in JS. Priority queues, anyone?

Comment by greim — April 16, 2009

It’s a shame JS doesn’t support linked lists natively, because it’s an immensely useful data structure.

They can be emulated by arrays, though.

Comment by chiaroscuro — April 16, 2009

can this type of data structure be more efficient in terms of performance?

Comment by befa44 — April 17, 2009

2 befa44

> can this type of data structure be more efficient in terms of performance?

Linked lists or the nonsense you see in this post? :)

Comment by chiaroscuro — April 17, 2009

It is really getting hard for me to answer the question “What is Ajaxian about?”

Comment by trav1m — April 17, 2009

This is a good intro to complex data structures (which he is writing, double linked lists is written already). Now this will all come together as soon as he writes anything with any unique sorting, speed or storage benefit like any of the number of tree’s.

Comment by thenightwassaved — May 10, 2009

Leave a comment

You must be logged in to post a comment.