Блог

У меня есть немного свободного времени, и я пытаюсь понять, как ArrayDeque работает внутри. Я прочитал пару статей и вопросов / ответов здесь, и я думаю, что я довольно близок. Я использовал отладку, чтобы следить за рабочим процессом, и есть кое-что, что меня беспокоит. Я создал пустой deque, в результате чего получился массив с 16 элементами, которые являются нулевыми. Когда я использовал addFirst, он добавил элемент в позицию 16 в массиве, а addLast был добавлен в начале в позицию 0. Чего мне не хватает, не могли бы вы поделиться некоторыми знаниями или указать мне правильное направление, чтобы я мог полностью понять, что происходит за кулисами. Заранее спасибо!

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

Из вашей отладки кажется ArrayDeque , что внутри поддерживается массив из 16 элементов, который мы можем просмотреть следующим образом:

  --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
  

Мы поддерживаем два разных указателя, указатель head и указатель tail, отслеживая положение первого элемента deque и положение после последнего элемента deque. Первоначально они будут указывать на начало массива:

  head
  |
  v
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
  ^
  |
 tail
  

Всякий раз, когда мы выполняем an addFirst , мы создаем резервную копию головного указателя на один шаг, а затем записываем элемент в найденное местоположение. Поскольку мы притворяемся, что два конца массива связаны друг с другом, резервное копирование на один шаг здесь перемещает указатель заголовка в последнюю позицию:

                                                              head
                                                              |
                                                              v
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
  ^
  |
 tail
  

Чтобы выполнить addLast , мы записываем в конечную позицию, затем продвигаем ее вперед:

                                                              head
                                                              |
                                                              v
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
| X |   |   |   |   |   |   |   |   |   |   |   |   |   |   | X |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
      ^
      |
     tail
  

Вот как это выглядело бы, если бы мы сделали еще два addFirst s:

                                                      head
                                                      |
                                                      v
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
| X |   |   |   |   |   |   |   |   |   |   |   |   | X | X | X |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
      ^
      |
     tail
  

И вот как это выглядело бы, если бы мы сделали еще два addLast s:

                                                      head
                                                      |
                                                      v
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
| X | X | X |   |   |   |   |   |   |   |   |   |   | X | X | X |
 --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- 
              ^
              |
             tail
  

Мы считываем элементы deque, начиная с указателя head и продвигаясь вперед, пока не дойдем до указателя tail. Итак, в этом случае мы начинаем чтение из слота, на который указывает by head , а не с первой позиции в массиве.

В конце концов, два указателя встретятся посередине. Когда это происходит, мы создаем совершенно новый массив, который больше исходного (обычно на 150% больше), затем копируем элементы в новый массив, чтобы освободить немного места.