How much extra memory is needed when calling ArrayList.add[]?
If there is enough space in the array to accommodate a new element, then no additional memory is required. Otherwise, a new array is created, 1.5 times larger than the existing one [this is true for JDK above 1.7, in earlier versions the size of the increase is different].
How much extra memory is allocated when you call LinkedList.add[]?
One new instance of the nested Node class is created.
How much memory to store one byte primitive in LinkedList?
Each LinkedList element stores a link to the previous element, the next element, and a data link.
For 32-bit systems, each link is 32 bits [4 bytes]. The object [header] of the nested Node class itself takes 8 bytes. 4 + 4 + 4 + 8 = 20 bytes, and since the size of each object in Java is a multiple of 8, so we get 24 bytes. A byte primitive occupies 1 byte of memory, but in JCF primitives are packed: a Byte object occupies 16 bytes in memory [8 bytes for the object header, 1 byte for a byte field, and 7 bytes for multiples of 8]. Let me remind you that values from -128 to 127 are cached and new objects are not created for them every time. Thus, in the x32 JVM, 24 bytes are spent storing one item in the list and 16 bytes - storing a packed Byte object. Total 40 bytes.
For a 64-bit JVM, each link takes 64 bits [8 bytes], the size of the header of each object is 16 bytes [two machine words]. The calculations are the same: 8 + 8 + 8 + 16 = 40 bytes and 24 bytes. Total 64 bytes.
How much memory to store one byte primitive in an ArrayList?
ArrayList is based on an array, for primitive data types, the value is automatically packed, so 16 bytes are spent to store the packed object and 4 bytes [8 for x64] to store a reference to this object in the data structure itself. Thus, in the x32 JVM, 4 bytes are used to store one element and 16 bytes are used to store a packed Byte object. For x64 - 8 bytes and 24 bytes, respectively.
For ArrayList or LinkedList, is the operation of adding an element in the middle [list.add[list.size[]/2, newElement]] slower?
For ArrayList:
- checking the array for capacity. If the capacity is not enough, then increasing the size of the array and copying all elements into a new array [O[N]];
- copying all elements to the right of the insertion position one position to the right [O[N]];
- element insertion [O[1]].
For LinkedList:
- find insertion position [O[N]];
- element insertion [O[1]].
In the worst case, insertion in the middle of the list is more efficient for LinkedList. In the rest, most likely, for ArrayList, since copying elements is done by calling the fast system method System.arraycopy[].
The ArrayList class implementation has the following fields: Object[] elementData, int size. Explain why you need to store size separately when you can always take elementData.length?
The size of the elementData array is the capacity of the ArrayList, which is always greater than the size variable, which is the actual number of elements stored. The capacity is automatically increased if necessary.
Read also:
- ArrayList and LinkedList in Java
- Iterator interface in Java
- Fail-fast and fail-safe behavior in Java