打印循环单链表时出现问题

Question

我有一个循环的单链表代码:

class Node{
constructor(value){
this.value = value;
this.next = null;
}
}
class LinkdeList{
constructor(){
this.first = null;
this.last = null;
}
empty(){
return this.first === null
}
insert(value){
let newest = new Node(value);
if (this.empty()) {
this.first = this.last = newest;
this.last.next = this.first;
}else{
newest.next = this.first;
this.first = newest;
this.last.next = this.first;
}
}
traverse(){
let aux = this.first;
while (aux.next != this.first) {
console.log(aux.value);
aux = aux.next;
}
}
}
let linked = new LinkdeList();
linked.insert("David");
linked.insert("John");
linked.insert("Adam")
linked.insert("Bob");
linked.traverse();

当我试图打印列表时，我只在控制台输入3个名称:

Bob
Adam
John

如你所见，我在链表中推入了4个名字。我试图在traverse方法中打印列表的值，但它不起作用，因为我没有进入控制台:

Bob
Adam
John
David

Answer 1

循环提前停止一步。这是do ... while环的一个很好的例子。当列表为空

时，还应该防止它失败。

traverse() {
if (this.empty()) return; // <---
let aux = this.first;
do {
console.log(aux.value);
aux = aux.next;
} while (aux != this.first);
}

关于你的代码的一些其他注释:

• 在一个非空的循环列表中，头总是在尾之后，实际上不需要维护first引用。只要保持last引用，知道您总是可以通过last.next获得列表的头部。

• console.log不应该在类方法中用于除调试之外的任何其他用途。通过将traverse方法设置为生成器，使其具有更大的灵活性。这样，您就可以将如何处理这些值的决定权留给该方法的调用者。

• 在循环列表中，节点不应该具有null值的next属性，不要在Node构造函数中分配null。而是给它一个自我引用。

• 将empty方法命名为isEmpty，因为它更清楚地表明这不会清空列表，但会返回是否为空。

• 修复类名中的错字:LinkedList

class Node {
constructor(value) {
this.value = value;
this.next = this; // self-reference
}
}
class LinkedList {
constructor() {
this.last = null; // No need for a `first`
}
isEmpty() {
return this.last === null;
}
insert(value) {
const newest = new Node(value);
if (!this.isEmpty()) {
newest.next = this.last.next;
this.last.next = newest;
}
this.last = newest;
}
*traverse() { // Generator
if (this.isEmpty()) return; // Guard
let aux = this.last;
do  {
aux = aux.next;
yield aux.value; // Don't print. Yield instead.
} while (aux != this.last);
}
}
const linked = new LinkedList();
linked.insert("David");
linked.insert("John");
linked.insert("Adam")
linked.insert("Bob");
// Caller of traverse can decide what to do: we want to print:
for (const name of linked.traverse()) console.log(name);

Answer 2

你的代码工作得很好!您只需要调整您的traversal()方法，因为while循环在它有机会记录最后一个节点之前就中断了。

你可以尝试这样做:

traverse(){
let aux = this.first;
while (true) {
console.log(aux.value);
aux = aux.next;
if (aux == this.first) {
break;
}
}
}

Answer 3

我将展开一个属性(count)

constructor() {
...
this.count = 0;   
}

当insert被调用时计算

insert(value) {
...
this.count = this.count + 1;
}

如果以后有扩展删除方法，请记住计算它

remove() {
...
this.count = this.count - 1;
}

并调整遍历的条件表达式，

用for (let i = this.count; i > 0; i--)代替while (aux.next != this.first)

我更喜欢trincot的答案，我的答案是针对小范围的代码更改。

在实践中，我将用类似的结构来设计它(trincot的答案)。

class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkdeList {
constructor() {
this.count = 0;
this.first = null;
this.last = null;
}
empty() {
return this.first === null
}
insert(value) {
let newest = new Node(value);
if (this.empty()) {
this.first = this.last = newest;
this.last.next = this.first;
} else {
newest.next = this.first;
this.first = newest;
this.last.next = this.first;
}
this.count = this.count + 1;
}
traverse() {
let aux = this.first;
for (let i = this.count; i > 0; i--) {
console.log(aux.value);
aux = aux.next;
}
}
}
let linked = new LinkdeList();
linked.insert("David");
linked.insert("John");
linked.insert("Adam")
linked.insert("Bob");
linked.traverse();