- Linked List / Doubly Linked List / Queue / Stack
- Tree / Binary Search Tree / minHeap-maxHeap
- Graph Traversal DFS - BFS / Dijkstra's Algorithm
- Recursion / Algorithmic Complexity
- Bubble Sort / Merge Sort / Quicksort
================ ================ ================
- a basic data structure which contain data and one or more links to other nodes
- can be used to represent a linear structure - LinkedList / nonlinear structure - Tree
- "orphaned" nodes - a2 and a5 as no links pointing to them
path: src/LinearDataStructure/Node.java
where a Node class was created adding getters and setters:
public class Node {
public String data;
private Node next;
private Node previous;
public Node(String data) {
this.data = data;
this.next = null;
}
| Singly LinkedList | Doubly LinkedList | | ArrayList |
|---------------------------------|-----------------------------------| |-------------------------------------|
| public void addToHead(data) {} | public void addToHead(data) {}* | | |
| public void addToTail(data) {} | public void addToTail(data) {}* | | |
|---------------------------------|-----------------------------------| |-------------------------------------|
| public String removeHead() {} | public String removeHead() {}* | | |
| did not apply | public String removeTail() {} | | |
|---------------------------------|-----------------------------------| |-------------------------------------|
| did not apply | public Node removeByData(data) {} | | public int[] removeByData(data) {} |
|---------------------------------|-----------------------------------| |-------------------------------------|
| public void printList() {} | | public void printList() {}* |
-------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------
| | + interface Deque methods: | | |
|---------------------------------------------------------------------| |-------------------------------------|
| | .getFirst(); / .getLast(); | | |
| | | | |
| | .peekFirst(); / .peekLast(); | | |
-------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------
| <<< Swapping Elements >>> |
| ------------------------------------------------------------------------------------------------------------|
| linear (sequential) search | | | binary search |
| ------------------------------------------------------------------------------------------------------------|
| while (node1 != null) { | | | |
| if (node1.data == data1) { | | | |
| break; | | | |
| } | | | |
| node1Prev = node1; | | | |
| node1 = node1.getNextNode(); | | | |
| } | | | |
| ------------------------------------------------------------------------------------------------------------|
| <<< Big O Notation >>> |
| ------------------------------------------------------------------------------------------------------------|
| Time Complexity: O(N) | | | Time Complexity: O(logN) |
| (head/tail): O(1) | | | |
| Space Complexity: O(1) | | | |
|-------------------------------------------------------------------------------------------------------------|
... is a general way of describing the function's runtime based on the input
Adding Runime (when we neglect costants and focus on a dominant term)
Thus, Θ(N) + Θ(N*logN) = Θ(N)
... the most efficient
Constatnt Runtime Θ(1): highly efficient as the algorithm is not influenced by the data unput (e.g. the program use only constants or print the same String);
Quadratic Runtime Θ(N^2): (e.g.search through a two-dimensional dataset (like a matrix) or nested loops);
Factorial Runtime Θ(N!): to generate all possible ways of arranging ittems in differentt order (aka permutation)
... the least efficient
*** Big Omega (Ω) for the best case *** Big O (O) for the worst case *** Big Theta (Θ) for onle case scenario ***
DFS Depth-First Search moves forward every time visiting a new vertex (employs a Stack or Recursion)
[ is useful for determining whether a path exists between two points - find out if the solution exists for a maze ]
BFS Breadth-First Search visits every conection before moving forward (by using a Queue)
[ is helpful in finding the shortest path between two points - useful for map navigation (GPS system) tools because it helps determine the shortest path between two vertices ]
Traversal Methods:
PRE-Order Traversal: start at the ROOT node + DFS (e.g. to create a copy of the tree or graph)
visit current node, left subtree, right subtree
POST-Order Traversal: start at the ROOT node but visit children before their parent (e.g. to delete the tree or graph)
traverse left subtree, right subtree, visit current node
Reverse POST-Order Traversal
visit current node, traverse right subtree in reverse post-order, traverse left subtree in reverse post-order
RUNTIME: O(E + V)
Dijkstra's Algorithm:
- to find all of the shortest distances between a start vertex and the rest of the vertices in a graph
RUNTIME: 0((E + V) logV) (in the worst case... (V+E)loop iterations x (logV) to update minHeap each iteration) Dijkstra’s Algorithm does not work with negative edge weights
Codecademy. "Pass the Technical Interview with Java" Skill Path
Simple Snippets. "Doubly Linked List Data Structure"
happy coding!