Naïve solutions

Unsorted array

  • 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.


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)


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