Linear Data Structures

Insert O(n), which means the cost of copying these items into the new array increases linearly and in direct proportion to the size of the array. Now let’s talk about removing an item. If you want to remove the last item, that’s pretty easy. We can quickly look it up by its index and clear the memory. So here we have Delete O(1), which is our best case scenario.

But when doing big O analysis, we should think about the worst case scenario. What is the worst case scenario here? This is when we want to remove an item from the beginning of the array. We have to shift all the items on the right one step to the left to fill in the hole. The more items we have, the more this shifting operation is going to cost. So for the worst case scenario, deletion is an all off and operation.

So because arrays have a fixed size in situations where we don’t know ahead of time how many items we want to store in them or when we need to add or remove a lot of items form them, they don’t perform well. In those cases we use LinkedLists.