int size: 4 bytes

ArrayList

ArrayDeque is almost always better than LinkedList:

• Amortised O(1) random access.
• Init with an initial capacity of 16 elements.

• Add when internal array is full, need to double the size and copy over all the data.

  • Capacity allocation goes up exponentially, does not need to copy over too much times: 2bytes^31 / 1024 / 1024 / 1024 = 2GB: only need to copy about 31 times for 2GB memory

  • for int ArrayDeque: (4bytes * 16)= 2^6 => 2^(31 - 6 + 6) = 2^(25 + 6) => only need to resize 25 times to fill 2GB

• LinkedList is better at removing the current element during iteration
• LinkedList consumes way more memory because of the storage used by their pointer
• LinkedList also suffers from cache miss

ArrayDeque remove?

Why the CPU cache is less efficient when it comes to non continuous memory arrays such as LinkedList?

• Memory locality: the CPU loads bigger blocks of memory. Sequential elements may reside in the same line, so you may fetch once and use the entire line multiple times (while in a linked list your next element is elsewhere so you don't enjoy the benefit). This benefit is reduced the bigger the elements become, and is gone once your element passes a line size.