Data Structures

Definition

A data structure is a way of organizing and storing data in a container to optimize time and memory usage for specific tasks, such as inserting, querying, or deleting elements.

Example

There are a couple of data structures that we have used before, such as:

• vector: A dynamic array that can grow or shrink.

• set: A container of unique elements that allows fast insertion, deletion, and lookup, all in \(O(\log n)\) time.

• map: A container of key-value pairs that supports fast retrieval, insertion, and deletion by key, all in \(O(\log n)\) time.

These data structures are implemented and provided by standard libraries, and we have been using them without knowing how they are implemented. In this section we’ll look at some data structutures that we’ll implement ourselves and then use in our code.