Data Structures Overview

Time and Space Complexity Overviews

Click on a tab below to see the worst or average case time complexities for access, search, insertion, and deletion operations for common data structures. The worst case tab includes space complexity details for each data structure. The last tab includes details about the best, average, and worst case time complexities for various array sorting algorithms as well as a column with space complexity details.

It is like that, but we need to know mores. Maintaining

$O(n)$

is not fun.

Worst Case

Data Structure	Access	Search	Insertion	Deletion	Space	Remark
Array	$\perfVeryGood{O}{1}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	tbd
Stack	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfVeryGood{O}{1}$	$\perfVeryGood{O}{1}$	$\perfAverage{O}{n}$	tbd
Queue	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfVeryGood{O}{1}$	$\perfVeryGood{O}{1}$	$\perfAverage{O}{n}$	tbd
Singly-Linked List	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfVeryGood{O}{1}$	$\perfVeryGood{O}{1}$	$\perfAverage{O}{n}$	tbd
Doubly-Linked List	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfVeryGood{O}{1}$	$\perfVeryGood{O}{1}$	$\perfAverage{O}{n}$	tbd
Skip List	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfBad{O}{n\log n}$	tbd
Hash Table	$\colorbox{gray}{N/A}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	tbd
Binary Search Tree	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	tbd
Cartesian Tree	$\colorbox{gray}{N/A}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	tbd
B-Tree	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfAverage{O}{n}$	tbd
Red-Black Tree	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfAverage{O}{n}$	tbd
Splay Tree	$\colorbox{gray}{N/A}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfAverage{O}{n}$	tbd
AVL Tree	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfGood{O}{\log n}$	$\perfAverage{O}{n}$	tbd
KD Tree	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	$\perfAverage{O}{n}$	tbd

Average Case

Data Structure	Access	Search	Insertion	Deletion	Remark
Array	$\perfVeryGood{\Theta}{1}$	$\perfAverage{\Theta}{n}$	$\perfAverage{\Theta}{n}$	$\perfAverage{\Theta}{n}$	tbd
Stack	$\perfAverage{\Theta}{n}$	$\perfAverage{\Theta}{n}$	$\perfVeryGood{\Theta}{1}$	$\perfVeryGood{\Theta}{1}$	tbd
Queue	$\perfAverage{\Theta}{n}$	$\perfAverage{\Theta}{n}$	$\perfVeryGood{\Theta}{1}$	$\perfVeryGood{\Theta}{1}$	tbd
Singly-Linked List	$\perfAverage{\Theta}{n}$	$\perfAverage{\Theta}{n}$	$\perfVeryGood{\Theta}{1}$	$\perfVeryGood{\Theta}{1}$	tbd
Doubly-Linked List	$\perfAverage{\Theta}{n}$	$\perfAverage{\Theta}{n}$	$\perfVeryGood{\Theta}{1}$	$\perfVeryGood{\Theta}{1}$	tbd
Skip List	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
Hash Table	$\colorbox{gray}{N/A}$	$\perfVeryGood{\Theta}{1}$	$\perfVeryGood{\Theta}{1}$	$\perfVeryGood{\Theta}{1}$	tbd
Binary Search Tree	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
Cartesian Tree	$\colorbox{gray}{N/A}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
B-Tree	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
Red-Black Tree	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
Splay Tree	$\colorbox{gray}{N/A}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
AVL Tree	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd
KD Tree	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	$\perfGood{\Theta}{\log n}$	tbd

Array Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Remark
Quicksort	$\perfBad{\Omega}{n\log n}$	$\perfBad{\Theta}{n\log n}$	$\perfVeryBad{O}{n^2}$	$\perfGood{O}{\log n}$	tbd
Mergesort	$\perfBad{\Omega}{n\log n}$	$\perfBad{\Theta}{n\log n}$	$\perfBad{O}{n\log n}$	$\perfAverage{O}{n}$	tbd
Timsort	$\perfAverage{\Omega}{n}$	$\perfBad{\Theta}{n\log n}$	$\perfBad{O}{n\log n}$	$\perfAverage{O}{n}$	tbd
Heapsort	$\perfBad{\Omega}{n\log n}$	$\perfBad{\Theta}{n\log n}$	$\perfBad{O}{n\log n}$	$\perfVeryGood{O}{1}$	tbd
Bubble Sort	$\perfAverage{\Omega}{n}$	$\perfVeryBad{\Theta}{n^2}$	$\perfVeryBad{O}{n^2}$	$\perfVeryGood{O}{1}$	tbd
Insertion Sort	$\perfAverage{\Omega}{n}$	$\perfVeryBad{\Theta}{n^2}$	$\perfVeryBad{O}{n^2}$	$\perfVeryGood{O}{1}$	tbd
Selection Sort	$\perfVeryBad{\Omega}{n^2}$	$\perfVeryBad{\Theta}{n^2}$	$\perfVeryBad{O}{n^2}$	$\perfVeryGood{O}{1}$	tbd
Tree Sort	$\perfBad{\Omega}{n\log n}$	$\perfBad{\Theta}{n\log n}$	$\perfVeryBad{O}{n^2}$	$\perfAverage{O}{n}$	tbd
Shell Sort	$\perfBad{\Omega}{n\log n}$	$\perfVeryBad{\Theta}{(n\log n)^2}$	$\perfVeryBad{O}{(n\log n)^2}$	$\perfVeryGood{O}{1}$	tbd
Bucket Sort	$\perfVeryGood{\Omega}{n+k}$	$\perfVeryGood{\Theta}{n+k}$	$\perfVeryBad{O}{n^2}$	$\perfAverage{O}{n}$	tbd
Radix Sort	$\perfVeryGood{\Omega}{nk}$	$\perfVeryGood{\Theta}{nk}$	$\perfVeryGood{O}{nk}$	$\perfAverage{O}{n+k}$	tbd
Counting Sort	$\perfVeryGood{\Omega}{n+k}$	$\perfVeryGood{\Theta}{n+k}$	$\perfGood{O}{n+k}$	$\perfAverage{O}{k}$	tbd
Cubesort	$\perfAverage{\Omega}{n}$	$\perfBad{\Theta}{n\log n}$	$\perfBad{O}{n\log n}$	$\perfAverage{O}{n}$	tbd

What is a data structure?

It is like that, but we need to know mores. Maintaining

more footnotes

is not fun.

A data structure, as its name implies, is a way of structuring data. Since we are dealing with computers, we are ultimately talking about a way of specifically structuring data inside random-access memory (RAM). As the Wiki article notes:

In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data (i.e., it is an algebraic structure about data).