data structures

arrays

arrays are contiguously allocated structures. each element has an address and could be easily searched.

time complexity of inserts on dynamic arrays

linked lists

linked lists are isolated pieces of memory connected through pointers.

arrays vs linked lists

linked list advantages:

• overflows if there is actually no memory left.
• moving pointers is more efficient than moving a large number of things.
• insertion and deletion are simpler compared to arrays.

array advantages:

• more efficient random element access.
• better memory locality.
• space efficient - doesn't need to store pointer info.

containers

containers are data structures where you could store and get data without knowing the content. examples of this are stacks and queues.

stacks

containers that support getting data through last-in-first-out. api has push(), pop(), peek().

queues

containers that support getting data through first-in-first-out. api has enqueue(), dequeue(), peek().

dictionaries

dictionaries allow accessing items by content. this is used to store key, value pairs. api has insert(), search(), and delete(). some implementations suport max() or min() and predecessor() or successor().

binary search trees

these are linked lists with two pointers for the left and right children. a node could also optionally have a parent pointer. the children are arranged in a specific order - the current node's value is greater than the value of the left child and smaller than the value of the right child. api has insert(), search(), min(), and max().