JavaScript 中链表的这个 pop() 方法是否正确？它有效，但我很好奇我是否使用正确的方法

Question

pop(){
if(this.head == null){
return undefined;
}
else if(this.head == this.tail){
this.head = null;
this.tail = null;
this.length--
}
else{
let temp = this.head;
let pre = this.head;
while(temp.next){
pre = temp;
temp = temp.next;
}
this.tail = pre;
this.tail.next = null;
this.length--
}

我更关心的是链接列表中只有一个项目的情况。

Answer 1

代码很好。

下面是一个将测试实现的程序。当然，这个类需要用其他一些方法来完成。可以将CCD_ 1简化为仅CCD_。

class Node {
constructor(value, next=null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor(...values) {
this.head = this.tail = null;
this.length = 0;
for (value of values) {
this.push(value);
}
}
push(value) {
if (this.tail) {
this.tail = this.tail.next = new Node(value);
} else {
this.head = this.tail = new Node(value);
}
this.length++;
}
pop(){
if (this.head == null){
return;
}
else if (this.head == this.tail){
this.head = null;
this.tail = null;
this.length--
}
else {
let temp = this.head;
let pre = this.head;
while(temp.next){
pre = temp;
temp = temp.next;
}
this.tail = pre;
this.tail.next = null;
this.length--
}
}
*[Symbol.iterator]() {
for (let node = this.head; node; node = node.next) {
yield node.value;
}
}
consistent() {
if (this.length != [...this].length) throw "length is inconsistent";
if (this?.tail?.next) throw "tail is inconsistent";
}
}
// Perform tests by doing the same operations on a native array simultaneously and comparing the result
let list = new LinkedList;
let arr = [];
for (let i = 0; i < 10000; i++) {
let choice = Math.random() > 0.5 && list.length < 10;
let value = Math.floor(Math.random() * 100);
if (choice) {
list.push(value);
arr.push(value);
} else {
list.pop();
arr.pop();
}
list.consistent();
if (JSON.stringify(arr) !== JSON.stringify([...list])) throw "Difference detected";
}
console.log("Tests done: all OK");

在JavaScript中，pop()通常返回弹出的值(并非所有语言(例如C++(都是这样(，因为本机数组原型就是这样定义pop的。因此，您可能需要考虑将相同的原理应用于pop方法。

以下是上述代码的一个版本，其中包括该功能(并对其进行了测试(：

class Node {
constructor(value, next=null) {
this.value = value;
this.next = next;
}
}
class LinkedList {
constructor(...values) {
this.head = this.tail = null;
this.length = 0;
for (value of values) {
this.push(value);
}
}
push(value) {
if (this.tail) {
this.tail = this.tail.next = new Node(value);
} else {
this.head = this.tail = new Node(value);
}
this.length++;
}
pop() {
if (this.head == null){
return;
}
const value = this.tail.value;
if (this.head == this.tail){
this.head = null;
this.tail = null;
} else {
let temp = this.head;
let pre = this.head;
while(temp.next){
pre = temp;
temp = temp.next;
}
this.tail = pre;
this.tail.next = null;
}
this.length--;
return value;
}
*[Symbol.iterator]() {
for (let node = this.head; node; node = node.next) {
yield node.value;
}
}
consistent() {
if (this.length != [...this].length) throw "length is inconsistent";
if (this?.tail?.next) throw "tail is inconsistent";
}
}
let list = new LinkedList;
let arr = [];
for (let i = 0; i < 10000; i++) {
let choice = Math.random() > 0.5 && list.length < 10;
let value = Math.floor(Math.random() * 100);
if (choice) {
list.push(value);
arr.push(value);
} else {
if (list.pop() !== arr.pop()) throw "Inconsistent pop return value";
}
list.consistent();
if (JSON.stringify(arr) !== JSON.stringify([...list])) throw "JSON is different";
}
console.log("tests done");

Answer 2

在列表中只有一个项目的情况下，这可能不起作用。

这段代码不会运行：

while(temp.next){
pre = temp;
temp = temp.next;
}

长度将减少。但我想，在长度为1的情况下，您必须将this.head和this.tail都指向null。