I have implemented a linked list in 2 ways in Javascript, but when doing so, I got really confused about what is really happening.

I was trying to create a mental image about what is being created, and what is pointing to what memory address (based on what I have learned about passing by reference), but I can't do it.

• Are both implementations correct?
• They seem to be doing the same thing, but do they behave in different ways under the hood?
• In option 1, for the prepend() method, I am creating a new object in memory, where "next" property is pointing to the existing memory address of "head" property, but "head" property is now pointing to the new object. Maybe it's a stupid question, but isn't this going in circles? Why does this work?

The differences are between the append() and prepend() methods.

Option 1:

class myLinkedList {
    constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
  }
  
  append(element){
    this.tail.next = {
      value: element,
      next: null
    }
    this.tail = this.tail.next;
  }

  prepend(element) {
    const newObj = {
      value: element,
      next: this.head
    }
    this.head = newObj;
  }
}


const linkedList = new myLinkedList(1);
linkedList.append(2);
linkedList.prepend(0);

Option 2:

class myLinkedList {
    constructor(value) {
    this.head = {
      value: value,
      next: null
    }
    this.tail = this.head;
  }
  
  append(element){
    const newNode = {
      value: element,
      next: null
    }
    this.tail.next = newNode;
    this.tail = newNode;
  }

  prepend(element) {
    const newNode = {
      value: element,
      next: null
    }
    newNode.next = this.head;
    this.head = newNode;
  }
}

const linkedList = new myLinkedList(1);
linkedList.append(2);
linkedList.prepend(0);

CodePudding user response：

You clarified your question in the comments.

The answer has to do with variable binding vs values.

JavaScript has internal representations for values like strings, numbers, user defined objects, and so on. That representation is the same whether or not the value is named foo, or is buried deep in some data structure.

Programs have variables. At any moment in time, a given variable is bound to a given value. This gives programmers a way to tell JavaScript what should happen to the values that they are bound to.

Assignment is binding values to things. When we assign to a variable, it is no longer bound to whatever old value it has been bound to. That old value may still exist in some data structure, or may become garbage to be cleaned up. But it is no longer associated with that variable.

And so here is what the sample code that you gave actually does.

-- Create a value and bind it to head.
let head = {
    value: 2,
    next: null
};
/* CURRENT BINDING:
 *
 *    head ----> {value:2, next:null}
 */

-- Create a value and bind it to newObj
let newObj = {
    value: 1,
    next: head
};
/* CURRENT BINDING:
 *
 *  newObj ----> {value:1, next:
 *    head ---->     {value:2, next:null}
 *               }
 */

-- Bind the variable head to the value newObj is bound to.
head = newObj;
/* CURRENT BINDING:
 *
 * head,newObj
 *         ----> {value:1, next:
 *                   {value:2, next:null}
 *               }
 */

-- And see that it worked.
console.log(head)

Does that clarify your model of how programs represent data enough to understand why this code doesn't create a circular reference?

But if you're curious, it is possible to create circular references.

let foo = {value:1}:
foo['next'] = foo;
console.log(foo);

How did that work, isn't assignment just binding values to things? Well, yes. But if the thing that it is bound to is somewhere in a data structure, then that data structure had to get changed to allow it to be bound.

What happens after you create circular references varies by language. In JavaScript, at some point after it is bound to nothing, the garbage collector will clean it up. In Python, it takes on a life of its own and you leak memory. And so on.