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):

Nelssen
  • 1,023
  • 1
  • 17
  • 42
  • 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 https://en.wikipedia.org/wiki/Array_data_structure and if there is anything about that which is not clear, ask about it. – kaya3 Feb 18 '20 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. – Nelssen Feb 18 '20 at 10:28
  • How would you know where the hole is? – kaya3 Feb 18 '20 at 10:29
  • Thanks for the reference, I find no reference to the specific case, I've mentioned, which is a fixed sized array with some of the positions with values, and other without values, and how this case is treated in memory – Nelssen Feb 18 '20 at 10:33
  • @kaya3 there is a hole in my array because I've not filled all the positions. and my goal is to undestand how this situation is handled in memory. From what I've read it looks like this holes are not took into account, and each non-null element is stored contiguously, if you fill a non-null value than the next elements are pulled 1 position forward. – Nelssen Feb 18 '20 at 10:37
  • 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. – kaya3 Feb 18 '20 at 10:46
  • @kaya3, I think I'm learning with the discussion, but my fundamental question is how arrays are represented in memory when they have null values, and how they behave when you add an element in the middle – Nelssen Feb 18 '20 at 11:38
  • @kaya3 I understood what you mean about "how do you know where the hole is". Thanks for your help. – Nelssen Feb 19 '20 at 11:00
  • 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). – kaya3 Feb 19 '20 at 11:18

2 Answers2

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.

kaya3
  • 47,440
  • 4
  • 68
  • 97
  • 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. – Nelssen Feb 19 '20 at 10:33
  • 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. (https://www.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. – Nelssen Feb 19 '20 at 10:41
  • 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. – Nelssen Feb 19 '20 at 10:49
  • 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. – Nelssen Feb 19 '20 at 10:54
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.

bramdc
  • 580
  • 1
  • 5
  • 21
  • 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: https://www.interviewcake.com/concept/java/array?#inserting) – Nelssen Feb 19 '20 at 10:45
  • 1
    @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: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html – bramdc Feb 19 '20 at 11:30
  • 1
    Hi @bramdc , Yeah I think they are describing a Dynamic Array. which is a very poor mistake and misinformation. – Nelssen Feb 19 '20 at 11:34