Doubly Linked List

Question

I coded up a basic DLL for use in a stack or a queue in JavaScript for practice. Coming from a C++/Java background, I basically just converted how I would code it up in one of those. I'm not sure if there's a more JavaScript optimized way of doing it.

function Node(val) {
    this.data = val;
    this.prev = null;
    this.next = null;
}

function LinkedList() {
    this.head = null;
    this.tail = null;

    this.addAtFront = function (val) {
        if (this.head === null) {  //If first node
            this.head = new Node(val);
            this.tail = this.head;
        } else {
            var temp = new Node(val);
            temp.next = this.head;
            this.head.prev = temp;
            this.head = temp;
        }
    };

    this.addAtEnd = function (val) {
        if (this.tail === null) {  //If first node
            this.tail = new Node(val);
            this.head = this.tail;
        } else {
            var temp = new Node(val);
            temp.prev = this.tail;
            this.tail.next = temp;
            this.tail = temp;
        }
    };

    this.removeAtHead = function () {
        var toReturn = null;

        if (this.head !== null) {
            toReturn = this.head.data;

            if (this.tail === this.head) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
                this.head.prev = null;
            }
        }
        return toReturn;
    };

    this.removeAtTail = function () {
        var toReturn = null;

        if (this.tail !== null) {
            toReturn = this.tail.data;

            if (this.tail === this.head) {
                this.head = null;
                this.tail = null;
            } else {
                this.tail = this.tail.prev;
                this.tail.next = null;
            }
        }

        return toReturn;
    };

    this.each = function (f) {
        var curr = this.head;
        while (curr !== null) {
            f(curr);
            curr = curr.next;
        }
    };

    this.printList = function () {
        this.each(function (item) {
            console.log(item.data);
        });
    };
}



var testList = new LinkedList();

var runTests = function () {
    testList.addAtFront("Second");
    testList.addAtFront("First");
    testList.addAtEnd("Third");
    testList.addAtEnd("Fourth");

    testList.printList();

    testList.removeAtHead();
    testList.removeAtTail();

    testList.printList();

    testList.removeAtHead();
    testList.removeAtHead();

    testList.printList();

};

If you're doing it as an exercise, there are certainly ways to reduce code size and make it more "JavaScripty". However, if you're doing a linked list to optimize algorithms that generally don't work too well on arrays (which is all you got in JS), you'll probably be disappointed. — Touffy
– Touffy, Commented Mar 7, 2015 at 20:02

Community · Accepted Answer · 2017-05-23 11:33:42Z

Overall, your code looks very nice. I just have a few, very small things to point out.

The value null is called a falsey value. This means that null can be treated as though it were false.

That being said, conditionals like this:

this.head === null

and this

this.tail !== null

can be shortened to this:

!this.head

and this

this.tail

respectively.

If you don't understand why, or want to experiment around a bit more, just open up your web browser's developer console and enter this:

var foo = null;
if(foo) { alert("bar"); }

You will not get a notification saying "bar". However, if you write

if(!foo) { ... }

You will get a notification saying "bar".

I think it is a bad idea to, in the function printList, to log out to the browser's console.

Different browsers have different implementations of console, which is why console.log is mainly used for debugging.
What if the user does not want to log to the console?

I think that, instead of logging out to the console, you should return a string of all the nodes' values. That way, the person who is using this code that you wrote can decide how they want to handle output of these values.

That would make your method look something like this:

this.printList = function() {
    var dataString = "";
    this.each(function(item) {
        dataString += item.data + "\n";
    });
    return dataString;
}

In this case, you may want to change the name from printList.

You should be setting the methods of LinkedList through the prototype, not through the "constructor" of the class.

What I mean is, you should be doing this:

function LinkedList() {
    this.head = null;
    this.tail = null;
}

LinkedList.prototype.addAtFront = function(val) {
    ...
}

...

rather than this:

function LinkedList() {
    this.head = null;
    this.tail = null;

    this.addAtFront = function(val) {
        ...
    }
    ...
}

Read here and here for why.

This is just a tip to extend on your implementation.

I recommend that you add some optional parameters to the LinkedList class constructor: someone using this may already have a some Nodes that they'd like to use in a new LinkedList.

Here is how I would change the constructor:

function LinkedList(head, tail) {
    this.head = ( head ? head : null );
    this.tail = ( tail ? tail : null );

    ....
}

The same goes to your Node constructor; maybe the user already has a next and a prev.

Your code is very clean and very neat. I think it was an incredible ease to follow along with

Stack Exchange Network

Doubly Linked List

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Doubly Linked List

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions