How are elements stored on an array? Contiguous (next to each other) addresses in memory.

What happens when you add an element to an array and there is not a contiguos space in memory to support that? All the array must be moved to a new memory position to fit the existing elements and the new one.

How are elements stored in a linked list? The elements can be anywhere in memory. Each element stores the address of the next item in the list.

How do you add an element to a linked list? With the address of the previous item.

Do you have to move elements from memory addresses with linked lists? No.

Regarding reading, inserting and deleting… what are linked lists better at? Why? At inserting and deleting. Inserting because you don’t have to move all elements when there is no space to accomodate a new one, like with arrays. You only have to insert the element and point to the previous item. Deleting because you don’t have to change the indexes of all the previous elements, like with arrays. You just delete the element and change the pointers to the previous and next element on the linked list.

How do you access the last element of a linked list? You go through all the elements until you get to the last one (O₍n₎). Although it is a common practice to keep track of the first and last elements of a linked list (so it would take only O₍1₎ for some operations that would require access to any of them).

You are required to read all elements one at a time for a given solution. Which would be the ideal data structure for that, taking into account you may also need to insert and delete many times? Linked Lists. They are bad for random reads, but since you need to read sequentially on that situation anyway, you will gain the O₍1₎ benefit on insertion and deletion.

Regarding reading, inserting and deleting… what are arrays better at? Why? Arrays are better when you need random access to elements - because you can access any one of them instantly through their indexes. But they are bad at insertion and deletion - you may need to do move all the array when not having enough contiguous space for inserting or move all elements prior to the current one when deleting.

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.

What are the 2 types of access (readings)? Random: reading elements on any position. Sequential: reading elements one by one, starting at the first.

What type of access (random or sequential) is provided by Linked Lists? Sequential.

What type of access (random or sequential) is provided by Arrays? Random or sequential. Arrays are pretty fast at reads, specially the random ones.

Despite being potentially slow for inserting and deleting, why are arrays used so much? Because they provide random access to elements, and lots of solutions require it.

Which is best for inserts/deletes - array or linked list? Linked List.

Which is best for random access - array or linked list? Array.

You need to implement binary search (which needs instant access to the middle of the list). Which will be better, an array or linked list? An array.