Naïve solutions
Unsorted array
| Idea: |
|
| 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 |