0

I'm trying to learn about the implementation of a circular queue using arrays, and currently, my main source of learning how it works is through this page.

https://www.happycoders.eu/algorithms/implement-deque-using-array/

However, I'm struggling to understand how one method in the code works, and that is the growToNewCapacity() method. I've provided the code down below.

public class ArrayDeque<E> {
        private static final int DEFAULT_INITIAL_CAPACITY = 10;
        private Object[] elements;
        private int headIndex;
        private int tailIndex;
        private int numberOfElements;

        public ArrayDeque() {
            this(DEFAULT_INITIAL_CAPACITY);
        }

        public ArrayDeque(int capacity) {
            if (capacity < 1) {
                throw new IllegalArgumentException("Capacity must be 1 or higher");
            }

            elements = new Object[capacity];
        }
    private void growToNewCapacity(int newCapacity) {
        Object[] newArray = new Object[newCapacity];
        int oldArrayLength = elements.length;
        int numberOfElementsAfterTail = oldArrayLength - tailIndex;
        System.arraycopy(elements, tailIndex, newArray, 0, numberOfElementsAfterTail);
        if (tailIndex > 0) {
            System.arraycopy(elements, 0, newArray, numberOfElementsAfterTail, tailIndex);
        }
        headIndex = 0;
        tailIndex = oldArrayLength;
        elements = newArray;
    }

I'm just completely lost after the second line of the method which states

Object[] newArray = new Object[newCapacity];
int oldArrayLength = elements.length;

Anything beyond that is completely dumbfounded for me, so can anyone please take some time off to explain what exactly is going on with the code, so that I could implement it based on my understanding later on.

Nutnicha
  • 335
  • 1
  • 10
  • system.arraycopy: https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/System.html#arraycopy(java.lang.Object,int,java.lang.Object,int,int) – xerx593 Oct 22 '22 at 07:14
  • 1
    `tailIndex`: Index of "tail" (element/node)!?, `elements.length` = "old capacity"... – xerx593 Oct 22 '22 at 07:16
  • 1
    The rest is straight forward(!?;): 1. System.arraycopy copies `numberOfElementsAfterTail` elements from `elements[tailIndex]` to `newArray[0]`. – xerx593 Oct 22 '22 at 07:22
  • 2. System.arraycopy (`if (tailIndex > 0)`! <=> "size"`>0`) copies `tailIndex` elements from `elements[0]` to `newArray[numberOfElementsAfterTail]` – xerx593 Oct 22 '22 at 07:26
  • No, `headIndex=0;...` is still "confusing", when tailIndex/size>0 – xerx593 Oct 22 '22 at 07:38
  • ..but I'd depends on how `head/tail` are treated:) – xerx593 Oct 22 '22 at 07:45
  • ..when `headIndex` should point to the first non-empty element, then `headIndex=numberOfElementsAfterTail` is correct. When it should point to the first empty/free element, then `headIndex=0;` is super. – xerx593 Oct 22 '22 at 07:47
  • thank u for ur explanation, one more thing though, can you please explain what is numberOfElementsAfterTail and what is point of having this info – Nutnicha Oct 22 '22 at 11:49
  • It is "the gap": `oldArrayLength - tailIndex` so..between (old) "capacity" and "size" .. and needed as a marker/counter/index ..in this implementation – xerx593 Oct 22 '22 at 12:07
  • Can call it "count/number of free space" in "old array". – xerx593 Oct 22 '22 at 12:09

0 Answers0