r/javahelp • u/DrBaconXD • May 28 '20
What is the difference between compile time vs run time?
So I was searching up the difference between Array and Linked List and i came across the comparison of their storage allocation. It says that:
Array- Element location is allocated during compile time.
Linked List = Element position is assigned during run time.
I'd really like to understand and know the difference between these two.
Thank you in advance!
Edit: Can someone please explain when do i use Linked List over Array/Array List? Thank you!
4
u/Satarash May 28 '20
Edit: Can someone please explain when do i use Linked List over Array/Array List? Thank you!
Array list and linked list differ in how they store the elements. Array list holds them consecutive in memory, while linked lists doesn't: instead each element has a reference to the next and previous elements. The difference is in the time required to insert a new element, accessing an element, and other such operations.
For example, inserting a new element at the end is fast for array list because the location in memory is easy to calculate (current size * number of elements), while it's slow for the linked list because the list has to call next() for each element until it reaches the last element. On the other hand, insertion at the beginning is cheap for the linked list because only a few references have to be updated, and it is costly for the array list because the new element can't just be stored anywhere in memory, it has to physically be at the beginning. So the list must allocate a new memory block, insert the new element, then move all the other elements after the new one.
You will almost always use the ArrayList, while LinkedList and array are used in special circumstances. For example, you are working with a large number of elements and it noticeably slows the application, then you might try replacing ArrayList with other alternatives and see if it helps.
source: https://docs.oracle.com/javase/tutorial/collections/implementations/list.html
2
2
u/ZeroGainZ May 28 '20
I don't believe that arrays are allocated at compile time. In Java, it depends on more than just array vs Linkedlists.
An array can be stack dynamic or heap dynamic, both of which the space is allocated at runtime.
In older languages, array creation was a compile time operation. For example, in C, creating an array can only be done using a constant, as the compiler does the allocation of memory at compile time. If you wanted an array whose length was dependent on say, a dynamic value like user input, you would use malloc or alloc to requesta block of memory from the OS, and cast it to whatever you wanted. God forbid you calculated the size incorrectly.
Make sure to read documentation about the language you're using, as mixing info cross languages can be confusing, especially with higher level languages like Java.
2
u/InYourFace555 May 28 '20
A vanilla Array requires you declared the size of Array before compiling. When the program compiles, it knows exactly the amount of memory to allocate. Any bugs such as OutOfIndex will yield during compile time. However, there is another class of Array called DynamicArray that applies for GenericTypes. DynamicArray implements a method to automatically increases size of the Array (by create a copy if I remeber correctly). This explains why some of the comments above says Array is allocated during runtime.
TL;DR: A vanilla Array like int[] does allocate resource during compile. A DynamicArray can allocate resource in runtime
2
u/NatKurien May 29 '20
The elements in an ArrayLists occupy a continuous chunk of memory, so retrieval of elements is fast. The elements in a LinkedList, however, occupy discontinuous chunks of memory, which means to say that the elements can be scattered all over the memory. Retrieving an element would require us to traverse the entire list until we find the required element we are looking for.
Inserting elements into an ArrayList causes a great deal of overhead. Consider the case where you have 10 elements in the ArrayList and you want to insert an element at position 5. This would mean that a new ArrayList of a larger size has to be created, each element of the old ArrayList has to copied into the new one while adding the new element. In the case of LinkedLists, however, all you need to do is to find the elements between which you want to insert the element. Adding the element at position 5 would mean that we would need to have element 4 point to the newly created element 5 and have element 5 point to element 6.
So if your main operation is to retrieve elements, then an ArrayList would be preferred over a LinkedList. If your main operation is to insert elements then a LinkedList would be preferred.
Hope this helps! :)
1
u/Yithar Intermediate Brewer May 28 '20
So the Java compiler compiles code into bytecode, which the Java Virtual Machine then runs.
A very good example for your question is checked exceptions. They are a compile time feature. This means the Java compiler checks that checked exceptions are either declared in a method using throws or caught. It's not a run time feature because the JVM has no notion of checked exceptions.
With an Array, you have to define a predefined size in your code. So that's even before the code is running. With LinkedList, it adds nodes as you add more elements. I've almost never used LinkedList in Java. It's more useful for something like functional programming where you break a list into the head and the tail. In general, I would prefer ArrayList over LinkedList.
1
u/frederik88917 May 28 '20
Well, the main difference between an Array and a ArrayList is the initial size allocated.
Arrays are fixed size data structures, that cannot grow so the VM knows how much size it will need beforetime.
ArrayLists are dynamic size Data Structures, you can give a starting size to it in order to improve the performance, but once you overgrow the data size, the JVM automatically doubles the size allocated, to allow you to keep managing data.
For most cases, ArrayLists are recommended over arrays, unless you know the expected size of your data. for that case, use an array for top notch performance
-1
May 28 '20
6
u/Stack_Canary May 28 '20
I mean, not very helpful to just post links and nothing else. I'm sure the guy can google, he probably wants someone to explain
-4
u/BenRayfield May 28 '20
Cuz of classloader, you can run Java, and generate every possible input output pattern, without a compiler. It is 100% runtime other than linking to DLL files etc such as to call opencl, and even opencl is 100% runtime.
13
u/tcbenkhard May 28 '20
The name already hints to it, but you write code in a .java file, then you compile this into class files (using javac, or if you are using an IDE then it will happen automatically).
java --> compile --> class --> execute
Compile time means that something is done when its being compiled. An array in your case would have to have its elements assigned when you compile the code. This means it needs to be predictable, since your code has not even executed yet. THIS IS NOT TRUE. An array can also be created, updated, filled, removed during runtime.
Runtime is when you are executing (running) your code. Think about a list that will get its values from another API or server, you dont know how many items there are before you do the actual request, so there is no way you can solve that in compile time unless you make a massive reservation of memory, which is highly inefficient.
I don't think you really need to know or think much about this, so just take this as some info as to what it is.
The difference between an array is that an array holds an index for each entry, while in a linkedlist each node holds a reference to the next object (linked together, like a chain) such as O-----O------O-----O-----O. To get to the 5th element in a linkedlist you would need to go through 1-4 before arriving at 5. To get a total of elements in a linkedlist you need to keep checking if elements have a 'next' element, and if they don't you arrived at the last element, and keep track of the count in between. Arrays just have an index.