Сложность алгоритма, вставленного элементом в круговой связанный список на переднем конце

Question

В круговом списке, если элементы необходимо вставить спереди [непосредственно перед узлом, указанным головой], могут быть сделаны в O (1) (см. Ответ здесь)

Но в книге в настоящее время я уже упоминался, что это делается в O (n) (обычный метод). Я также видел несколько лекций, все они упоминают обычный метод пересечения списка и добавления элемента.

Мой вопрос:

1. В практических сценариях какой метод используется?

2. Я собираюсь присутствовать на экзамене, который состоит из MCQ, если задается выше, если задается вопрос о том, чтобы отметить O (n), так как это стандартный ответ?

Answer 1

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

1. Известен ли алгоритм программисту.
2. Простота кодирования (проще всего, если она уже реализована в какой -то библиотеке, которую вы можете использовать).
3. Скорость - это зависит от того, как используется структура данных.
4. Пространственные накладные расходы, взятые структурой данных.

Интеллектуальный программист должен учитывать все это и попытаться сделать себя более осведомленными о различных алгоритмах и структурах данных.