Singly linked list abstraction in ES5 JavaScript

Question

Below is the code for, Singly linked list implementation,

function List(){
 this.start=null; 
 this.end=null;
}
List.makeNode=function(){ 
 return {data:null,next:null};
};
List.prototype.add=function (data){
 if(this.start===null){ 
 this.start=List.makeNode(); 
 this.end=this.start;
 }else{
 this.end.next=List.makeNode(); 
 this.end=this.end.next; 
 }
 this.end.data=data; 
};
List.prototype.traverse = function(){
 var current = this.start;
 while (current !== null) {
 current = current.next; 
 }
};
List.prototype.insertAsFirst = function(d) {
 var temp = List.makeNode();
 temp.next = this.start; 
 this.start = temp; 
 temp.data = d; 
};
List.prototype.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; 
 } 
};
List.prototype.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;
 }
};
List.prototype.item=function(i){ 
 var current = this.start; 
 while (current !== null) {
 i--; 
 if(i===0) return current; 
 current = current.next; 
 } 
 return null;
};
List.prototype.each = function(f) {
 var current = this.start; 
 while (current !== null) { 
 f(current); 
 current = current.next;
 }
};

From the above code,

1) Is List a proper abstraction?

2) Does List ensure encapsulation?

3) Is the usage of List.prototype justified?

4) Does makeNode justified as static function?

• Madara's Ghost: You do realized the JS arrays are (normally) implemented as Linked Lists under the hood, right?
• overexchange: @MadaraUchiha JS array implemented as linked list will degrade insert operation performance. Any reference on this info?
• Joseph: @overexchange I'd worry more about getting things done over some micro-optimization.
• JonathanR: @MadaraUchiha this is incorrect. See quora.com/How-are-javascript-arrays-implemented-internally Javascript arrays are more like C++ vector or Java ArrayList when they are dense. When they are sparse they're essentially hashmaps, they're still not linked lists, ie performance will always be better than O(n) for retrieval.

Answer 1

You don't need to track the end of the list. You can just check that you've reached it if an element's next is null.

makeNode doesn't do anything. Every time you use it you set data instantly after, so data should be a parameter. Setting next to null isn't that useful because if you don't change it you can simply check node.next === undefined and get the same thing, while using less memory.

Try

function MakeNode(data) {
 return { data: data };
}

In general it's not that useful to separate the node and list abstractions. If you want a list just pass around the first node of the list. It makes many algorithms much simpler to read and write.

I'd start with

function Node(data, next) {
 this.data = data;
 this.next = next;
}

This sets next to undefined if you just do new Node(5).

Answer 2

Everything JonathanR says is true, but also

• The traverse function does nothing useful
• You are finding an element based on data in 3 different places, that should be a separate function
• insertAtFirst -> should really be unshift to be familiar
• add should be push
• each probably should be forEach

As I went thru the code I maintained a version that I would write, and I realized I was missing a ton of test cases ( I think you are as well ), such as deleting the first node if there is only 1 node. In that case you need to set this.end to null. You need a lot of test cases! That is why I was hesitant to show my version, since I just know some use cases are missing. But if you check it out, it might give you ideas on how to approach this differently.

 function List(){
 this.start=null; 
 this.end=null;
 }
 function List.makeNode = function makeNode(data, next) {
 return {data:data,next:next};
 }
 List.prototype.push = function add(data){
 var node = List.makeNode(data);
 if(!this.start){ 
 this.start=node;
 }else{
 this.end.next=node; 
 }
 this.end = node; 
 };
 List.prototype.unshift = function unshift(data) {
 this.start = List.makeNode( data , this.start );
 };
 List.prototype.get = function get(data){
 var current = this.start; 
 while( current ){
 if( current.data === data ){
 return data;
 }else{
 current = current.next;
 }
 }
 }
 List.prototype.getPrior = function getPrior(data){
 var current = this.start,
 previous;
 while( current ){
 if( current.data === data ){
 return previous;
 }else{
 previous = current;
 current = current.next;
 }
 }
 }
 List.prototype.remove = function remove(data) {
 var previous = this.getPrior(data);
 if(!previous){
 this.start = this.start.next;
 } else if( this.end.data == data ){
 this.end = previous;
 previous.next = null;
 } else {
 previous.next = previous.next.next;
 }
 };
 List.prototype.insertAfter = function insertAfter(target, data) { 
 var target = this.get(target); 
 if( target == this.end ){
 this.end = this.end.next = List.makeNode(data)
 }else{
 target.next = List.makeNode( data , target.next ); 
 }
 };
 List.prototype.item = function item(i){ 
 var current = this.start; 
 while (current !== null) {
 if(!--i) return current; 
 current = current.next; 
 } 
 };
 List.prototype.forEach = function forEach(f) {
 var current = this.start; 
 while (current) { 
 f(current); 
 current = current.next;
 }
 };

• Is it a proper abstraction is an interesting question, I would say no. It seems more distinct rather than abstract ;)
• Did you encapsulate? No, all the data can be gotten without using any of the provided functions
• List.prototype justified -> Absolutely
• makeNode as a static function, meh. Honestly if you think about it, the result of List and makeNode are very very similar, I would (ab)use that.