没有使用 return 语句时发生无限循环

Question

这是一个初学者问题。

我有 2 个简单的 classes，目的是创建一个链表。如果在其 if 语句中未使用 return 语句，我的 LinkedList class 中的 append 方法将导致无限循环。任何人都可以提供一些关于为什么会这样的见解吗？

class LinkedList {
    head: Nodule;

    append(appendedNodule: Nodule) {
        if (!this.head) {
            this.head = appendedNodule;
        }
        let current: Nodule = this.head;
        while (current.next) {
            current = current.next;
        };
        current.next = appendedNodule;

    }
}

class Nodule {
    data: number;
    next: Nodule;
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

Answer 1

让我们为您附加的第一个节点逐行执行代码：

    if (!this.head) {

这个条件成立：还没有人头。所以 if 块被执行

        this.head = appendedNodule;

所以现在我们有了一个头节点，也就是追加节点。没有return，所以我们继续执行方法

    }
    let current: Nodule = this.head;

现在我们还有一个局部变量current，它也指向头部（不再为空），它也是附加的节点。

    while (current.next) {

当前head没有下一个结点，所以while块没有执行

        current = current.next;

所以上面的指令没有执行

};

但是下一个是，因为我们不再处于 while 循环中了

    current.next = appendedNodule;

头部现在有一个下一个节点，这个下一个节点就是它自己。

因此，如果我们现在追加另一个节点，while 循环将获取下一个节点，一次又一次，直到它为空。但它永远不会为空，因为您已经创建了一个循环：

 ---------\
 |        | next
 \/       |
current ---

让我们逐行再次执行相同的方法：

    if (!this.head) {

条件现在为假。我们有一个头节点，所以跳过 if 块

        this.head = appendedNodule;
    }
    let current: Nodule = this.head;

当前变量引用到头节点

    while (current.next) {

这是真的，因为头节点的下一个节点就是它自己。所以我们执行 while 块

        current = current.next;

当前成为下一个节点。所以我们再次测试 while 条件。它仍然是正确的：下一个节点是当前节点。所以我们有一个无限循环。

};

Answer 2

我认为这里的问题在于LinkedList的初始化。一开始，列表是空的：

const linkedList = new LinkedList(); // linkedList = {head: undefined}

然后当您将第一项添加到列表中时：

linkedList.append(new Nodule(42));

发生以下情况：

append(appendedNodule: Nodule) { // appendedNodule = {data: 42, next: undefined}
    if (!this.head) { // Condition evaluates to true, since we just initialized the LinkedList
        this.head = appendedNodule; // linkedList = {head: {data: 42, next: undefined}}
    }
    let current: Nodule = this.head; 
    // current = {data: 42, next: undefined}

    // current.next is undefined, so we skip this loop entirely
    while (current.next) {
        current = current.next;
    };

    // current.next = current now! We've created a circular reference!
    current.next = appendedNodule;

}

看来问题出在这里的分支上。如果列表为空，我们只需要使用提供的 Nodule 实例定义 head。否则，我们需要追加到列表的末尾。我认为包装

let current: Nodule = this.head;
while (current.next) {
    current = current.next;
};
current.next = appendedNodule;

在 else 块中就可以了:-)

没有使用 return 语句时发生无限循环

Infinite loop occurs when no return statement is used

linked-list

infinite-loop

typescript