Лабораторная работа «Линейные и циклические списки»
Цель: понять, чем связанное хранение отличается от массива.
Узел:
function createNode(value, next = null) {
return { value, next };
}
Обязательные функции:
function pushFront(head, value) {}
function pushBack(head, value) {}
function findNode(head, value) {}
function deleteValue(head, value) {}
function listLength(head) {}
function reverseList(head) {}
function toArray(head) {}
После односвязного списка студент реализует циклический вариант.
Обязательные алгоритмические задания:
-
вставка по позиции;
-
удаление первого совпадения;
-
удаление всех совпадений;
-
разворот списка;
-
поиск среднего элемента двумя указателями;
-
определение наличия цикла алгоритмом «черепаха и заяц»;
-
задача Иосифа на циклическом списке.
Эксперимент: сравнить вставку в начало массива и связного списка; поиск по индексу в массиве и списке.
Нужно обязательно обсудить, что измеренная в Chrome длительность — экспериментальный результат конкретной реализации, тогда как асимптотическая оценка характеризует рост числа операций.