Each data structure has its advantages when it comes to deciding which to use. One major factor is the performance of a data structure, which usually means how quickly an algorithm or operation can be performed on the data structure correctly. This is a measure of how quickly you can add a new item to a stack, or how quickly you can find an item in a linked list. The more complex the data structure is, the longer it takes to perform the algorithms. Big O notation is used to define the complexity of an algorithm. It is easier to understand by looking at examples.
An array, as you learned earlier, is a data structure that uses an index to access values. The process of simply accessing a value at position 5, for example, is only a single action. In Big O notation, this is shown as O(1), which means that the operation is done in constant time, or right away. It is the least complex.
Where the array falls short is in searching. If you wanted to search an array for a value, you would search every element in the array until it is found, or not found. This is shown as O(n), where n represents the number of elements in the array and is referred to as linear complexity. The search algorithm isn’t bad when searching through a small array, but if the array has a couple million elements, the complexity scales up by a factor of n. The important thing to understand is that the Big O of an operation describes how it scales when the number of elements grows.
The insert and delete operations are also the same as search because the array needs to be searched through to find the item to delete, or find a specific element to update.
| Array Big O | ||||
| Access | O(1) | |||
| Search | O(n) | |||
| Update | O(n) | |||
| Delete | O(n) | |||
Looking at other data structures, you see that some data structures are more or less complex for particular operations.
The stack and queue are particularly good at adding and removing elements. Accessing specific elements however is not as efficient because all elements need to be iterated through using a foreach loop.
| Stack & Queue Big O | ||||
| Access | O(n) | |||
| Search | O(n) | |||
| Push, Enqueue | O(1) | |||
| Pop, Dequeue | O(1) | |||
A linked-list has similar complexity to a stack or queue for its operations but varies in complexity if you want to add elements to the beginning or end versus in the very middle. Adding elements to the middle requires an iteration through the elements to find the location to add the element.
| Linked List Big O | ||||
| Access | O(n) | |||
| Search | O(n) | |||
| Insert/Remove at the beginning or end | O(1) | |||
| Insert/Remove in the middle | O(n) | |||
The dictionary data structure has a similar complexity to an array.
| Dictionary Big O | ||||
| Access | O(1) | |||
| Search | O(n) | |||
| Add | O(1) | |||
| Remove | O(1) | |||
The sort and search algorithms can also be labeled by complexity with big O notation. The following table shows the big O values for the different methods of sorting and searching. Sometimes an operation can have a best case and worst case when it comes to complexity. These additional variables make certain approaches better or worse as your data structure grows in size.
| Selection Sort | O(n2) | ||
| Bubble Sort | Best: O(n) Worst: O(n2) | ||
| Quick Sort | Best: O(n log(n)) Worst: O(n2) | ||
| Merge Sort | O(n log(n)) | ||
| Linear Search | O(n) | ||
| Binary Search | O(log(n)) |
When you understand how the different operation's scale in complexity with larger amounts of data, you are able to better choose which data structures and algorithms to use in your program.