Data structures store and organize data. Operations on data structures include insert, find, remove and iterate and any application-specific operations like [[sort]]. The set of supported operations and the values stored together make up a data structure's **Abstract Data Type (ADT)**. A data structure's ADT is the simple model that a programmer needs to understand when using it, without knowing the implementation details. Each programming language implements it's own data structure library as first class objects in the language. A data structure represents the middle-ground between the physical memory of a computer and the logic of the algorithm. Efficient [[algorithm|algorithms]] rely on efficient data structures. When designing and working with data structures, it can be helpful to think about how the data structure interacts with the physical memory of your computer. For example, it's far faster to add to the end of a list than to add to beginning of a list ($\Theta(1)$ vs $\Theta(n)$ in [[asymptotic notation]]), provided the list has space to grow available at the end of the list. Storing a list in sorted order offers many advantages. ## common data structures - array: a contiguous sequence of memory - matrix: a combination of arrays. In row-major order, the matrix is stored row by row. In column-major order, the matrix is stored column by column. In block-representation, the matrix is divided into blocks and each block is stored contiguously. - stack: a set in which the first element deleted is the most recent added (LIFO). An insert operation is commonly called a `push` and a delete operation a `pop`. An [[underflow error]] occurs if `pop` is called on an empty stack. A `push` on a stack that causes it to exceed it's pre-defined size results in an [[overflow error]], or "stack overflow" (the namesake of the popular site [[Stack Overflow]]). - queue: a set in which the first element deleted is the first added (FIFO). An insert operation is commonly called an `enqueue` and a delete operation a `dequeue`. A queue has a head and a tail, with `enqueue` the element is placed at the tail and with `dequeue` the element at the head is removed. - [[heap]]: an array of keys that may be linked to other data called a **payload**. Operations include insert, delete, and minimum. Has properties min heap () and max heap (same as min heap, but reversed). handle pointer satellite data