JavaScript Data Structures - The Linked List
Written by Ian Elliot   
Thursday, 05 September 2019
Article Index
JavaScript Data Structures - The Linked List
A List Object
More List Operations
When To Use A 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;
  }
 };
}
 

 

 

 

 

Further Reading

JavaScript Books (2012)

 


JavaScript Data Structures 

Cover

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.

espbook

 

Comments




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

Banner


JavaScript Canvas - Fetch API

Working with lower-level data is very much part of graphics. This extract from Ian Elliot's book on JavaScript Graphics looks at how to use typed arrays to access graphic data.



JavaScript Jems - The Inheritance Tax

JavaScript should not be judged as if it was a poor version of the other popular languages - it isn't a Java or a C++ clone. It does things its own way.  In particular, it doesn't do inheritance  [ ... ]


Other Articles

datastruct

 

<ASIN:1871962579>

<ASIN:1871962560>

<ASIN:1871962501>

<ASIN:1871962528>

 

 



Last Updated ( Thursday, 05 September 2019 )