Вивести одинозв’язаний список

Скажімо, у нас є одинозв’язаний список (як описано в розділі Рекурсія та стек):

          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, то ми втрачаємо таку здатність.

Говорячи про хороші імена змінних, list тут – це сам список. Його перший елемент. І це повинно залишитися так. Це ясно і надійний.

З іншого боку, tmp використовується виключно проходу, як i у for циклі.

Рішення через рекурсію

Рекурсивний варіант 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); // виведіть поточний елемент

  if (list.next) {
    printList(list.next); // зробіть те ж саме для решти списку
  }

}

printList(list);

Що ж тепер краще?

Технічно цикл є більш ефективним. Ці два варіанти роблять те ж саме, але цикл не витрачає ресурси для вкладених викликів.

З іншого боку, рекурсивний варіант коротший, а іноді його легше зрозуміти.