Сколько элементов необходимо получить в операции get (x) в двусвязном списке?

Question

Есть вопрос о doubly linkedlist, о котором я некоторое время думал, но до сих пор не могу получить ответ.Предположим, что в doubly linkedlist есть N элементов.Сколько элементов нам нужно получить, если мы хотим получить узел в doubly linkedlist как в худшем случае, так и в среднем?

Интуитивно, я думаю, что наихудший случай - это N/2 элементов, потому что мы можем перемещаться спереди и сзади doubly linkedlist.Однако другое мнение состоит в том, что мы не знаем положение узла, поэтому мы не должны знать, в каком направлении нам следует начинать?Если это так, то худший случай - N.В этом и заключается смущение.

Я пока не знаю правильный результат, возможно, я обновлю свой вопрос на следующей неделе, потому что это один из вопросов в моем уроке.

Answer 1

На этот вопрос нет единственно правильного ответа.На самом деле это зависит от того, как реализован метод get(position).

• Если имплантация всегда пересекает список в одном направлении (вперед или назад), то наихудший случай - N шагов.

• Если имплантация проходит список с одного конца или другого в зависимости от значения позиции, то наихудший случай - N / 2 шага.

Но здесь есть одна загвоздка.Чтобы сделать это «умным» способом, реализация списка должна вести учет размера списка.Без этого он должен вычислить размер ... который включает в себя обход всего списка.

(Реализации Oracle / OpenJDK LinkedList определены как обходы с любого конца во всех версиях Java, которыеЯ посмотрел. Однако вы не сказали, говорите ли вы о стандартных реализациях.)

Средний случай также не так прост, как вы думаете.На самом деле это зависит от функции распределения позиций, которые вы ищите.Если функция распределения «плоская»;т.е. все позиции одинаково вероятны, тогда среднее количество шагов составляет половину худшего случая.В противном случае ... нет.

Answer 2

Если вам нужно проверить каждый узел, чтобы увидеть, соответствует ли он тому, что вы ищете, то наихудший случай - это N независимо от того, является ли он одиночным или двойным связанным.Независимо от того, начинаете ли вы в конце, начинаете или оба конца и работаете, вполне может оказаться, что именно тот узел, который вам нужен, является последним узлом в списке, и вы достигнете его, просмотрев все остальные узлы

Если бы у вас был английский алфавит в списке из 26 узлов, просто так получилось, что он был в порядке, вы хотели найти z и начали с самого начала, вы бы посетили 26 узлов.Точно так же, если вы хотели A и начали в конце списка, еще 26 узлов.Если бы вы хотели M и проходили внутрь с обоих концов, сначала поочередно от конца, а затем начинали, вы все равно посетили бы 26 узлов

Если x является индексом, а ваш список отслеживает количество элементов, которые он содержит, тоВы можете определить, с какого конца начинать, основываясь на том, больше или меньше x, чем N / 2.В этом сценарии наихудший случай - Раунд (n / 2), потому что для списка с нечетным числом элементов (например, список из 11 узлов) средний узел имеет 6 узлов с любого конца, а округление до 11/2 дает 6. Есливы не знаете количество узлов списка, у вас наихудший случай N (где x = количество узлов списка), и вы начинаете с заголовка списка