Javascript: Linked List: Unable to delete object reference

Question

I'm doing a Linked List data structure. The prototype includes a method to pop (delete) the last item from the list which I'm attempting to do by finding the last object, and then setting it to null. It does not seem to work. What does work is setting the reference (the 'pointer') in the previous object to null. I'm still a relative JS OOP newbie, can't get my brain to understand why. The code:

function LinkedList() {
    this._rootNode = null;
    this._length = 0;                                       
}

LinkedList.prototype = {

   push: function(data) {
       var newNode = {
           data: data,                                      
           nextNode: null
       };
       // initialize this._rootNode or subsequent .nextNode with newNode
       this._length++;
   },

   pop: function() {
       var selectedNode, perviousNode;

       if ( this._rootNode ) {
           if ( this._length > 1 ) {
               selectedNode = this._rootNode;
               while ( selectedNode.nextNode ) {
                   previousNode = selectedNode;  // <-- shouldn't need this?
                   selectedNode = selectedNode.nextNode;
               }
               selectedNode = null;              // <-- doesn't delete it
               // previousNode.nextNode = null;  // <-- works (but feels unnecessary?)
           } else {  
               this._rootNode = null;
           }
           this._length--;
       }
   },

   // more methods..
};


/* --- Main Prorgam --- */

var list = new LinkedList();

list.push('AAA');
list.push('BBB');
list.pop();
console.log(list._rootNode.nextNode.data);   <-- 'BBB' still there

Would appreciate some insight, and any other tips on improving the function. Thanks!

citizenslave · Accepted Answer · 2014-02-15 23:55:23Z

3

I guess you realize that your push method doesn't work, but you haven't asked about that one.

If you are doing some kind of school project that requires you to write a linked list like this, then by all means, continue. Your issue is that selectedNode is not really "the node itself", it's a reference to it, and you're just setting that reference to null while the previous item's nextNode pointer still refers to it, so you haven't actually removed it from your list. You would actually do so by un-commenting the line setting that pointer to null, which means you also have to leave in the line saving the reference to the previous node.

previousNode.nextNode = null;

You actually don't want to delete the node entirely with pop(), you want to return it. Once you remove the reference to the popped node in your calling function though, it will be the last reference and the object will be made available for garbage collection. This is (to my knowledge) how all traditional OOP languages handle linked lists at the basic level.

Which brings me to my next point, that most OOP languages you'll use these days don't actually require you to work on the basic level. Most of them have libraries that will implement linked lists for you and Javascript in particular essentially implements a linked list-style data structure in its array syntax. To the point where ([1,2,3,4]).pop() evaluates to 4 and ([1,2,3,4]).push(5) evaluates to [1,2,3,4,5]. If you actually need to USE a linked list in a real project, just don't.

edited Feb 15, 2014 at 23:55

answered Feb 15, 2014 at 23:38

citizenslave

1,41814 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

pete Over a year ago

Ah, makes total sense! Yes, it is a programming exercise in data structures and algorithms, just tried whipping it out for fun. Thanks!

citizenslave Over a year ago

It would actually be quicker for you to push and pop from the front of the list. Saves you the need to traverse it. Just save a reference to the rootNode, set the rootNode reference to its nextNode, set the original node's nextNode reference to null and return it. Same for push. The only reason you'd need to traverse the list would be if you wanted to enforce a queue instead of a stack behavior.

Collectives™ on Stack Overflow

Javascript: Linked List: Unable to delete object reference

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related