CODEWITHSUNDEEP
javascriptooplinked-list
pete
pete

Reputation: 2799

Javascript: Linked List: Unable to delete object reference

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!

Upvotes: 1

Views: 92

Answers (1)

citizenslave
citizenslave

Reputation: 1418

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.

Upvotes: 3

Related Questions