Какой временной и пространственный порядок имеют основные операции с односвязным списком?

Основные операции с односвязным списком и их временная и пространственная сложность:

• Добавление в начало списка:

  • Время: O(1) — просто создаём новый узел и меняем указатель головы.
  • Память: O(1) — выделяется память под новый узел.

• Добавление в конец списка:

  • Время: O(n) — нужно пройти по всем узлам, чтобы найти последний.
  • Память: O(1) — выделяется память под новый узел.

• Удаление из начала списка:

  • Время: O(1) — меняется указатель головы.
  • Память: O(1) — освобождается память удалённого узла.

• Удаление из конца списка:

  • Время: O(n) — нужно найти предпоследний узел.
  • Память: O(1) — освобождается память удалённого узла.

• Поиск элемента:

  • Время: O(n) — в худшем случае нужно пройти весь список.
  • Память: O(1) — не требует дополнительной памяти.

Таким образом, односвязный список эффективен для операций в начале, но менее эффективен для операций в конце или поиска по индексу.