JavaScript 中的 LinkedList push() 方法,使用了 this.tail,无法理解按值引用。

huangapple go评论76阅读模式
英文:

LinkedList push() method in JavaScript with a this.tail , unable to understand the reference by value

问题

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    let newNode = new Node(val)
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      console.log(this.tail);
      console.log(this.tail.next);
      debugger
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
}

let x = new SLL();
x.push('Hi');
x.push('Hello');
x.push('How');
x.push('Are');
x.push('You');
x.push('Man');

Doubt:
在第二次执行push('Hello')之后,在else部分将tail赋值为新节点 "this.tail = newNode"。但在第三次执行push('How')时,为什么this.tail仍然引用this.head

我已经使用console.log输出了this.tailthis.tail.next的值。输出显示了新的节点。我无法理解为什么它仍然引用this.head

Usecase 1:

let l = { a : 1}
let o;
let p;

o = l;
p = o;

p.a = 2;

console.log("l",l);
console.log("o",o);
console.log("p",p);

p = { a:10};

console.log("l",l);
console.log("o",o);
console.log("p",p);

p = {a:10}时,会创建一个新的内存空间,对吗?

现在从 "p" 到 "o" 的链接断开了,对吗?

英文:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

class SLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val) {
    let newNode = new Node(val)
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      console.log(this.tail);
      console.log(this.tail.next);
      debugger
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
}

let x = new SLL();
x.push(&#39;Hi&#39;);
x.push(&#39;Hello&#39;);
x.push(&#39;How&#39;);
x.push(&#39;Are&#39;);
x.push(&#39;You&#39;);
x.push(&#39;Man&#39;);

<!-- end snippet -->

Doubt:
After the 2nd push('Hello'), the tail is assigned with the newNode "this.tail = newNode" under else part. But in the 3rd push "push('How')" how the this.tail is still referencing the this.head.

I have done console.log of both "this.tail" and "this.tail.next".The output shows fresh node. Am not able to understand how this still reference to the this.head.

JavaScript 中的 LinkedList push() 方法,使用了 this.tail,无法理解按值引用。

JavaScript 中的 LinkedList push() 方法,使用了 this.tail,无法理解按值引用。

Thanks for the answers!

Usecase 1:

let l = { a : 1}
let o;
let p;

o = l;
p = o;

p.a = 2;

console.log(&quot;l&quot;,l);
console.log(&quot;o&quot;,o);
console.log(&quot;p&quot;,p);

p = { a:10};


console.log(&quot;l&quot;,l);
console.log(&quot;o&quot;,o);
console.log(&quot;p&quot;,p);

when p = {a:10} a new memory space is created right?

Now the link is broken form "p" to "o" right?

JavaScript 中的 LinkedList push() 方法,使用了 this.tail,无法理解按值引用。

答案1

得分: 1

head引用列表中的第一个节点,但当第二个节点添加到列表时,第一个节点的next属性将会更新。我们可以通过跟随next链来“看到”head节点之后的节点。

这可能有助于形象化理解:

当执行x = new SLL()时,我们可以将其想象如下:

 x
 ↓
┌─────SLL────┐
│ head: null │
│ tail: null │
│ length: 0  │
└────────────┘

当执行x.push('Hi');时,会创建newNode

                    newNode
                     ↓
 x                 ┌─────Node────┐
 ↓                 │ val: 'Hi'   │
┌─────SLL────┐     │ next: null  │
│ head: null │     └─────────────┘
│ tail: null │
│ length: 0  │
└────────────┘

然后进入if块,其中this.headthis.tail都被引用到新节点,最后列表的长度属性被更新:

                    newNode
                     ↓
 x                 ┌─────Node────┐
 ↓             ┌──►│ val: 'Hi'   │
┌─────SLL────┐ │ ┌►│ next: null  │
│ head: ───────┘ │ └─────────────┘
│ tail: ─────────┘
│ length: 1  │
└────────────┘

现在回到主程序,执行x.push('Hello');。再次创建一个新节点:

                                        newNode
                                         ↓
 x                 ┌─────Node────┐     ┌─────Node────┐
 ↓             ┌──►│ val: 'Hi'   │     │ val: 'Hello'│
┌─────SLL────┐ │ ┌►│ next: null  │     │ next: null  │
│ head: ───────┘ │ └─────────────┘     └─────────────┘
│ tail: ─────────┘
│ length: 1  │
└────────────┘

这次进入了else块,执行this.tail.next = newNode;。它更新了this.tail引用的节点的next属性:

                                        newNode
                                         ↓
 x                 ┌─────Node────┐     ┌─────Node────┐
 ↓             ┌──►│ val: 'Hi'   │ ┌──►│ val: 'Hello'│
┌─────SLL────┐ │ ┌►│ next: ────────┘   │ next: null  │
│ head: ───────┘ │ └─────────────┘     └─────────────┘
│ tail: ─────────┘
│ length: 1  │
└────────────┘

这是一个重要的步骤:通过改变next属性来扩展链表,这是在head属性引用的节点上发生的,这解释了为什么你可以通过查看head来“看到”已扩展的链表。

else块中,下一条语句this.tail = newNode;更新了链表实例的tail属性,最后更新了长度属性:

                                        newNode
                                         ↓
 x                 ┌─────Node────┐     ┌─────Node────┐
 ↓             ┌──►│ val: 'Hi'   │ ┌──►│ val: 'Hello'│
┌─────SLL────┐ │   │ next: ────────┘ ┌►│ next: null  │
│ head: ───────┘   └─────────────┘   │ └─────────────┘
│ tail: ─────────────────────────────┘
│ length: 2  │
└────────────┘

这个过程会继续添加下一个单词。每次调用push都会改变tail节点的next属性,并使其引用一个新的节点。

希望这样能够解释为什么head可以通过查看列表的末尾来“看到”对列表的更改。

英文:

The head references the first node in the list, but that first node will get its next property updated when a second node is added to the list. We can "see" the tail node from the head node by following the next chain.

It may help to visualise this:

When x = new SLL() has executed, we can picture it as follows:

 x
 ↓
┌─────SLL────┐
│ head: null │
│ tail: null │
│ length: 0  │
└────────────┘

When x.push(&#39;Hi&#39;); is executed, newNode is created:

                    newNode
                     ↓
 x                 ┌─────Node────┐
 ↓                 │ val: &#39;Hi&#39;   │
┌─────SLL────┐     │ next: null  │
│ head: null │     └─────────────┘
│ tail: null │
│ length: 0  │
└────────────┘

Then the if block is entered, where both this.head and this.tail are made to reference that new node, and finally the list's length property is updated:

                    newNode
                     ↓
 x                 ┌─────Node────┐
 ↓             ┌──►│ val: &#39;Hi&#39;   │
┌─────SLL────┐ │ ┌►│ next: null  │
│ head: ───────┘ │ └─────────────┘
│ tail: ─────────┘
│ length: 1  │
└────────────┘

Now to the main program again, where x.push(&#39;Hello&#39;); is executed. Again a new node is created:

                                        newNode
                                         ↓
 x                 ┌─────Node────┐     ┌─────Node────┐
 ↓             ┌──►│ val: &#39;Hi&#39;   │     │ val: &#39;Hello&#39;│
┌─────SLL────┐ │ ┌►│ next: null  │     │ next: null  │
│ head: ───────┘ │ └─────────────┘     └─────────────┘
│ tail: ─────────┘
│ length: 1  │
└────────────┘

This time the else block is entered, where this.tail.next = newNode; is executed. It updates the next property of the node that this.tail references:

                                        newNode
                                         ↓
 x                 ┌─────Node────┐     ┌─────Node────┐
 ↓             ┌──►│ val: &#39;Hi&#39;   │ ┌──►│ val: &#39;Hello&#39;│
┌─────SLL────┐ │ ┌►│ next: ────────┘   │ next: null  │
│ head: ───────┘ │ └─────────────┘     └─────────────┘
│ tail: ─────────┘
│ length: 1  │
└────────────┘

This was an important step: the linked list was extended by mutating a next property, which is happening at a node that also the head property references, and explains why you can "see" that extended list by looking at head.

In that else block the next statement, this.tail = newNode; updates the tail property of the linked list instance, and finally the length property is updated:

                                        newNode
                                         ↓
 x                 ┌─────Node────┐     ┌─────Node────┐
 ↓             ┌──►│ val: &#39;Hi&#39;   │ ┌──►│ val: &#39;Hello&#39;│
┌─────SLL────┐ │   │ next: ────────┘ ┌►│ next: null  │
│ head: ───────┘   └─────────────┘   │ └─────────────┘
│ tail: ─────────────────────────────┘
│ length: 2  │
└────────────┘

This process continues with the addition of the next word. Every push will mutate the next property of the tail node and make it reference a new node.

I hope this clarifies why head can "see" the changes that are made to the list as you push new elements at its end.

答案2

得分: 0

带有尾部地址指针的链表实现

class Node {
  constructor() {
    this.value = null;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.root = null;
    this.tail;
  }

  insert(value) {
    // 创建一个Node类的对象
    let newNode = new Node();

    if (!this.root) {
      newNode.value = value;
      this.root = newNode;
      this.tail = this.root;
      return;
    }

    let current = this.tail;
    // 为新节点赋值
    newNode.value = value;

    current.next = newNode;
    // 更新尾部到新插入节点的地址
    this.tail = current.next;
  }

  // 打印所有节点
  printAllNodes() {
    let current = this.root;
    while (current != null) {
      console.log(current.value);
      current = current.next;
    }
  }
}

let list = new SinglyLinkedList();

list.insert(5);
list.insert(10);
list.insert(15);
list.insert(20);
list.insert(25);

list.printAllNodes();

// console.log(list.root);

请注意,我已经为您翻译了代码的关键部分。如果您需要任何其他帮助,请随时提出。

英文:

Linked list implementation with Tail address pointer

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

class Node {
  constructor() {
    this.value = null;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.root = null;
    this.tail;
  }

  insert(value) {
    // create object of node class
    let newNode = new Node();

    if (!this.root) {
      newNode.value = value;
      this.root = newNode;
      this.tail = this.root;
      return;
    }

    let current = this.tail;
    //assign value to newNode
    newNode.value = value;

    current.next = newNode;
    //update the tail to newly inserted Node address
    this.tail = current.next;
  }

  //   To print all nodes
  printAllNodes() {
    let current = this.root;
    while (current != null) {
      console.log(current.value);
      current = current.next;
    }
  }
}

let list = new SinglyLinkedList();

list.insert(5);
list.insert(10);
list.insert(15);
list.insert(20);
list.insert(25);

list.printAllNodes();

// console.log(list.root);

<!-- end snippet -->

huangapple
  • 本文由 发表于 2023年6月30日 00:21:42
  • 转载请务必保留本文链接:https://go.coder-hub.com/76582909.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定