Стоимость поиска элемента, находящегося в начале связанного списка, действительно одна, потому что вы будете держать указатель на этот первый элемент.Таким образом, было бы O (1) найти первый элемент.
В случае двунаправленного односвязного списка, предполагая, что вы имеете в виду указатель на первый и последний элемент односвязногоСписок, вы действительно обнаружите, что время, чтобы найти последний элемент будет O (1), потому что у вас есть ссылка, где именно он находится.
Однако рассмотрим случай двунаправленного односвязного списка, в котором вы хотите найти (n-1) -й элемент в этом списке.Внезапно вы обнаружите, что вам нужно перебирать n-1 элементов, пока не дойдете до этого элемента.Таким образом, вы обнаружите, что в наихудшем случае времени выполнения для односвязного списка с двойным окончанием будет O (n-1), что на самом деле равно O (n).
Даже в том случае, если у вас был двойной конец, дваждысвязанный список, вы обнаружите, что в худшем случае время выполнения будет O (n / 2) (при условии, что у вас есть механизм, чтобы определить, был ли элемент в первой половине второй половины, что маловероятно).Но O (n / 2) все еще действительно O (n).
Поскольку мы обычно ссылаемся на наихудший случай, когда говорим о большой временной сложности, вы можете видеть, что связанные списки неизменно O (n).
Примечание. Это не означает, чтоbig-o - единственная мера сложности времени.В зависимости от вашей реализации амортизированная или вероятностная временная сложность может действительно отличаться от ее наихудшей временной сложности и, вероятно, равна.