Data Structures and Algorithm Review 1/2
Array, LinkedList, Stack, Queue, and Tree
Array
The Array is a data structure where you can store data in a linear fashion. Array occupies contiguous spaces in memory. By doing so, we can access elements using indexes.
If you already know the index of the value, a read operation on Array will have O(1) time complexity. If you are searching for a value without knowing the index, you have to go from the beginning to the end in the worst case. That makes searching value to be an O(n) operation.
Adding a value to the back of an array is an O(1) operation if you know the index of the last element in the array. However, adding a value to the front of an array takes O(n), since after adding the value, all the consecutive values need to be shifted one index to the right.
Since Array is static, if it reaches its capacity while adding values to it, you need to increase its space. Developers seem to choose to use 2x of the original capacity when they need to do this. The process is making a new Array with 2x capacity and then filling it with the values from the original Array. This process takes O(n) time since it iterates through all the elements in the Array but adding an element to an Array is still amortized to be O(1) considering the ultimate number of elements can be really big.
Linked List
Linked List is also a linear data structure where you can make a node point to another. Unlike an Array, having nodes connected to another means it does not have to occupy adjacent memory cells. It also means you do not have indexes to point nodes, you need a reference to the root node and use it to iterate the entire list.
Adding a value to the head of a Linked List is O(1) operation since it is a task of switching references from an old node to a new one. Adding to the back of a LinkedList takes O(n) since you have to iterate all the way down to the back to access the node. Removing a node or searching for value goes through the same operation.
A circular Linked List is a list where the end node is connected to the root node. Useful when you need to cycle through the list continuously.
A doubly-linked Linked List is a list where each node has a reference to the previous node as well as the one after it. Having access to the previous node can make implementing the removing operations simpler.
Stack
Stack is a linear data structure following the Last-In-First-Out principle. As in a stack of plates, you can pop the top element of the stack or push a new element on top of it. Both pop and push operation happens at the same end and takes O(1) time. You can use either Array or Linked List to implement Stack.
Queue
Queue is similar to Stack but follows the First-In-First-Out principle. As in a line in front of a cashier, you can enqueue or add an element to the back and dequeue or remove an element from the front. Unlike Stack, these operations happen on the other side of the ends and takes O(1) time. You can use either Array or Linked List to implement Queue.
Tree
Tree is a hierarchical data structure that shapes like upside-down tree. A node can have multiple children and a child node can have their child nodes. Nodes are connected from top to bottom but not between siblings. Root node means the central node where the structure begins. Leaf nodes are the ones at the bottom most in the structure without their children.
Because of recurring nature of Tree, you can usually use recursion to traverse nodes in the Tree.
A node means each data point edges mean the connection among nodes.
The depth of a node is the number of edges from the node to the root node. A root node has zero depth as you would measure the depth of water from the surface.
The height of a node is the number of edges on the longest paths from the node to a leaf. A leaf node has zero height.
The height of a tree equals to the height of its root node or the depth of its deepest node.
While a general Tree has no constraints on how child nodes can be added, Binary Tree can only have up to two children. A full binary tree is a tree where every node has either zero or two children. A complete binary tree is a tree filled at every level except for the last level and all nodes on the last level are pushed as far left as much as possible. A perfect binary tree is a tree with all interior nodes with two children and leaves have the same depth (as in an ancestry chart).
Binary Search Tree is a Binary Tree with smaller child on the left and bigger child on the right, and can be used various searching purposes.
