A node is an abstract data type with two things. First, a node stores data. Second, a node stores pointers to other nodes. A graph is any collection of nodes and their pointers to other nodes. The nodes of a graph are also called vertices, and the pointers that connect them are called edges. The start of a linked list was called the head. The start of a binary tree is called the root....
The main advantage of a linked list is that you can add and remove elements at any position in $O(1)$. The caveat is that you need to have a reference to a node at the position in which you want to perform the addition/removal, otherwise the operation is $O(n)$, because you will need to iterate starting from the head until you get to the desired position. A normal (dynamic) array requires $O(n)$ for adding and removing from an arbitrary position....
A hash map is an unordered data structure that stores key-value pairs. A hash map can add and remove elements in $O(1)$, as well as update values associated with a key and check if a key exists, also in $O(1)$. The biggest disadvantage of hash maps is that for smaller input sizes, they can be slower due to overhead. Because big O ignores constants, the $O(1)$ time complexity can sometimes be deceiving - it’s usually something more like $O(10)$ because every key needs to go through the hash function, and there can also be collisions....
Technically, an array can’t be resized. A dynamic array, or list, can be. In the context of algorithm problems, usually when people talk about arrays, they are referring to dynamic arrays. Given an array, a subarray is a contiguous section of the array. All the elements must be adjacent to each other in the original array and in their original order. A subarray or substring is a contiguous section of an array or string....
Monotonic: (of a function or quantity) varying in such a way that it either never decreases or never increases. A monotonic stack or queue is one whose elements are always sorted. It can be sorted either ascending or descending. Monotonic stacks and queues maintain their sorted property by removing elements that would violate the property before adding new elements. By maintaining the sorted property, the search space is reduced. Pseudocode for maintaining a monotonic increasing stack over an input array:...