current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote -1 down vote favorite

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?

share|improve this question
3  
You do realized the JS arrays are (normally) implemented as Linked Lists under the hood, right? – Madara Uchiha 2 days ago
1  
@MadaraUchiha JS array implemented as linked list will degrade insert operation performance. Any reference on this info? – overexchange 2 days ago
1  
@overexchange I'd worry more about getting things done over some micro-optimization. – Joseph the Dreamer 2 days ago
    
@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. – JonathanR 2 days ago
up vote 0 down vote

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.