0

Arrays are stored in a linear fashion, with memory cells of fixed size for each element. To have fixed sized memory cells Arrays should be homogenious. So in Arrays we get an Nth element by skipping certain amount of bits (defined by element type) N times.

But what about lists? Or heterogenious arrays like we have in JavaScript? How are they stored in memory. And how does accessing a certain element work with lists?

1
  • Your question is unclear: are you asking about (linked) lists, heterogenous arrays, or JavaScript arrays? And if you are asking about JavaScript arrays, which of the dozens of implementations are you asking about? Dec 29, 2022 at 19:48

3 Answers 3

2

How are they stored in memory.

In general, this is not something which is defined by a language specification. A specific implementation of a language is free to store something in memory however it likes so long as that implementation is consistent with the behaviour defined by the language specification.

That said, the answer for JavaScript is mostly "everything is a reference" - the object itself is not stored in the array or list, but a pointer to the actual object, and that pointer is of constant size independent of the type of object it is pointing to.

For the other end of the scale, look at something like C: there, arrays do contain the object directly, and can therefore only contain objects of one specific type.

3
  • let's say I have a heterogenious array in JavaScript const arr = [21, "summer", true, null]. The array itself is an object. But how are the elements of the array are stored in the memory? They all are primitive but have different sizes since they are of different types.
    – forty5
    Dec 29, 2022 at 18:22
  • 2
    They will likely be boxed. But again, implementation dependent. Dec 29, 2022 at 18:55
  • There’s the “Any” protocol in Swift which can be anything.
    – gnasher729
    Dec 29, 2022 at 20:24
2

Disclaimer: I did not look up JavaScript's implementation

For your example of const arr = [21, "summer", true, null] my guess, as Philip Kendall also pointed out, is that it's likely stored in memory as references to your data.

If it stores each piece of your data in memory at it's own location:

memory location a -> (Integer) 21
memory location b -> (String) "summer"
memory location c -> (Boolean) true
memory location d -> (Object) null

then your array can just hold consistent length references that point to each piece of data:

memory location e -> (Array) [reference a, reference b, reference c, reference d]
1
  • 1
    You might also have a tagged-pointer optimization to store small immediate values like null, undefined, booleans, and small integers directly inline without needing heap allocation en.wikipedia.org/wiki/Tagged_pointer
    – Alexander
    Dec 29, 2022 at 19:45
-1

In languages with arrays supporting multiple types of elements usually what is stored is pointers, object references and so on, which all have the same size, so the problem goes away.

“Lists” are implemented any way the implementation likes. I’d probably use an array or a list of arrays as the underlying structure because I don’t like lots of little allocations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.