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.


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 = List.makeNode();
   this.end =;
  } ; = data;

 this.delete = function(data) {
  var current = this.start;
  var previous = this.start;
  while (current !== null) {
   if (data === {
    if (current === this.start) {
     this.start =;
    if (current === this.end)
                      this.end = previous; =; return;
    previous = current;
    current =;

 this.insertAsFirst = function(d) {
  var temp = List.makeNode(); = this.start;
  this.start = temp; = d;

 this.insertAfter = function(t, d) {
  var current = this.start;
  while (current !== null) {
   if ( === t) {
    var temp = List.makeNode(); = d; =;
    if (current === this.end) this.end = temp; = temp;
   current =;

  this.item = function(i) {
   var current = this.start;
   while (current !== null) {
    if (i === 0) return current;
    current =;
   return null;

 this.each = function(f) {
  var current = this.start;
  while (current !== null) {
   current =;


If you would like the code for this project then register and click on CodeBin.

Further Reading

JavaScript Books (2012)


JavaScript Data Structures 



  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.





or email your comment to:


Just JavaScript - The Object Expression

As in most programming languages, the expression is an important part of JavaScript, but it isn't quite the same. This is where the idea that JavaScript has some weird type conversions arises. But in  [ ... ]

Just JavaScript - The Function Object

The function object is the most important object in all of JavaScript and yet we tend to forget that it is an object. Understanding that JavaScript functions are objects is probably the most important [ ... ]

Other Articles









Last Updated ( Thursday, 27 July 2017 )

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