Блог

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

 for(int i = 0; i <= numOfElements/2; i  ){
element = element.next;
}
  

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

Особенность связанного (или двусвязно связанного) списка в том, что произвольный доступ выполняется медленно ( O(n) ).

Вам нужно использовать другой вид списка, такой как список пропусков.

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

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

Я не уверен, что это будет иметь большой смысл, это зависит от причины, по которой вам нужен двусвязный список. В идеале вы могли бы просто отказаться от его использования. Но если это невозможно, вы могли бы подкрепить это другим типом структуры данных, таким как hashmap с целым числом в качестве ключа. Тогда вы могли бы сделать что-то вроде:

 element.get(numOfElements/2);
  

Когда вы говорите «перейти к середине», вы имеете в виду буквально точный средний элемент каждый раз? Или просто «где-то еще, кроме начала или конца, но точное место будет отличаться»?

Если вы имеете в виду точную середину, вы могли бы сохранить указатель на середину списка вместе с обычными начальным и конечным указателями. Каждый раз, когда запись добавляется в список или удаляется из него, существует вероятность того, что этот указатель придется переместить. Обратите внимание, что потребовалось бы две вставки с каждой стороны, чтобы переместить его на одну позицию, и одна вставка ниже и одна выше аннулировали бы. Поэтому вам пришлось бы сохранить «половинный счетчик». Когда элемент вставлен ниже, вычтите единицу из половины счетчика. Когда элемент вставлен выше, добавьте его. Если значение половины счетчика теперь равно -2, переместите средний указатель вниз на один слот и сбросьте значение половины счетчика на 0. Если значение половины счетчика теперь равно 2, переместите средний указатель вверх на один слот и сбросьте значение половины счетчика. Я делал это однажды много лет назад. Я забыл почему.

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

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

Помогает ли что-либо из этого с проблемой, которую вы действительно пытаетесь решить, я не могу сказать без дополнительной информации.

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

или сохраните 2 отдельных списка и каждый раз, когда вы обращаетесь к середине, вы корректируете их, пока они не станут одинаковой длины (сохраняйте длину как отдельный параметр для каждого)

 public class DoubledLickedList{
    private Node fhead,ftail,shead,stail;
    private AtomicInteger fsize,sSize;

    public Class Node{
        private Node next;
        private Node prev;
        public Node getNext(){
            if(next==null amp;amp; next==ftail)return shead;
            return next;
        }

        public Node getPrev(){
            if(prev==null amp;amp; prev==shead)return ftail;
            return prev;
        }
    }

    public Node getMiddle(){
        adjustToMiddle();
        return ftail;
    }

    private void adjustToMiddle(){
        while(fsize.get()>sSize.get() 1){
            //pop first and push it to the second
            fsize.incrementAndGet();
            sSize.decrementAndGet();
        }
        while(sSize.get()>fsize.get() 1){
            //pop second and push it to the first
            sSize.incrementAndGet();
            fsize.decrementAndGet();
        }
    }

 }
  

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

У всех гораздо более быстрый произвольный доступ.