• Using an array means all the elements are stored contiguously (right next to each other) in memory

• If you want to add a new element to an array and it there is not a contiguous space in memory to support that, all the array must be moved to a new memory position to fit the existing plus the new element. Moving all the array is costly.

• On linked lists, the elements can be anywhere in memory. Each elements stores the address of the previous item in the list. That makes it possible to use random memory addresses, not contiguous addresses as on arrays.

• If you want to add an element to a linked list, you must add it with the address of the previous item.

• With linked lists, you don’t have to move the elements.

• Linked lists are better at INSERTS.

• Linked lists do not allow instant access to the last element on it (you have to go through all the list to get it)

• Linked lists are great if you have to read all items one at a time.

• If you need random access to elements, linked lists are not good for that.

• Arrays are good to read random elements - you can access any one of them instantly.

• Big-O notation for arrays and linked lists:

OPERATION	| ARRAYS	| LINKED LISTS
----------------------------------------------
reading		| O₍1₎		| O₍n₎
----------------------------------------------
insertion	| O₍n₎		| O₍1₎
----------------------------------------------
deletion	| O₍n₎		| O₍1₎ [*]
----------------------------------------------

[*] It is common to keep track of the first and last items on a linked list, so it would take only O₍1₎ time to delete those.

• What is better if you want to insert elements in the middle, and array or a linked list? A linked list. You only need to change what the previous element points to. With an array, you have to shift all the rest of the elements down - and if there is no space, you might have to move all elements to a new location.

• What is better if you want to delete an element, and array or a linked list? A linked list. You only need to change what the previous element points to. With an array, you have to move everything when you delete an element.

• The are 2 types of access (readings): random and sequential.

• Sequential access (reading) works reading elements one by one, starting at the first. Linked lists can only do sequential access.

• Random access (reading) works reading elements on any position. Arrays are fast at reads because of that.

• Lots of use cases require random access, so that is why arrays are used a lot.

• Linked lists are good for inserts/deletes, and arrays are good for random access.

• Binary search needs random access (you need to get to the middle of the list instantly).