Вернуться к уроку

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

важность: 5

Односвязный список – это структура данных, которая состоит из элементов, каждый из которых хранит ссылку на следующий. Последний элемент может не иметь ссылки, либо она равна null.

Например, объект ниже задаёт односвязный список, в next хранится ссылка на следующий элемент:

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

Графическое представление этого списка:

Альтернативный способ создания:

var list = { value: 1 };
list.next = { value: 2 };
list.next.next = { value: 3 };
list.next.next.next = { value: 4 };

Такая структура данных интересна тем, что можно очень быстро разбить список на части, объединить списки, удалить или добавить элемент в любое место, включая начало. При использовании массива такие действия требуют обширных перенумерований.

Задачи:

  1. Напишите функцию printList(list), которая выводит элементы списка по очереди, при помощи цикла.
  2. Напишите функцию printList(list) при помощи рекурсии.
  3. Напишите функцию printReverseList(list), которая выводит элементы списка в обратном порядке, при помощи рекурсии. Для списка выше она должна выводить 4,3,2,1
  4. Сделайте вариант printReverseList(list), использующий не рекурсию, а цикл.

Как лучше – с рекурсией или без?

Вывод списка в цикле

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

function printList(list) {
  var 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;
  }

}

…Но при этом мы в будущем не сможем расширить функцию и сделать со списком что-то ещё, ведь после окончания цикла начало списка уже нигде не хранится.

Поэтому и используется временная переменная – чтобы сделать код расширяемым, и, кстати, более понятным, ведь роль tmp – исключительно обход списка, как i в цикле for.

Вывод списка с рекурсией

Рекурсивный вариант printList(list) следует простой логике: вывести текущее значение (1), а затем пропустить через себя следующее (2):

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

function printList(list) {

  alert( list.value ); // (1)

  if (list.next) {
    printList(list.next); // (2)
  }

}

printList(list);

Обратный вывод с рекурсией

Обратный вывод – почти то же самое, что прямой, просто сначала мы обрабатываем следующее значение, а потом – текущее:

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

function printReverseList(list) {

  if (list.next) {
    printReverseList(list.next);
  }

  alert( list.value );
}

printReverseList(list);

Обратный вывод без рекурсии

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

function printReverseList(list) {
  var arr = [];
  var tmp = list;

  while (tmp) {
    arr.push(tmp.value);
    tmp = tmp.next;
  }

  for (var i = arr.length - 1; i >= 0; i--) {
    alert( arr[i] );
  }
}

printReverseList(list);

Обратный вывод без рекурсии быстрее.

По сути, рекурсивный вариант и нерекурсивный работают одинаково: они проходят список и запоминают его элементы, а потом выводят в обратном порядке.

В случае с массивом это очевидно, а для рекурсии запоминание происходит в стеке (внутренней специальной структуре данных): когда вызывается вложенная функция, то интерпретатор сохраняет в стек текущие параметры. Вложенные вызовы заполняют стек, а потом он выводится в обратном порядке.

При этом, при рекурсии в стеке сохраняется не только элемент списка, а другая вспомогательная информация, необходимая для возвращения из вложенного вызова. Поэтому тратится больше памяти. Все эти расходы отсутствуют в варианте без рекурсии, так как в массиве хранится именно то, что нужно.

Преимущество рекурсии, с другой стороны – более короткий и, зачастую, более простой код.