Array vs. Linked List

Array is a data chunk allocated in a specific address on heap, while its start address (address of first item) is stored on stack. Items of an array are stored next to each other so they can be accessed by calculating item address by adding number of bytes to the start address (ex. 4 bytes for int) multiplied by required index.

Example:

int[] arr = new int[] {1, 2, 3};

If address of arr is 0x1000

then address of arr[1] is 0x1000 + (4 * 1) = 0x1004

On the other hand Linked List is a set of data chunks allocated using dynamic memory allocation (one by one, not like array in which all items are allocated when it is initialized). It is also stored on heap and address of first item is stored on stack. Items of linked list are not stored next to each other in memory, so they need a kind of link between its items to be accessed and not get lost in memory. In a simple linked list it is a pointer to the next item and items can be accessed by traversing from the start address (address of first item) until the required item is reached, which is slower than access mechanism of array because it fetches many addresses while in array it is just a simple calculation and one direct fetch.

Conclusion:

Array is faster than Linked List in read/access operation.

Try to think about these operations too:

– Adding an item

– Deleting an item

– Updating an item