Что квалифицируется как (медленный) доступ к внутреннему элементу LinkedList

Question

Сообщение в LinkedList гласит:

LinkedList допускает вставки или удаления в постоянное время, но только последовательный доступ к элементам. Другими словами, you can walk the list forwards or backwards, but grabbing an element in the middle занимает время, пропорциональное размеру списка.

Я не понимаю, что будет подходить для захвата элемента в середине?

В следующем фрагменте кода предполагается, что arrL представляет собой LinkedList, который содержит 50 элементов, когда счетчик j достигает 20 и программа выполняет arrL.get(20). Означает ли это, что программа захватывает элемент посередине? Также в следующей программе я просто иду вперед по списку, не так ли?

    for(int j=0;j<arrL.size();++j){
        arrL.get(j);
    }

Answer 1

Да, на каждой итерации вы просматриваете список от начала до элемента j-го , поэтому общая производительность цикла составляет n^2 (очень плохо). Это потому, что в каждой итерации у вас есть независимый get() вызов, который имеет линейную производительность.

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

for(Iterator<E> iter = arrL.iterator(); iter.hasNext();) {
  E e = iter.next();
}

или лучше:

for(E k: arrL) {
}

Кстати, это очень базовый вопрос о структуре данных, Java здесь не имеет никакого отношения ...

Answer 2

Для LinkedList get (N) занимает время, пропорциональное N. So - get (19) занимает примерно в 20 раз больше времени, чем get (0).Ваш цикл for работает за O (n ^ 2) время - n проходов, с O (n) временем за каждый проход.Если вы хотите получить доступ к членам по порядку, используйте итератор:

Iterator it = arrL.iterator();
while(it.hasNext()) {
   it.next();
}

или implicity, например, так:

for(Obj o : arrL) {
  // do something with o
}

Answer 3

@ Вики, это значит, что каждый раз, когда вы звоните arraL.get(j), эта операция занимает линейное время. Это означает, что когда вы получаете 20-й элемент, он начинается с начала (или конца, я не уверен насчет реализации) и пересекает весь список до 20-го элемента. Другая реализация ArrayList будет делать это в постоянное время (внутренне она хранит массив, поэтому вы можете думать о arrL.get(20) как array[20]), но каждый раз, когда вы удаляете элемент посередине, ему придется сдвигать элементы в массиве. В общем, ArrayList - лучший выбор, с точки зрения производительности, для случайного чтения, а LinkedList - лучший выбор, когда вы будете выполнять много удалений.

Answer 4

В связанном списке каждая запись списка знает только своего предшественника и своего преемника: они просто ссылаются друг на друга.Хорошая вещь об этом состоит в том, что этот список легко увеличивать, просто добавляя и связывая новые элементы.Но достижение элемента, который не является конечной точкой в ​​списке, требует перехода от любого конца к конкретному элементу.Следовательно, для каждого вызова get(j) требуется j посещения элемента из конечной точки в цепочке / списке.Иными словами, get(j) довольно дорого с точки зрения времени.Например, если список содержит 1000 элементов, для получения номера элемента 500 требуется 500 посещений с любого конца.Если бы список был длиной 2000 элементов, то для перехода к среднему элементу (элемент 1000) аналогичным образом потребовалось бы 1000 посещений, поскольку мы следуем за ссылками узла (цепочкой).

Напротив, доступ к любому элементу в массиве требует постояннойвремя.