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.
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 = []; } } }());