Data Structure

Context

Linear Data Structure

• Linked List / Doubly Linked List / Queue / Stack

Nonlinear Data Structure

• Tree / Binary Search Tree / minHeap-maxHeap

Hash Map

Graph Data Structure

• Graph Traversal DFS - BFS / Dijkstra's Algorithm

Algorithmic Concepts

• Recursion / Algorithmic Complexity

Sorting Algorithms

• Bubble Sort / Merge Sort / Quicksort

================ ================ ================

Node

• 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;
        }

---

LinkedList

|        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)     |                                   | |                                     |
|-------------------------------------------------------------------------------------------------------------|

"Runner" Technique

---

Asymptomatic Notation (Time and Space Complexity)

      ... 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);

Logarithmic Runtime O(logN): (e.g. binary search);

Linear Runtime O(N): (e.g. linear search (first part of the list preffered)

Θ(N*logN) for sorting algorithms;

Quadratic Runtime Θ(N^2): (e.g.search through a two-dimensional dataset (like a matrix) or nested loops);

Exponential Runtime Θ(2^N): (e.g. recursive algorithms);

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 ***

---

Sorting Algorithms

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

References:

Codecademy. "Pass the Technical Interview with Java" Skill Path
Simple Snippets. "Doubly Linked List Data Structure"

happy coding!