Структура данных для быстрого поиска среднего элемента

Question

Мне нужно решить проблему, где я могу вставить влево и вправо.А затем извлекать данные из середины массива.

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

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

Вот код, с которым я уже пробовал:

private static void middleQueue(int loopLength, String[] commandsArray) {

    LinkedList<String> linkedList = new LinkedList<>();

    int counterSize = 0;

    for (int i = 0; i < commandsArray.length; i++) {
        if(commandsArray[i].equals("R")){
            linkedList.add(commandsArray[i+1]);
            i++;
            counterSize++;
        }
        else if(commandsArray[i].equals("L")){
            linkedList.addFirst(commandsArray[i+1]);
            i++;
            counterSize++;
        }
        else if(commandsArray[i].equals("E")){
            if((linkedList.size() & 1) == 0)
                System.out.println(linkedList.remove((counterSize / 2)-1));
            else
                System.out.println(linkedList.remove((counterSize / 2)));

            counterSize--;
        }
    }
}

Answer 1

Как уже отмечали другие, вам нужна структура данных с 3 указателями.

A doubly linked list будет хорошо.Но если вы будете использовать singly list list (с указателями только в одном направлении), то вы сможете либо двигаться только вправо или влево (но не оба одновременно).SLL не будет служить цели.

Смотрите это для реализации очень похожей проблемы: https://www.geeksforgeeks.org/design-a-stack-with-find-middle-operation/

Answer 2

В Java вы должны использовать два ArrayDeque s, один для первой половины списка и один для последней половины.Перемещайте элементы от одного к другому, чтобы сохранить их одинаковый размер, чтобы у вас всегда был доступ к середине.

Это будет быстрее и эффективнее, чем использование LinkedList.

Answer 3

Возьмите 3 указателя первый, средний, последний указатель.Тогда есть 2 случая:

1. , если вы добавляете из первого ответа.Вам нужно переместить средний указатель влево, а затем его текущую позицию.

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