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--;
        }
    }
}

标签： algorithmdata-structures

Answer 1

先取3个指针，中间，最后一个指针。那么有2种情况：

1. 如果您从第一个答案添加。您需要将中间指针移到左侧，然后移到当前位置。

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