The Ashes

Technology, Science and other news
April 17, 2009

Giving you that CompSci 101 feeling with JavaScript

Posted by : admin
Filed under : General

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:

PLAIN TEXT
JAVASCRIPT:

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

No Comments

(required)
(will not be published) (required)
(opitional)

cciash.com EN ES IT DE PT CZ FR RU
September 2018
M T W T F S S
« Sep    
 12
3456789
10111213141516
17181920212223
24252627282930

Pages

Categories

Resources

There are many online poker site where you can play but at poker.hk you can play the poker games with all the knowledge you need related to the game with the poker school available in both the English and Chinese language.

Super Casino

Now you can bet on any sports and any sporting events from all the comfort from your home. Bet770 allows you to bet on any events and match with in just 3 clicks. They also offers great odds on football betting for every premier and champions league match. Get £50 free in bets when you register.

Bingo770, offering best online bingo games with £7.70 free no deposit Bonus!