2

I know this is basic but I'm not finding sources that confirms my interpretation.

The goal is to understand how arrays are stored in memory, below you will find my interpretation.

If a 4 size Array is like:

array[0] = 0

array[1] = null

array[2] = 2

array[3] = 3

Is it stored adjacently in memory without counting nulls, like this for instance?

[0], [2], [3]

if you add an element in a null position ([1]), than the next elements are pulled 1 position in memory?

[0], [1] (New), [2] (Pulled), [3] (Pulled)

References (Amoung others):

Improve this question
9
  • If you stored the array like [0], [2], [3], how would you know where the "hole" is, or that there is a "hole" at all? I suggest start by reading en.wikipedia.org/wiki/Array_data_structure and if there is anything about that which is not clear, ask about it. Commented Feb 18, 2020 at 10:01
  • It is a fixed size array with 4 positions. 3 of those positions have values but one, which is null. That would be the "hole". So my question is if all the values are stored contiguosly despite the "hole", and than when you add something in the null valued position each elements next to that position are puled back one position. this is the question. Commented Feb 18, 2020 at 10:28
  • How would you know where the hole is? Commented Feb 18, 2020 at 10:29
  • 1
    OK, so your array has a "hole", but if you store just the elements that aren't "holes", how would you know where the "hole" is? I'm not asking how you know if there is a hole or not, the question is how your memory representation can be used to work out the position of the hole. Commented Feb 18, 2020 at 10:46
  • 1
    No problem - glad I was able to help. I think this is confusing for a lot of learners nowadays because higher-level languages don't have "real" arrays (so you get used to thinking about data structures at a higher level of abstraction), and people often say "array" when what they really mean is a list (which can be represented using an array, but is not the same thing as an array). Commented Feb 19, 2020 at 11:18

2 Answers 2

Reset to default
4

A null is generally represented in memory by all the bits being zero. That is true regardless of whether the null is stored in an array or anywhere else.

I think there is some confusion in your question regarding what an array is. An array is a fixed-length sequence where every element in the sequence has the same type. The length of the array is determined when the array is created, and the length cannot change later (though you can create a new array with a different length if necessary).

The above is what you'll get from any textbook, but keep in mind that some languages like Javascript and PHP use the word "array" to mean things that are not arrays. A Javascript "array" is really a list, and a PHP "array" is really a strange hybrid between a list and an associative array. A Python list is not an array, though some sources mistakenly refer to it as one. These other data structures all allow you to insert an element at an index, but "insert an element" is not an operation on an array, because that would require increasing the length of the array by 1. The only operations on arrays are to get the value at an index, set the value at an index, and (if it's a length-prefixed array) get the array's length. You can use an array to represent a variable-length sequence, but you shouldn't confuse the array for what it represents.

There is no special treatment of null with regard to memory locations; if the array has a null at index 1, then the memory location corresponding to index 1 contains the memory representation of null. The whole point of an array is that each index corresponds with a memory location, so you can use the index to find the memory location directly. The formula for the memory address of an array element is:

(address for array[index]) = (address of array start) + index * (bytes per array element)

If the element at index 1 didn't take up a memory location, then the element at index 2 wouldn't be in the right place according to this formula.

The natural follow-up question is, if null in an array is represented in memory the same way as the number 0, how can the program tell whether the value is null or 0?

Since all the array elements have to be the same type of thing, null in an array only makes sense if the array elements are references, rather than primitive integers. For example, in Java you could have null in an Integer[] array but not an int[] array. So the zero bits representing a null would not be confused with the zero bits representing the number 0, because anyone reading an array of references is supposed to interpret the contents as references, not as integers; and anyone reading an array of primitive integers should interpret those bits as the number 0, not a null reference.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Well I think this time I was able of understanding clearly, what you mean. Elements are stored contiguously, nulls are stored in memory. thanks for the technical correctness. What doesn't make sense to me is the worst case cenario for "inserting"/"deleting" from an array to be time complexity of O(N). if changing a null element of an array would be just changing the value from memory I think we would be talking of O(1). But that's not the case its O(N). So despite your logical explanation. There are pieces of the puzzle that are not connecting.
How can the worst cenario of changing a null value of an array to be O(N), if it is just changing the values from memory, using a formula that just gives you the exact position in memory? this is a pointer for O(1) I think. However resources tells other wise. (interviewcake.com/concept/java/array?#inserting) I'm not discarding the probability of me doing a big confusion, of even the source to be faulty.
Hi @kaya3 I'm suspeting the source where I read from is wrong. as you said and as wikipedia said. you cannot insert/delete from an array. but you can from a dynamic array. and there for it looks like this guys are talking about a dynamic array, instead of an array. very strange.
So I think you are fundamentally correct, I'll search a bit more and if no further questions come up I'll mark as correct. Sorry about my confusion. I was refereing to "setting a element" as "insert an element", but that's wrong. No insert/delete possible, nulls are represented in memory. and the time complexity of setting an element is in fact O(1). Looks like the puzzle is concluded.
4

If you start with an empty array like so:

int[] intArray = new int[];
String[] stringArray = new String[];

you'll have this in you java memory (this is oversimplified): enter image description here

Both arrays get initialized with their default values (null for String because it's an object and 0 for int).

What is the default initialization of an array in Java?

Now if you try to populate the arrays:

intArray[0] = 0
intArray[2] = 2
intArray[3] = 3

stringArray[0] = "0"
stringArray[2] = "2"
stringArray[3] = "3"

you'll output in memory will become this:

enter image description here

if you add an element in a null position (1), than the next elements are pulled 1 position in memory?

No this is not true, if a index(1) has a value of null it will still populate his place in the index (see last picture see 2). Because the index(1) actually is populated with a value, only it's the default value.

Improve this answer

3 Comments

Thank you for your explanation it also fits the explanation of @kaya3. It makes sense. And probably is correct. I'm give this two answers I'm lead to think that probably the source where I was reading from was some how imprecise (Source: interviewcake.com/concept/java/array?#inserting)
@Nelssen I had a look at the source, it's indeed a little bit dubious. The inserting explained in the source (inserting by scooting over everything starting from specified index) is a characteristic of ArrayList.add(index, value) and not an array. This method will scoot over the value's starting from the specified index and only than insert the value. So this is confusing, an array in Java is pretty bare bones and ArrayList is a more fleshed out class, wrapped around an array, that will do everything explained in the article: docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
Hi @bramdc , Yeah I think they are describing a Dynamic Array. which is a very poor mistake and misinformation.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.