Why is my linked list object in JavaScript not updating when I try to add a node to the beginning of-CodePudding

I'm trying to create a linked list using a factory function. When I run the method append on the list console.log displays the correct value. The prepend method on the other hand doesn't seem to be working when I console.log the resulting list. However, when I run a method to return the value of the list and log that I get the value I'm looking for. The code is as follows:

//linked list factory function
const LinkedListFactory = (initialNode) => {
  //declare initial value of the list
  let head = { value: initialNode.value, nextNode: initialNode.nextNode };

  //method to return list
  const giveList = () => {
    return head;
  };

  //method to return last node in list
  const getLast = () => {
    let lastNode = head;
    if (lastNode) {
      while (lastNode.nextNode) {
        lastNode = lastNode.nextNode;
      }
    }
    return lastNode;
  };

  //method to append node to the end of the list
  const append = (node) => {
    getLast().nextNode = node;
  };

  //method to add node to the front of the list (not working)
  const prepend = (node) => {
    let temp = { ...head };
    node.nextNode = temp;
    head = node;
    //gives the correct updated value of the list
    console.log(head);
  };

  return { head, append, prepend, giveList };
};

//node factory function to create data nodes
const NodeFactory = (value = null, nextNode = null) => {
  return { value, nextNode };
};

//creating test nodes
let node1 = NodeFactory("This is node 1");
let node2 = NodeFactory("This is node 2");
let node3 = NodeFactory("This is node 3");
let node4 = NodeFactory("This is node 4");

let list = LinkedListFactory(node1);
console.log(list.head);

list.append(node2);

console.log(list.head);

list.prepend(node3);

//These two statements give different values in the console
console.log(list.head);
console.log(list.giveList());

I did some googling to try and pin down the problem but I've had no luck so far. I expected node3 to be added to the beginning of the linked list and point to node1 which would then point to node2. When I console.log the list it only shows node1 and node2 but not node3. When I run a method to return the linked list and log it I get the value I'm looking for. I don't know why it's doing this behaviour and I'm very confused.

CodePudding user response：

The problem is that head = node is not actually doing what you think it is doing.

First let's have a look at the LinkedListFactory, which internally declares a variable head and initializes it with the contents of the Node that is passed to LinkedListFactory. After you declaring the methods you return a new object with them and the head node in it. (I will call it the "list" from now)

JavaScript objects are always references to their underlying values. This means after LinkedListFactory returns the "list" object's head property will point to the same value as the head variable that was declared in the LinkedListFactory.

When you, in prepend, set the head variable to equal to a new temp Node, the "list" object's head property will still point to the original value.

To achieve what you want you need to change prepend to look like something like this:

function prepend(node) {
    let temp = this.head; // temp points to the old head
    this.head = node; // overwrite pointer to head on list
    this.head.nextNode = temp; // point to old head
    head = this.head; // keep head and this.head in sync
  }

In this case this will refer to the object the prepend function was called on, so the "list", and we can modify it.

In your implementation we are only changing what the internal variable head is pointing to. In this implementation we change the head property of the "list".

I can recommend you to have a look at these MDN pages:

I thought about this a little bit more. Your implementation works, you just give a meaning to the "list"'s head property where there is none. You can simply remove it as it is only confusing:

//linked list factory function
const LinkedListFactory = (initialNode) => {
  //declare initial value of the list
  let head = { value: initialNode.value, nextNode: initialNode.nextNode };

  //method to return list
  const giveList = () => {
    return head;
  };

  //method to return last node in list
  const getLast = () => {
    let lastNode = head;
    if (lastNode) {
      while (lastNode.nextNode) {
        lastNode = lastNode.nextNode;
      }
    }
    return lastNode;
  };

  //method to append node to the end of the list
  const append = (node) => {
    getLast().nextNode = node;
  };

  //method to add node to the front of the list (not working)
  const prepend = (node) => {
    let temp = { ...head };
    node.nextNode = temp;
    head = node;
    //gives the correct updated value of the list
    console.log(head);
  };

  return { append, prepend, get head() { return giveList(); } }; // I aliased giveList to a `head` setter
};

//node factory function to create data nodes
const NodeFactory = (value = null, nextNode = null) => {
  return { value, nextNode };
};

//creating test nodes
let node1 = NodeFactory("This is node 1");
let node2 = NodeFactory("This is node 2");
let node3 = NodeFactory("This is node 3");
let node4 = NodeFactory("This is node 4");

let list = LinkedListFactory(node1);
console.log(list.head);

list.append(node2);

console.log(list.head);

list.prepend(node3);

console.log(list.head);