我很难理解链表中的第一个节点/旧头在哪里。
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
var newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
shift() {
if (!this.head) return undefined;
var currentHead = this.head;
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}
}
我知道我们为旧头部添加了一个新变量，然后将头部向上移动到下一个节点，但是旧头部/前一个节点在哪里?我看到我们返回了它，这就是从列表中删除它的原因吗?我知道代码是有效的，我只是好奇那个节点去了哪里。
该节点的未来掌握在称为shift的代码手中。如果调用者忽略返回的引用，则该节点将变得不可达，并且垃圾收集器可以决定释放其内存。
假设我们有一个链表mylist，它有三个节点(值为1,2和3)。我们可以将其可视化如下(我省略了length，因为它与问题无关):
mylist
↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ head: ──────>│ val: 1 │ │ val: 2 │ │ val: 3 │
│ tail: ─────┐ │ next: ──────>│ next: ──────>│ next: null│
└───────────┘│ └───────────┘ └───────────┘┌>└───────────┘
└─────────────────────────────┘
现在当我们调用mylist.shift()时，我们将currentHead赋值并改变head的值，如下所示:
mylist currentHead
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ head: ──────┐│ val: 1 │ │ val: 2 │ │ val: 3 │
│ tail: ─────┐││ next: ──────>│ next: ──────>│ next: null│
└───────────┘││└───────────┘┌>└───────────┘┌>└───────────┘
│└─────────────┘ │
└─────────────────────────────┘
因此，除非任何其他代码持有对值为1的节点的引用，否则现在只有一个局部变量currentHead引用它。当函数返回时，该变量的生命周期将结束，当它的值被返回时，现在由方法的调用者来捕获它。
那么我们假设调用者执行了let node = mylist.shift()，那么我们就会出现这种情况(我移动了一些盒子):
node
↓
┌───────────┐
│ val: 1 │
│ next: ─────┐
└───────────┘│
mylist │
↓ │
┌───────────┐└>┌───────────┐ ┌───────────┐
│ head: ──────>│ val: 2 │ │ val: 3 │
│ tail: ─────┐ │ next: ──────>│ next: null│
└───────────┘│ └───────────┘┌>└───────────┘
└──────────────┘
但是，如果我们只调用shift而不捕获返回值，就像mylist.shift()一样，那么就不会再有对值为1的节点的引用:
┌───────────┐
│ val: 1 │
│ next: ─────┐
└───────────┘│
mylist │
↓ │
┌───────────┐└>┌───────────┐ ┌───────────┐
│ head: ──────>│ val: 2 │ │ val: 3 │
│ tail: ─────┐ │ next: ──────>│ next: null│
└───────────┘│ └───────────┘┌>└───────────┘
└──────────────┘
换句话说，在JavaScript中没有办法以某种方式访问该节点。在这种情况下，节点仍然在那里——可能再过一毫秒、一分钟或一小时——但它对程序是不可见的，它的命运现在完全掌握在垃圾收集器的手中，它可能随时决定释放该节点占用的内存。
我正在使用您的代码创建一个singlyLinkedList，它将保存我的HTML列表的值。
当你点击shift时，它会运行shift函数，在这里你的shift函数被调用。
你可以看到我将返回节点的值(旧的头部)分配给元素的textContent，所以你可以在顶部看到返回值。
update函数只是将类中的列表与HTML列表同步。
function push() {
const value = document.getElementById('input').value;
value && list.push(value);
update();
}
function shift() {
// Below i'm using the returned value of shift (the head of the list),
// otherwise it would be lost, and there would be no reference to it,
// so it would be collected by the Garbage collector
document.getElementById('shifted').textContent = list.shift().val;
update();
}
function update() {
const li = document.getElementById('list');
li.innerHTML = '';
let index = list.head;
while (index) {
const node = document.createElement('li');
node.textContent = index.val;
li.appendChild(node);
index = index.next;
}
}
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(val) {
var newNode = new Node(val);
if (!this.head) {
this.head = newNode;
this.tail = this.head;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
shift() {
if (!this.head) return undefined;
var currentHead = this.head;
this.head = currentHead.next;
this.length--;
if (this.length === 0) {
this.tail = null;
}
return currentHead;
}
}
document.getElementById('push').addEventListener('click', push);
document.getElementById('shift').addEventListener('click', shift);
const list = new SinglyLinkedList();
// Adding some initial items to the list and displaying the list
list.push("1"); list.push("2"); list.push("3"); update();<p>The Shifted/Returned node value is <span id="shifted">Undefined</span></p>
<button id="shift">Shift</button>
<label for="add">Add a node to the list</label>
<input id="input" name="add" type="text" />
<button id="push">Push</button>
<ul id="list">
</ul>