输出单链表 - JavaScript 中文教程

假设我们有一个单链表（如递归和栈一章中所述）

          let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};
        

编写一个函数 printList(list)，它逐个输出列表项。

使用循环和递归两种方法实现解决方案。

哪个更好：使用递归还是不使用递归？

基于循环的解决方案

基于循环的解决方案变体

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {
  let tmp = list;

  while (tmp) {
    alert(tmp.value);
    tmp = tmp.next;
  }

}

printList(list);

请注意，我们使用临时变量tmp来遍历列表。从技术上讲，我们可以使用函数参数list代替

          function printList(list) {

  while(list) {
    alert(list.value);
    list = list.next;
  }

}
        

…但这将是不明智的。将来我们可能需要扩展函数，对列表做其他事情。如果我们改变list，那么我们将失去这种能力。

说到好的变量名，这里的list就是列表本身。它的第一个元素。它应该保持这样。这很清楚且可靠。

另一方面，tmp的作用仅仅是列表遍历，就像for循环中的i一样。

递归解决方案

printList(list)的递归变体遵循一个简单的逻辑：要输出一个列表，我们应该输出当前元素list，然后对list.next执行相同的操作。

let list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: {
        value: 4,
        next: null
      }
    }
  }
};

function printList(list) {

  alert(list.value); // output the current item

  if (list.next) {
    printList(list.next); // do the same for the rest of the list
  }

}

printList(list);

现在哪个更好？

从技术上讲，循环更有效。这两个变体做的事情一样，但循环不会为嵌套函数调用消耗资源。

另一方面，递归变体更短，有时更容易理解。