Does indexing of an array make it random accessible?

[Arun Singh Raaj]

Does indexing make an array random-accessible or contiguous storing of elements?
If index is the reason then why LinkedList is not random accessible despite having indexes? Why only ArrayList is random accessible?

Thanks in advance.

[Jeanne Boyarsky]

Arun,
Random access means that there is fast access regardless of which index you pick. This means the algorithm is usually )(1) constant time.

Imagine you have a million elements in your list. Asking for the millionth element of an ArrayList is fast because it goes to that index. However, in a LInkedLIst, Java has to go through each element to get to the last one. Definitely not fast.

Contiguous storing of elements helps, but isn't required. If I had a HashMap of index to value, it would be fast.

[Arun Singh Raaj]

thanks for the info.
I want to know, Since ArrayList is backed by array data-structure, do ArrayList elements get stored in contiguous locations similar to array's?

[Winston Gutkowski]

Arun Singh Raaj wrote:I want to know, Since ArrayList is backed by array data-structure, do ArrayList elements get stored in contiguous locations similar to array's?

Answer: Probably. Nothing (or very little) is certain in Java.

Question: Why do you care?

The idea of any computer language is that it you trust IT to store information in the "best" way possible, be it contiguous, linked, or some form of hashmap.

That said, primitives are ... er ... primitive, so I suspect the language will try to store them contiguously if it possible can.

HIH

Winston

[Arun Singh Raaj]

Winston Gutkowski wrote:Question: Why do you care?

because I want to know why insertion is slower in ArrayList. I understand in case of arrays that to insert a new element it has to shift rest all elements because they are stored in contiguous locations but ArrayList is a dynamic array so I guessed it also stores elements in contiguous locations. please shed some light. thanks

[Jeanne Boyarsky]

Arun Singh Raaj wrote:

Winston Gutkowski wrote:Question: Why do you care?

because I want to know why insertion is slower in ArrayList. I understand in case of arrays that to insert a new element it has to shift rest all elements because they are stored in contiguous locations but ArrayList is a dynamic array so I guessed it also stores elements in contiguous locations. please shed some light. thanks

Arun,
I think Winston's point is that you can understand why it is slower without having to know how the data is sorted. If I want to insert an element at the beginning of the linked list, I just have to update two pointers. Whereas in an ArrayList, I have to update what each index refers to for all subsequent elements. This is true whether tit is stored in an array, a map or even a file mapping indexes to values.

It so happens, the data is stored in an array which you can determine from the source code. For objects, you definitely aren't guaranteed continguous memory since they are references. For primitives, I don't know without looking at the spec.

[Campbell Ritchie]

Good to see you again, Winston

The Java™ Tutorials suggest that the contents of arrays are stored in contiguous memory, but remember that the Java™ Tutorials haven't been updated since Java8, well over five years ago. As Jeanne says, that would mean that information allowing you to find the memory location of an object is stored in contiguous memory, but there is no way of knowing where that memory is, nor where all the objects are, nor whether any of those memory locations change as your program runs. In the case of primitives, you probably would have the individual values in the array. Again the memory location of that array can change as the program runs.
As you already know, arrays allow random access to their elements, and as Jeanne has told you, inserting values at the beginning or middle of an array requires all subsequent values must be moved to make space for them. Maybe you would use this method to copy all the elements into their new positions. I don't know how fast that method runs; the link doesn't say anything.
An ArrayList does use an array, because it says so in the documentation. It also tells you which methods run in constant time O(1), which in amortised constant time (Wikipedia link), and which in linear time O(n).

[Campbell Ritchie]

Winston Gutkowski wrote:. . . Why do you care? . . .

It might be interesting to know, but you can program very well without actually knowing those details.

primitives are ... er ... primitive . . .

Yes, and with the exception of booleans, the amount of memory each occupies is defined strictly by the Java® Language. It should therefore always be possible to predict how much space is needed for a primitive in an array.

[Winston Gutkowski]

Arun Singh Raaj wrote:because I want to know why insertion is slower in ArrayList. I understand in case of arrays that to insert a new element it has to shift rest all elements because they are stored in contiguous locations but ArrayList is a dynamic array so I guessed it also stores elements in contiguous locations.

I suspect it has to do with your assumption of what a "dynamic array" means, and it's certainly nothing like an awk "array".
My assumption is that it increases (and possibly decreases) in size as needed to hold all elements, but that has nothing to do with how fast it can insert an element, especially in the middle.

Winston

[Campbell Ritchie]

Winston Gutkowski wrote:. . . it increases (and possibly decreases) in size as needed to hold all elements . . .

Yes, the documentation link I posted yesterday says,

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.

...but doesn't say anything about shrinking the array, which you can do with this method.

There is a design problem about the methods to alter the List's capacity: they are not declared in the List interface.

[Arun Singh Raaj]

Jeanne Boyarsky wrote:Whereas in an ArrayList, I have to update what each index refers to for all subsequent elements. This is true whether tit is stored in an array, a map or even a file mapping indexes to values.
It so happens, the data is stored in an array which you can determine from the source code.

So this seems the answer of my question "why is insertion slower in ArrayList." The ArrayList elements are possibly stored in array.

[Arun Singh Raaj]

for(Employee e:list){  //assume list is ArrayList<Employee>
System.out.println(e);
}

As it is very much explained everywhere that ArrayList is backed by Array DS and it provides direct access to the elements so it's given priority over LinkedList when you have to access the data.
Now as per the code above, how will it access directly when I've not provided any index?
Won't it firstly search through all elements to find the index first then access it? Is ArrayList faster only if you provide index? please shed some light. Thanks.

[Campbell Ritchie]

Maybe a little look at the RandomAccess tagging interface will help. Remind yourself what sort of implementation a for‑each statement represents. Remember the for‑each statement is also called enhanced for.
What does DS mean? Data Source? Data Structure? Please avoid undefined abbreviations.

[Campbell Ritchie]

Because an array list is backed by an array supporting random access, it permits faster iteration with a for loop than using an Iterator. That means that the get() method can be used faster on an array list than any way to iterate a linked list. But “priority” isn't the correct term.

[Arun Singh Raaj]

Got it! thanks.

[Arun Singh Raaj]

Hi, what collection would you use to bundle some 100 Employee records that you retrieved from database and have to pass them to the user interface?
Where do developers perform the sorting of those records usually, at backend itself or at UI? If sorting is performed at backend then what collection is better to have in this case?

Thanks.

[Campbell Ritchie]

There is no such thing as a “better” collection or a “worse” collection. What you use depends on what you are going to do with it. The Java™ Tutorials aren't exhaustive, but they tell you what the commoner types of collection do. They don't describe stacks, nor bidirectional maps, for example.
You can sort a List in situ in Java® easily, or you can use an ORDER BY clause in your SQL; it depends which you know better, but remember that database programs are very good at such sorting.

[Arun Singh Raaj]

Hi, if ArrayList/LinkedList have 10 as default size then why does it throw IndexOutOfBoundsException when you insert some value at given index in an empty List:

List<Integer> list = new ArrayList<>();
list.add(2);
list.add(2, 44);  //it throws IndexOutOfBoundsException

[Stephan van Hulst]

Ten is not the default size. It's the default capacity. Capacity is how much elements the list can contain before it needs to grow.

[Frenkel Smeijers]

Jeanne Boyarsky wrote:Imagine you have a million elements in your list. Asking for the millionth element of an ArrayList is fast because it goes to that index. However, in a LInkedLIst, Java has to go through each element to get to the last one. Definitely not fast.

Actually, a LinkedList in Java is a doubly-linked list.

Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

source: Javadoc
So asking for the millionth element in a list of a million elements is also fast for a LinkedList, but asking for the 500,000th element is indeed slow.