I am having some free time and trying to understand how ArrayDeque works internally. I've read a couple of articles and questions/answers here and I think I'm pretty close. I used debugging to follow the workflow and there is something that's bothering me. I created an empty deque which resulted in an array with 16 elements which are null. When I used addFirst it added an element on position 16 in the array and addLast added in the beggining on position 0. What am I missing, can you please share some knowledge or point me in the right direction so I can fully understand what is happening behind the curtains. Thanks in advance!
ArrayDeque operations
136 Views Asked by Ivan Mirchev At
1
There are 1 best solutions below
Related Questions in JAVA
- I need the BIRT.war that is compatible with Java 17 and Tomcat 10
- Creating global Class holder
- No method found for class java.lang.String in Kafka
- Issue edit a jtable with a pictures
- getting error when trying to launch kotlin jar file that use supabase "java.lang.NoClassDefFoundError"
- Does the && (logical AND) operator have a higher precedence than || (logical OR) operator in Java?
- Mixed color rendering in a JTable
- HTTPS configuration in Spring Boot, server returning timeout
- How to use Layout to create textfields which dont increase in size?
- Function for making the code wait in javafx
- How to create beans of the same class for multiple template parameters in Spring
- How could you print a specific String from an array with the values of an array from a double array on the same line, using iteration to print all?
- org.telegram.telegrambots.meta.exceptions.TelegramApiException: Bot token and username can't be empty
- Accessing Secret Variables in Classic Pipelines through Java app in Azure DevOps
- Postgres && statement Error in Mybatis Mapper?
Related Questions in DATA-STRUCTURES
- Why is the runtime for this O(n)?
- Purpose of last 2 while loops in the merge algorithm of merge sort sorting technique
- What is the problem in my "sumAtBis" code?
- Asking code suggestions about data structure and algorithm
- What would be the most efficient way to store multiple sets of fixed arrays (std::vector)?
- About Suffix Trees features
- Getting wrong answer in Binary Search solution
- Are there techniques to mathematically compute the amount of searching in greedy graph searching?
- AVL tree Nth largest operation - How to have all my tests pass? JAVA
- Why does the map size change?
- Complexity in Union of disjointed sets with lists
- Hash collisions in Golang map resolving
- C++ ordered map optimized with index access
- How to sort this list of strings along with the strings and output the result as expected?
- Why deleting an element in a linkedlist costs O(1)
Related Questions in DEQUE
- storing instances in an array based python deque
- Bug when sorting std::deque
- How to fix TypeError: 'int' object is not subscriptable error in deques, python
- Can iterator of `std::deque` go before its beginning
- Python: Deque Unable to load specific number of rows from bottom of csv while including the 1st row header column names
- Storing Deque Data fro class level access returns empty
- Why do mutable borrow errors disappear when refining the type of a function pointer variable
- Maximum subarray sum with at most K elements
- Two threads operate a std::deque, does below code have race condition?
- How to find the max element in a deque in java in O(1) amortized time?
- I am getting this error "Error when enabling iframe communication" when try to run accessibility script
- How to allocate an array whose elements are 'deque', through pointer in C?
- Assertion fails for collections.deque
- How to process the script just once
- How to add pointer semantics into C++ STL?
Related Questions in CIRCULAR-BUFFER
- How to implement a ring buffer safely in shared memory safely when the consumer is operating in real-time context
- Segmentation Fault with Circular Buffer Implemenation
- How to wrap around a ring buffer?
- How to wait for all Disruptor messages to be consumed in a test case
- ==284==ERROR: AddressSanitizer: stack-buffer-underflow
- mpmc ring buffer: Does a back-off improve the throughput?
- Use of volatile in circular buffers with interrupts
- Why is the circular buffer not standardized in C++?
- How to safely overwrite data in a full circular_buffer in C++
- How to speed up data imports from ring buffers in a java client?
- Ring buffers of android logcat
- Gstreamer: How to Create video directly from a buffer_list | Create Circular buffer in Gstreamer
- How to implement circular buffer using memcpy in C
- Lock-free ring buffer designs: Non-atomic + errors seen, atomic + opinions sought
- Why use the circular buffer in "overriding" mode at all?
Related Questions in ARRAYDEQUE
- storing instances in an array based python deque
- Java: How to tell if Two ArrayDeque are equal?
- How can I use ArrayDeque-like List in Java?
- Why Does ArrayDeque class doesnot provide implementation of all the abstract methods declared in deque Interface?
- How could ArrayDeque has unlimited size with an array backup
- How to send from deque and split it into two lists?
- Java Deque algorithm
- In ArrayDeque containsAll(Collection c), contains(Object o), equals(Object o) give expected but equals(Collection c) gives unexpected result
- Which queue-derived data type could facilitate the fastest algorithm to check if an string is a palindrome?
- Java ArrayDeque - offerLast & pollFirst vs offerFirst & pollLast
- Printing max element in a Deque<Integer>
- How to use ArrayDeque to set data to the RecyclerView in Android
- difference between the grow() methods in java.util.Stack and java.util.ArrayDeque
- ArrayList VS ArrayDeque in shifting elements?
- Does ArrayDeque have overhead of shifting elements on remove/add?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
An array-based deque is typically implemented using a data structure called a circular buffer. The idea is that we maintain an array of elements, but pretend that the ends of the array are glued together to form a ring.
From your debugging, it seems like the
ArrayDequeinternally maintains an array of 16 elements, which we can view like this:We maintain two different pointers, a head pointer and a tail pointer, keeping track of the position of the first element of the deque and the position one past the last element of the deque. Initially, they'll point to the start of the array:
Whenever we do an
addFirst, we back up the head pointer by one step, then write the element to the location we find. Since we're pretending that the two ends of the array are linked together, backing up one step here moves the head pointer to the last position:To do an
addLast, we write to the tail position, then advance it forward:Here's what it would look like if we did two more
addFirsts:And here's what it would look like if we did two more
addLasts:We read the elements of the deque by starting at the head pointer and proceeding forward until we reach the tail pointer. So in this case, we start reading from the slot pointed at by
head, not the first position in the array.Eventually, the two pointers will meet in the middle. When that happens, we create a brand-new array that's larger than the original one (usually, 150% bigger), then copy the elements over into the new array to free up some space.