# Naïve solutions

## Unsorted array

 Idea: put new items at the end of the array; when deleting, fill the gap by the last item Advantages: very simple; insert and delete is in $O(1)$ Disadvantages: find takes linear time (we have to search the whole array) Note: If we do not know the maximum size, we can use dynamic array implementation described in examples 7 a 8 in the Different notions of complexity section. Then the $O(1)$ time is in amortized sense.

Example:

## Sorted array

 Idea: keep all the items in a sorted order Advantages: we can find items in $O(\log n)$ time by binary search Disadvantages: keeping the array sorted takes time (to insert an item at the proper position, we have to move all the following items first)

Example:

## Linked list (sorted or unsorted)

 Idea: the stored items are not necessarily consecutive in memory, but each item points to the following one (and possibly also to the preceding one – a so called doubly linked list) Advantages: linked list is flexible – we can insert or delete items simply by changing pointers (no need to move other items as in the sorted array) Disadvantages: in one step, we can only move to the next (and possibly to the previous) item accessing the $k$th item takes $O(k)$ time; similarly, finding a given item may take $O(n)$ time