algorithm - 快速检索中间元素的数据结构

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个指针first, middle, last指针。那么有2种情况:

1. 如果你首先添加答。您需要将中间指针移动到左侧，然后移动到当前位置。

2. 如果你从最后添加答。您只需要将中间指针增加到它的下一个。