A data structure (DS) is a way of organizing data so that it can be used effectively.

Complexities review

Array

Overview

An array organizes items sequentially, one after another in memory. Each position in the array has an index, starting at 0.

Strengths

Fast lookups. Retrieving the element at a given index takes O(1) time, regardless of the length of the array.
Fast appends. Adding a new element at the end of the array takes O(1) time.

Weaknesses

Fixed size. You need to specify how many elements you’re going to store in your array ahead of time. (Unless you’re using a fancy dynamic array.)
Costly inserts and deletes. You have to “scoot over” the other elements to fill in or close gaps, which takes worst-case O(n)O(n) time.

List

Untitled

Overview

A dynamic array is an array with a big improvement: automatic resizing. One limitation of arrays is that they’re fixed size, meaning you need to specify the number of elements your array will hold ahead of time. A dynamic array expands as you add more elements. So you don’t need to determine the size ahead of time.