Search code examples
javascriptlinked-list

Dangling Node when Deleting Node From Linked List at the head of the Linked List


my question is about the operation to delete the node that is the head, based on the value passed into the delete node function, when the head.value === valueToDelete. we will simply declare the head as the next value.

In Javascript, what happens to the old head that has lost its linkage in the list and is no longer the head (in memory, etc)? Wouldn't mind a break down in other languages too that are more strictly typed. thanks in advance for helping me understand.

var LinkedList = function () {
  this.head = null;
  this.tail = null;
};
LinkedList.prototype.makeNode = function (val) {
  var node = {};
  node.val = val;
  node.next = null;
  return node;
};
LinkedList.prototype.deleteFromAnywhere = function (valueToDelete) {
  var current = this.head;
  var previous = current;
  //from head:
  if (current.val === valueToDelete || valueToDelete === this.head.val) {
    this.head = current.next;
  }
  //from middle:
  while (current.next) {
    if (current.val === valueToDelete) {
      //drop the link of the deleted, point the one before it to the one after it
      previous.next = current.next;
    }
    //from tail:
    if (current.val === valueToDelete && (current.next === null || this.tail.val === valueToDelete)) {
      this.tail = previous;
      previous.next = null;
    }
    //increment, keep previous one behind/current one ahead.
    //ie skip ahead.
    previous = current;
    current = current.next;
  }
};
LinkedList.prototype.addToTail = function (value) {
  var newTail = this.makeNode(value);
  if (!this.head) {
    this.head = newTail;
  }
  if (this.tail) {
    this.tail.next = newTail;
  }
  this.tail = newTail;
};
var list = new LinkedList();
list.addToTail(4);
list.addToTail(5);
list.addToTail(8);
list.deleteFromAnywhere(5);
console.log(list);


Solution

  • Objects that are no longer referenced are available for garbage collection. Mozilla contributors write:

    Low-level languages like C, have manual memory management primitives such as malloc() and free(). In contrast, JavaScript automatically allocates memory when objects are created and frees it when they are not used anymore (garbage collection).

    This garbage collector runs now and then and frees the associated memory. This is not related to strict/lose typing. Java, which is strictly typed, also has such garbage collector.