Производительность при добавлении новых элементов после существующих в LinkedList

Question

Давайте предположим, что у нас есть java.util.LinkedList, содержащий несколько сотен элементов. Одна возможность вставить новый элемент E после существующего элемента K будет:

list.add(list.indexOf(K) + 1, E);

Насколько я понимаю, этот метод имеет поведение O (k ² ), где k обозначает позицию элемента K. Сначала indexOf () пробегает список, пока не найдет K, а затем add должен проделайте ту же самую работу снова, пока она не достигнет положения k + 1. Но записи, которые должны быть изменены, могут быть легко определены после первого шага. Я думаю, что было бы не так много работы для создания метода addAfter (K, E) с поведением O (k).

Есть ли способ повысить производительность в подобном сценарии, кроме перехода на java.util.ArrayList?

Заранее спасибо.

Answer 1

Вы ошибаетесь в своем предположении, что это O (k ^ 2), просто O (2k) это O (k) (Кстати, здесь должен быть не k = индекс элемента, а размер списка, ноне имеет значения для проблемы).Но вы правы, это занимает вдвое больше времени и неэффективно.Единственный способ, которым я могу придумать, - это использовать ListIterator и найти / вставить себя (что предназначено именно для такого рода манипуляций).

Answer 2

Насколько я понимаю, у этого метода есть поведение O (k2), где k обозначает позицию элемента K. Сначала indexOf () проходит по списку, пока не находит K, а затем add не должен выполнять ту же работу снова, пока достигает положения k + 1.

На самом деле, стоимость list.add(list.indexOf(K) + 1, E) равна O(k), если list равна LinkedList.

• Вызов list.indexOf(K) включает k обход ссылок и k сравнения.

• Вызов list.add(k + 1, E) включает k + 1 обход ссылок.

Добавить их - 3 k + 1 операций; т.е. O(k).

---

Однако вы правы. Можно было бы создать альтернативную версию LinkedList с помощью метода addAfter или addBefore. Эти методы также будут O(k), но они должны быть быстрее. К сожалению, LinkedList не реализован таким образом, чтобы вы могли просто добавить эти методы (и реализовать их оптимально). Внутренние элементы LinkedList объявлены как частные, поэтому вам нужно будет начать все сначала.

---

И случайно list.add(list.indexOf(K) + 1, E) для ArrayList будет O(N), где N - длина списка. Шаг indexOf выполняет сравнение k, а шаг add включает перемещение элементов N - k. Ergo N операций и O(N)

Answer 3

Этот пример кода должен выполнить k операций:

    LinkedList<Integer> list = new LinkedList<Integer>();
    for(int i=0;i<100;i++){
        list.add(i);
    }

    Integer insert = 1001;
    Integer before = 50;
    for (ListIterator<Integer> iterator = list.listIterator(); iterator.hasNext();) {
        Integer next = iterator.next();
        if(next.equals(before)){
            iterator.add(insert);
            break;
        }
    }