List data structure in javascript

Posted on | by Prashant Yadav

Posted in

List data structure is a ADT with a collection of data in which items does not needs to be searched, added or removed in any sorted order.

Just like a TO-DO list, a Grocery list, a Top-Ten list etc.

List Data Structure

Computers can utilize this list data structure for common problems. For more complex problems we will need some other advance data structures like Stack, Queue, Linked List and more.

Definition of List ADT

A list is an ordered sequence of data. Each data stored in the list is called an item and item can be of any data type.

Items can be added to the beginning of the list or after any existing item in the list, we can remove the items from the list. We can also clear the whole list and reset it.

You can also check the size of the list, A list with no items will be a empty list.

The items of the list can be displayed together or we can display the single item at the current position.

We can move at different position in the list, to front, to last, to next, to prev or to any given position. We can also check the current position in the list and use this to print the item at that position.

We will create a list that will support the Strings, Numbers, Boolean, null, Object & Arrays.

List of operation performed by list ADT

  • size (method): Returns the size of the list.
  • clear (method): Clears the list.
  • print (method): Prints all the items of the list.
  • getElement (method): Returns the item at the current position in the list.
  • insert (method): Inserts a new item after the given item in the list.
  • append (method): Adds a new item on the top of the list.
  • remove (method): Removes the given item from the list.
  • front (method): Moves the position to the first item in the list.
  • rear (method): Moves the position to the last item in the list.
  • prev (method): Moves the position to the previous item in the list.
  • next (method): Moves the position to the next item in the list.
  • currPos (method): Returns the current position in the list.
  • moveTo (method): Moves to the specific position in the list.
  • contains (method): Check if item is present in the list.

Implementing list data structure in Javascript

We will implement list data structure with different methods. Everything will be written in ESNext.

  • A classical approach using function and then making properties and methods private with closure.
  • By using ES6 class and again making the properties and methods private with closure.

A classical approach

 function List(){
   //Initialize the list
   this.listSize = 0;  //track size of the list
   this.pos = 0;       //track current position in the list
   this.items = [];    //hold items

   //other methods goes here
 }

Adding item to the list

   //Add item to the list
   this.append = (element) => {
    this.items[this.listSize++] = element;
   }

Finding item in the list

  //Find item from the list
  //this won't work for objects and arrays
  this.find = (element) => {
    for(let i = 0; i < this.listSize; i++){
      if(this.items[i] === element){
        return i;
      }
    }
    
    return -1;
  }

Removing item from the list

  //Remove item from the list
  this.remove = (element) => {
    let index = this.find(element);
    
    if(index > -1){
      this.items.splice(index, 1);
      --this.listSize;
      return true;
    }
    
    return false;
  }

Insert item after the given item in the list

  //Insert items at specific position in the list
  this.insert = (element, after) => {
    let insertPos = this.find(after);
    
    if(insertPos > -1){
       this.items.splice(insertPos+1, 0, element);  
       ++this.listSize;
      return true;
    }
    
    return false;
  }

Check if item is present in the list

  //Check if item is present in the list
  this.contains = (element) => {
    let index = this.find(element);
    return index > -1 ? true : false;
  }

Move to the first item in the list

  //Move to the front of the list
  this.front = () => {
    this.pos = 0;
  }

Move to the last item in the list

  //Move to the end of the list
  this.rear = () => {
    this.pos = this.listSize - 1;
  }

Move to the previous item in the list

  //Move to the prev item in the list
  this.prev = () => {
    if(this.pos > 0){
      --this.pos;
    }
  }

Move to the next item in the list

  //Move to the next item in the list
  this.next = () => {
    if(this.pos < this.listSize - 1){
      ++this.pos;
    }
  }

Move to the specific item in the list

  //Move to the specific position in the list
  this.moveTo = (pos) => {
    if(pos > 0 && pos <= this.listSize){
      this.pos = pos - 1;
    }
  }

Get the current position in the list

  //Get the current position in the list
  this.currPos = () => {
    return this.pos;
  }

Get the current item in the list

  //Get current item from the list
  this.getElement = () => {
    return this.items[this.pos];
  }

Get the size of the list

  //Get the size list
  this.size = () => {
    return this.listSize;
  }

Print all the items of the list

  //Print the items of the list
  this.print = () => {
    return this.items.join(',');
  }

Clear the list

  //Clear the list
  this.clear = () => {
    this.listSize = 0;
    this.pos = 0;
    this.items = [];
  }

Complete implementation of list data structure

function List(){
  //Initialize the list
  this.listSize = 0;
  this.pos = 0;
  this.items = [];
     
  //Add item to the list
  this.append = (element) => {
    this.items[this.listSize++] = element;
  }
     
  //Find item from the list
  this.find = (element) => {
    for(let i = 0; i < this.listSize; i++){
      if(this.items[i] === element){
        return i;
      }
    }
    
    return -1;
  }

  //Remove item from the list
  this.remove = (element) => {
    let index = this.find(element);
    
    if(index > -1){
      this.items.splice(index, 1);
      --this.listSize;
      return true;
    }
    
    return false;
  }
     
  //Insert items at specific position in the list
  this.insert = (element, after) => {
    let insertPos = this.find(after);
    
    if(insertPos > -1){
       this.items.splice(insertPos+1, 0, element);  
       ++this.listSize;
      return true;
    }
    
    return false;
  }
      
  //Check if item is present in the list
  this.contains = (element) => {
    let index = this.find(element);
    return index > -1 ? true : false;
  }
      
  //Move to the front of the list
  this.front = () => {
    this.pos = 0;
  }
     
  //Move to the end of the list
  this.rear = () => {
    this.pos = this.listSize - 1;
  }
     
  //Move to the prev item in the list
  this.prev = () => {
    if(this.pos > 0){
      --this.pos;
    }
  }

  //Move to the next item in the list
  this.next = () => {
    if(this.pos < this.listSize - 1){
      ++this.pos;
    }
  }
      
  //Get the current position in the list
  this.currPos = () => {
    return this.pos;
  }
     
  //Move to the specific position in the list
  this.moveTo = (pos) => {
    if(pos > 0 && pos <= this.listSize){
      this.pos = pos - 1;
    }
  } 
     
  //Get current item from the list
  this.getElement = () => {
    return this.items[this.pos];
  }

  //Get the size list
  this.size = () => {
    return this.listSize;
  }
     
  //Print the items of the list
  this.print = () => {
    return this.items.join(',');
  }

  //Clear the list
  this.clear = () => {
    this.listSize = 0;
    this.pos = 0;
    this.items = [];
  }
}

Input:
let list = new List();
list.append('Prashant');
list.append('Taha');
list.append('Anil');

list.insert('Yogesh', 'Taha');
console.log(list.print()); //print all the items of the string.
console.log(list.getElement());

list.next();  //move to next item
console.log(list.getElement());

list.rear(); //move to last item
console.log(list.getElement());

list.prev(); //move to prev item
console.log(list.getElement());

console.log(list.size());  //get the size of the list

list.remove('Taha');
console.log(list.size());  //get the size of the list
console.log(list.print()); //print all the items of the string.

Output:
//"Prashant,Taha,Yogesh,Anil"
//"Prashant"
//"Taha"
//"Anil"
//"Yogesh"
//4
//3
//"Prashant,Yogesh,Anil"

In order to make the list work with Objects and Arrays data. We will need to update the find method to compare two different objects and arrays.

  //Find item from the list
  this.find = (element) => {
    if(typeof element === 'object' && element !== null){
      for(let i = 0; i < this.listSize; i++){
        if(Object.entries(this.items[i]).toString() === Object.entries(element).toString()){
          return i;
        }
      }
    }else{
      for(let i = 0; i < this.listSize; i++){
        if(this.items[i] === element){
          return i;
        }
      }
    }
    return -1;
  }

Also print method won't work properly because the object will be printed as '[object object]'

Input:
let list = new List();
list.append('Prashant');
list.append('Taha');
list.append({a: 1, b: 2});
list.insert([1, 2, 3, 4], 'Taha');
console.log(list.print()); //print all the items of the string.
console.log(list.getElement());

list.next();  //move to next item
console.log(list.getElement());

list.rear(); //move to last item
console.log(list.getElement());

list.prev(); //move to prev item
console.log(list.getElement());

console.log(list.size());  //get the size of the list

list.remove('Taha');
list.remove({a: 1, b: 2});
console.log(list.size());  //get the size of the list
console.log(list.print()); //print all the items of the string.

Output:
//"Prashant,Taha,1,2,3,4,[object Object]"
//"Prashant"
//"Taha"
//Object {
//  a: 1,
//  b: 2
//}
//[1, 2, 3, 4]
//4
//2
//"Prashant,1,2,3,4"

Making methods and properties private with IIFE and closure.

let List = (function(){
  return function List(){
    //Initialize the list
    this.listSize = 0;
    this.pos = 0;
    this.items = [];

    //Add item to the list
    this.append = (element) => {
      this.items[this.listSize++] = element;
    }

    //Find item from the list
    this.find = (element) => {
      for(let i = 0; i < this.listSize; i++){
        if(this.items[i] === element){
          return i;
        }
      }

      return -1;
    }

    //Remove item from the list
    this.remove = (element) => {
      let index = this.find(element);

      if(index > -1){
        this.items.splice(index, 1);
        --this.listSize;
        return true;
      }

      return false;
    }

    //Insert items at specific position in the list
    this.insert = (element, after) => {
      let insertPos = this.find(after);

      if(insertPos > -1){
         this.items.splice(insertPos+1, 0, element);  
         ++this.listSize;
        return true;
      }

      return false;
    }

    //Check if item is present in the list
    this.contains = (element) => {
      let index = this.find(element);
      return index > -1 ? true : false;
    }

    //Move to the front of the list
    this.front = () => {
      this.pos = 0;
    }

    //Move to the end of the list
    this.rear = () => {
      this.pos = this.listSize - 1;
    }

    //Move to the prev item in the list
    this.prev = () => {
      if(this.pos > 0){
        --this.pos;
      }
    }

    //Move to the next item in the list
    this.next = () => {
      if(this.pos < this.listSize - 1){
        ++this.pos;
      }
    }

    //Get the current position in the list
    this.currPos = () => {
      return this.pos;
    }

    //Move to the specific position in the list
    this.moveTo = (pos) => {
      if(pos > 0 && pos <= this.listSize){
        this.pos = pos - 1;
      }
    } 

    //Get current item from the list
    this.getElement = () => {
      return this.items[this.pos];
    }

    //Get the size list
    this.size = () => {
      return this.listSize;
    }

    //Print the items of the list
    this.print = () => {
      return this.items.join(',');
    }

    //Clear the list
    this.clear = () => {
      this.listSize = 0;
      this.pos = 0;
      this.items = [];
    }
  }
}());

List implemented with ES6 Class

class List {
  //Initialize the list
  constructor(){
    this.listSize = 0;
    this.pos = 0;
    this.items = [];
  }
    
  //Add item to list
  append = (element) => {
    this.items[this.listSize++] = element;
  }
  
  //Find item in the list
  find = (element) => {
    if(typeof element === 'object' && element !== null){
      for(let i = 0; i < this.listSize; i++){
        if(Object.entries(this.items[i]).toString() === Object.entries(element).toString()){
          return i;
        }
      }
    }else{
      for(let i = 0; i < this.listSize; i++){
        if(this.items[i] === element){
          return i;
        }
      }
    }
    return -1;
  }
  
  //Remove item from the list
  remove = (element) => {
    let index = this.find(element);
    
    if(index > -1){
      this.items.splice(index, 1);
      --this.listSize;
      return true;
    }
    
    return false;
  }
   
  //Insert item at specific position in the list
  insert = (element, after) => {
    let insertPos = this.find(after);
    
    if(insertPos > -1){
       this.items.splice(insertPos+1, 0, element);  
       ++this.listSize;
      return true;
    }
    
    return false;
  }
  
  //Check if items is there in list
  contains = (element) => {
    let index = this.find(element);
    return index > -1 ? true : false;
  }
  
  //Move to the front of the list
  front = () => {
    this.pos = 0;
  }
  
  //Move to the end of the list
  rear = () => {
    this.pos = this.listSize - 1;
  }
  
  //Move to the prev item in the list
  prev = () => {
    if(this.pos > 0){
      --this.pos;
    }
  }
  
  //Move to the next item in the list
  next = () => {
    if(this.pos < this.listSize - 1){
      ++this.pos;
    }
  }
  
  //Return the currentPos in the list
  currPos = () => {
    return this.pos;
  }
  
  //Move to any particular position in the list
  moveTo = (pos) => {
    if(pos > 0 && pos <= this.listSize){
      this.pos = pos - 1;
    }
  } 
  
  //Get the current element in the list
  getElement = () => {
    return this.items[this.pos];
  }
  
  //Size of the list
  size = () => {
    return this.listSize;
  }
  
  //Print the list
  print = () => {
    return this.items.join(',');
  }
  
  //Clear the list
  clear = () => {
    this.listSize = 0;
    this.pos = 0;
    this.items = [];
  }
}

We can also wrap this inside a closure to make all the properties and methods private.

let List = (function(){
  return class List {
    //Initialize the list
    constructor(){
      this.listSize = 0;
      this.pos = 0;
      this.items = [];
    }

    //Add item to list
    append = (element) => {
      this.items[this.listSize++] = element;
    }

    //Find item in the list
    find = (element) => {
      if(typeof element === 'object' && element !== null){
        for(let i = 0; i < this.listSize; i++){
          if(Object.entries(this.items[i]).toString() === Object.entries(element).toString()){
            return i;
          }
        }
      }else{
        for(let i = 0; i < this.listSize; i++){
          if(this.items[i] === element){
            return i;
          }
        }
      }
      return -1;
    }

    //Remove item from the list
    remove = (element) => {
      let index = this.find(element);

      if(index > -1){
        this.items.splice(index, 1);
        --this.listSize;
        return true;
      }

      return false;
    }

    //Insert item at specific position in the list
    insert = (element, after) => {
      let insertPos = this.find(after);

      if(insertPos > -1){
         this.items.splice(insertPos+1, 0, element);  
         ++this.listSize;
        return true;
      }

      return false;
    }

    //Check if items is there in list
    contains = (element) => {
      let index = this.find(element);
      return index > -1 ? true : false;
    }

    //Move to the front of the list
    front = () => {
      this.pos = 0;
    }

    //Move to the end of the list
    rear = () => {
      this.pos = this.listSize - 1;
    }

    //Move to the prev item in the list
    prev = () => {
      if(this.pos > 0){
        --this.pos;
      }
    }

    //Move to the next item in the list
    next = () => {
      if(this.pos < this.listSize - 1){
        ++this.pos;
      }
    }

    //Return the currentPos in the list
    currPos = () => {
      return this.pos;
    }

    //Move to any particular position in the list
    moveTo = (pos) => {
      if(pos > 0 && pos <= this.listSize){
        this.pos = pos - 1;
      }
    } 

    //Get the current element in the list
    getElement = () => {
      return this.items[this.pos];
    }

    //Size of the list
    size = () => {
      return this.listSize;
    }

    //Print the list
    print = () => {
      return this.items.join(',');
    }

    //Clear the list
    clear = () => {
      this.listSize = 0;
      this.pos = 0;
      this.items = [];
    }
  }
}());

Introducing frontend system design course 🔥 where you will learn to design frontend of 30+ applications.