CODEWITHSUNDEEP
javaarraysmemorylinked-list
newlogic
newlogic

Reputation: 827

How much memory is used when allocating an array vs allocating an linked list in Java?

My guess is its a 32-bit/64-bit word (depending on the CPU) per value stored in the array. So it would be array size X 32-bit/64-bit.

In the case of linked lists, it would be twice this to store the reference which points to the next element. So it would be 2 * array size X 32-bit/64-bit.

Is this correct, am I missing anything?

Upvotes: 2

Views: 4937

Answers (2)

Andrey Chaschev
Andrey Chaschev

Reputation: 16486

I made an experiment on memory consumption of arrays. Here are the results for 20000 ints arrays:

    
OS: Windows 8 6.2, amd64
JVM: Oracle Corporation Java HotSpot(TM) 64-Bit Server VM 24.0-b56

                   x |          min |          avg |          max |       stddev
       total cpu, ms |     7.000000 |     8.250000 |    10.000000 |     0.829156
bytes per LinkedList |    830.48 KB |    830.48 KB |    830.48 KB |      0.50  B
      bytes per item |     42.00  B |     42.00  B |     42.00  B |      0.00  B

       total cpu, ms |     4.000000 |     6.000000 |     7.000000 |     0.547723
 bytes per ArrayList |    416.00 KB |    416.00 KB |    416.00 KB |      0.00  B
      bytes per item |     21.00  B |     21.00  B |     21.00  B |      0.00  B

       total cpu, ms |     0.000000 |     0.950000 |     1.000000 |     0.217945
byt per TIntArrayList|    105.56 KB |    105.56 KB |    105.56 KB |      0.00  B
      bytes per item |      5.00  B |      5.00  B |      5.00  B |      0.00  B

So it's 

LinkedList:    42 bytes 
ArrayList:     21 bytes 
TIntArrayList: 5 bytes

However if the size of the array list is unknown, the resulting memory consumption due to array reallocation is:

LinkedList:    42 bytes
ArrayList:     29 bytes
TIntArrayList: 10 bytes

Upvotes: 1

Flavio
Flavio

Reputation: 11977

Much more. Each element in a linked list has:

  • Pointer to next element, pointer to previous element, pointer to item value (12 bytes) + object overhead (around another 12 bytes). Say 24 bytes.
  • Each element is not primitive but a wrapper. If every element is different, it will occupy space. For integers say another 16 bytes.

Total: 40 bytes per element.

Don't take this at face value, it's just to give you an idea. If you want precise numbers fire up a memory analysis tool (e.g. Eclipse MAT).

Upvotes: 7

Related Questions