### Topic 5 - Abstract data structures [HL]

# Applications

*Evaluation of static and dynamic data structures. Comparison of different data structures given their computational complexity in Big O notation.*

Note: the big O notation and complexity of algorithms are not required by the IB syllabus, but are a common way of comparing algorithms and data structures.

## Big O notation

This chapter is about comparing different static and dynamic data structures. A useful concept for this is the big O notation which describes the complexity of an algorithm (computational/time). It helps to describe how much time an algorithm will take to solve a problem. Here we will refer to the **worst-case** scenario for each algorithm. The best way to understand the big O notation is by looking at a few examples:

- O(n) - linear time: this means that as the execution time will grow proportional to the data input size
`n`

- O(n
^{2}) - polynomial time: this means that execution time is proportional to the square of the data input size - O(2
^{n}) - exponential time: this means that execution time grows exponentially with data input size - O(log n) - logarithmic time: execution time grows in a logarithmic relationship to data input size

Big-O cheat sheet provides a good overview on different complexities and also shows a table comparing access, search, insertion and deletion complexity for different data structures.

*Figure 1: Comparison of common complexities*

## Applications

### Arrays

- when size is known
- smaller number of elements
- ordered array for better search performance and low insertion rate
- when all elements are defined at the beginning and are just changed

Examples:

- game board, e.g. battleship board
- student’s progress for a limited sized class

### Stack

- when you need elements to get first in and last out (LIFO)
- when search and traversal is not needed

Examples:

- undo/redo history: undo button pops the last element of the stack, to get back to the former state, e.g. in web browsers, word processors
- the Java Virtual Machine uses stacks to remember not finished methods of a program

### Queues

- when you need the first element to be inserted also be the first to get out (FIFO)
- when search and traversal is not needed

Examples:

- any kind of buffer, e.g. keyboard input, GUI drawer

### Linked Lists

- when you don’t know the size ahead of time
- if you don’t need random access
- if you want to insert or delete elements in the middle of the list efficiently
- where memory efficiency is needed

Examples:

- Input dependent structures, e.g. Strings
- Implementations of stacks or queues

### Binary Trees

- if you need fast search and traverse performance
- big number of elements
- ordered elements

Example:

- databases with a lot of random acess
- Binary Space Partition: 3D video game rendering