I've been studying data structures and have taken a stab at implementing a doubly LL in JavaScript. Please review and advise on any additional improvements and optimizations. I'm more interested in feedback particularly regarding the implementations of removeAt(), contains() and getItem() methods as they share similar, repetitive code:
//Blueprints
function Node(val){
this.data = val;
this.next = null;
this.prev = null;
}
function DoublyList(){
this._length = 0;
this._isCircular = false;
this.head = null;
this.tail = null;
}
//Adds to the list
DoublyList.prototype.add = function(val){
var node = new Node(val);
if(this._length){
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}else{
this.head = node;
this.tail = node;
}
this._length++;
return node;
}
//Check if list is empty
DoublyList.prototype.isEmpty = function(){
return this._length===0;
}
//Contains method returns index if true
DoublyList.prototype.contains = function(val){
if(this.isEmpty()){
return 'List is Empty';
}
var currentNode = this.head, i=0;
//if val is in 1st node
if(currentNode.data === val){
return 0;
}
//if val is in last node
if(this.tail.data === val){
return (this._length-1);
}
//if val is in middle
while(i++ < (this._length-1)){
if(currentNode.data === val){
return (i-1);
}
currentNode = currentNode.next;
}
return false;
}
//Make circular
DoublyList.prototype.makeCircular = function(){
if(!this.isEmpty()){
this.head.prev = this.tail;
this.tail.next = this.head;
this._isCircular = true;
}
}
//get data by node index
DoublyList.prototype.getItem = function(index){
if(this.isEmpty()){
return 'List is Empty';
}
if(index<0 || index > this._length){
return 'Invalid Index!';
}
var currentNode = this.head, i=0;
//if first item in list
if(index===0){
return currentNode.data;
}
//if last item in list
if(index === (this._length-1)){
return this.tail.data;
}
//if item is in middle of list
while(i++ < index){
currentNode = currentNode.next;
}
return currentNode.data;
}
DoublyList.prototype.removeAt = function(index){
if(this.isEmpty()){
return 'List is Empty';
}
if(index<0 || index > this._length){
return 'Invalid Index!';
}
var currentNode = this.head, i=0;
//if first item in list: O(1)
if(index===0){
this.head = currentNode.next;
this.head.prev = this.tail;
this.tail.next = this.head;
this._length--;
return this;
}
//if last item in list: O(1)
if(index === (this._length-1)){
this.tail = this.tail.prev;
this.tail.next = this.head;
this.head.prev = this.tail;
this._length--;
return this;
}
//if item is in middle of list: O(n)
while(i++ < index){
currentNode = currentNode.next;
}
var temp = currentNode;
temp.prev.next = currentNode.next;
this._length--;
return this;
}
var doublyList = new DoublyList();
console.log('isEmpty:\n'+doublyList.isEmpty());
doublyList.add(5);
doublyList.add(10);
doublyList.add(15);
doublyList.add(20);
doublyList.add(25);
doublyList.add(30);
doublyList.add(35);
doublyList.add(40);
console.log('Added items...\n');
console.log('Original List:\n'+doublyList);
console.log('makeCircular:\n'+doublyList.makeCircular());
console.log('Circular List:\n'+doublyList);
console.log('Get 3rd item:\n'+doublyList.getItem(2));
console.log('Contains:\n'+doublyList.contains(15));
console.log('RemoveAt:\n'+doublyList.removeAt(2));
