在链表上使用 shift() 时节点会去哪里？

Question

我无法理解链表中第一个节点/旧头的位置。

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;
    }
}

我明白了，我们给老头添加一个新的变量，然后把头往上移动到下一个节点，但是老头/上一个节点去哪了？我看到我们 return 它，是什么正在删除它/从列表中删除它？我知道代码有效，我只是好奇该节点的去向。

Answer 1

我正在使用您的代码创建一个 singlyLinkedList，它将保存我的 HTML 列表的值。

当您点击 shift 时，它会运行 shift 函数，其中会调用您的 shift 函数。

您可以看到我正在将返回的节点（旧头部）的值分配给元素的 textContent，因此您可以在顶部看到返回值。

更新功能只是将您的 class 列表与 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>

Answer 2

该节点的未来掌握在调用 shift 的代码手中。如果调用者忽略 returned 引用，该节点将变得不可访问，垃圾收集器可能会决定释放其内存。

假设我们有一个包含三个节点（值为 1、2 和 3）的链表 mylist。我们可以将其可视化如下（我省略了 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 引用它。此变量将在函数 returns 时达到其生命周期的终点，并且由于其值为 returned，现在由方法的调用者捕获它。

那么假设调用者已经完成了let node = mylist.shift()，那么我们就会有这种情况（我移动了一些方框）：

node
  ↓
┌───────────┐ 
│ val: 1    │
│ next: ─────┐
└───────────┘│
mylist       │   
  ↓          │    
┌───────────┐└>┌───────────┐  ┌───────────┐  
│ head: ──────>│ val: 2    │  │ val: 3    │
│ tail: ─────┐ │ next: ──────>│ next: null│
└───────────┘│ └───────────┘┌>└───────────┘
             └──────────────┘

但是，如果我们只调用 shift 而没有捕获 return 值，例如 mylist.shift()，那么将不再引用值为 1 的节点：

┌───────────┐ 
│ val: 1    │
│ next: ─────┐
└───────────┘│
mylist       │   
  ↓          │    
┌───────────┐└>┌───────────┐  ┌───────────┐  
│ head: ──────>│ val: 2    │  │ val: 3    │
│ tail: ─────┐ │ next: ──────>│ next: null│
└───────────┘│ └───────────┘┌>└───────────┘
             └──────────────┘

换句话说，在 JavaScript 中将无法以某种方式访问该节点。在那种情况下，节点仍然存在——可能再持续一毫秒、一分钟或一个小时——但它对程序是不可见的，它的命运现在完全掌握在垃圾收集器的手中，垃圾收集器可能决定在随时释放该节点占用的内存。

在链表上使用 shift() 时节点会去哪里？

Where does the node go when using shift() on a linked list?

javascript

algorithm

linked-list

data-structures