> For the complete documentation index, see [llms.txt](https://notes.danfitz.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://notes.danfitz.com/other/algo-expert/a-defining-data-structures-complexity-analysis.md).

# Defining Data Structures And Complexity Analysis

## What are Data Structures?

### The point of learning data structures

The fundamental purpose of coding interviews is to evaluate your problem-solving skills.

Data structures are simply the concepts and tools you use to solve problems better.

### Definition of data structures

At its core, all programming is just **manipulating data**: taking data from one place to another and massaging it into a format that you want along the way.

High-level, **data structures** are really just a way to organize and manage that data.

More formally, data structures can be defined by three main components:

* A collection of data values,
* The relationships among them, and
* The functions and operations that can be applied to the data.

## Complexity Analysis

### Definition of complexity analysis

In many cases, when you try to solve a problem, you'll find multiple solutions. How do you determine which is the *best* solution among them?

(This is also a common interview question. Once you solve a problem, you may be asked, "Can you do better?")

**Complexity analysis** is a means of evaluating the quality of a solution, so you can compare it to other solutions. It typically just means figuring out two metrics:

* **Time complexity**
  * How fast a solution runs
* **Space complexity**
  * How much memory a solution uses up

### Connection to data structures

Recall that data structures involve "functions and operations that can be applied to the data". *These* functions and operations have time and space complexity ramifications: they take up time and memory.

Additionally, the relationships among data values in data structures have time and space complexity ramifications too.

So, when in a coding interview, choosing a data structure becomes about

* Finding the data structure that solves the problem
* Finding the data structure that also solves it fastest and with the least memory usage