Data Structures

In computer science, a data structure is a data organization, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i.e., it is an algebraic structure about data.
Data Structures is about how data can be stored in different structures. Algorithms is about how to solve different problems, often by searching through and manipulating data structures.
Primitive Data Structures are basic data structures provided by programming languages to represent single values, such as integers, floating-point numbers, characters, and booleans.
Abstract Data Structures are higher-level data structures that are built using primitive data types and provide more complex and specialized operations. Some common examples of abstract data structures include arrays, linked lists, stacks, queues, trees, and graphs.
An algorithm is a set of step-by-step instructions to solve a given problem or achieve a specific goal.
Data structures and algorithms (DSA) go hand in hand. A data structure is not worth much if you cannot search through it or manipulate it efficiently using algorithms, and the algorithms in this tutorial are not worth much without a data structure to work on.
Examples of Abstract Data Structures: Array - LinkedList - Record/Tuple - HashTables - Trees - Binary Trees - Stack
Bubble Sort is an algorithm that sorts an array from the lowest value to the highest value.
The Selection Sort algorithm finds the lowest value in an array and moves it to the front of the array.
==Arrays==
Bubble sort: Visit every element in an array, swap elements if they are not in the correct order //// O(n^2)
Selection Sort: Visit every element in array, if it doesn't match, move it forward to the "right" position //// O(n^2)
Insertion Sort: Two array. Take element from unsorted array and position it in the correct position of the sorted array //// O(n^2)
Quick Sort: array of values, chooses one of the values as the 'pivot' element, and moves the other values so that lower values are on the left of the pivot element, and higher values are on the right of it. It makes sense to choose the last element of the array, unless the final element(s) of the array are already the highest //// O(n⋅log n)
Counting Sort: Sort elements by the times they occur within the array, it makes sense if the values of the number in array are lower that the total amount of values in array //// O(n+k)
Radix sort: Sort element by right-most digit. Radix Sort must sort the elements in a stable way for the result to be sorted correctly. A stable sorting algorithm is an algorithm that keeps the order of elements with the same value before and after the sorting. Let's say we have two elements "K" and "L", where "K" comes before "L", and they both have value "3". //// O(n*k)
Merge Sort: The Merge Sort algorithm is a divide-and-conquer algorithm that sorts an array by first breaking it down into smaller arrays, and then building the array back together the correct way so that it is sorted. ///// O(n⋅log n)
Linear Search: The Linear Search algorithm searches through an array and returns the index of the value it searches for. O(n)
Binary Search: Checks middle value index of array, if it is not a match, and the value at medium index is lower than searched value, it checks the medium right portion index of the array. If medium index is higher, it checks the medium index of the left half of the array. Continue until array is found O(log n)
==LinkedList==
A Linked List is, as the word implies, a list where the nodes are linked together. Each node contains data and a pointer. The way they are linked together is that each node points to where in the memory the next node is placed.
Singly linked List -> Doubly linked list -> Circular Linked List
==Stack==
In a pile of pancakes, the pancakes are both added and removed from the top. So when removing a pancake, it will always be the last pancake you added. This way of organizing elements is called LIFO: Last In First Out.
Operations: Push, Pop, Peak, IseMpty, Size
Stack can be implemented using LinkedList and Arrays
==Queue==
A queue is a data structure that can hold many elements. The first element in line is also the first to leave. This way of organizing elements is called FIFO: First In First Out.
Operations: Enqueue, dequeue, peak, isempty, Size
==HashTable==
A Hash Table is a data structure designed to be fast to work with. The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.
In a Linked List, finding a person "Bob" takes time because we would have to go from one node to the next, checking each node, until the node with "Bob" is found. And finding "Bob" in an Array could be fast if we knew the index, but when we only know the name "Bob", we need to compare each element (like with Linked Lists), and that takes time. With a Hash Table however, finding "Bob" is done really fast because there is a way to go directly to where "Bob" is stored, using something called a hash function.
 
===HashSet===
HashSet class implements the Set interface
In HashSet, we store objects(elements or values) e.g. If we have a HashSet of string elements then it could depict a set of HashSet elements: {“Hello”, “Hi”, “Bye”, “Run”}
HashSet does not allow duplicate elements that mean you can not store duplicate values in HashSet.
HashSet permits to have a single null value.
HashSet is not synchronized which means they are not suitable for thread-safe operations until unless synchronized explicitly.[similarity]
 add contains next notes
HashSet O(1) O(1) O(h/n) h is the table 
===HashMap===
HashMap class implements the Map interface
HashMap is used for storing key & value pairs. In short, it maintains the mapping of key & value (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This is how you could represent HashMap elements if it has integer key and value of String type: e.g. {1->”Hello”, 2->”Hi”, 3->”Bye”, 4->”Run”}
HashMap does not allow duplicate keys however it allows having duplicate values.
HashMap permits single null key and any number of null values.
HashMap is not synchronized which means they are not suitable for thread-safe operations until unless synchronized explicitly.[similarity]
==Trees==
===Pre-Order Traversal===
Nodes are visited left-to right, no node is visited twice
===In-Order Traversal===
Nodes are visited left to right. If a node has no child-nodes, it goes back to the last parent node before visiting the next child node
===Post-Order Traversal===
Nodes are visited left to right. If If a node has no child node, but there's a node on the same height, that node is visited, before going back to theparent node
===Array Implementation===
index * 2 + 1 (left node)
index * 2 + 2 (right node)
===Binary Search Tree====
Left value is smaller than the node, right value is taller
===AVL Trees===
The AVL Tree is a type of Binary Search Tree named after two Soviet inventors Georgy Adelson-Velsky and Evgenii Landis who invented the AVL Tree in 1962.
Self-Balancing. If the difference between the parent node and a child node becomes two or more, it is shifted left or right
==Graph==
A vertex, also called a node, is a point or an object in the Graph, and an edge is used to connect two vertices with each other. Graphs are non-linear because the data structure allows us to have different paths to get from one vertex to another, unlike with linear data structures like Arrays or Linked Lists. Graphs are used to represent and solve problems where the data consists of objects and relationships between them, such as: Social Networks, Maps, Biology, Internet
Weighted, Directed, Connected, Cyclic, Loop
===Breadth First Search Traversal===
Visit all neighboring nodes of the current node you're visiting
===Depth First Search Traversal===
The next node visited must be a neighbouring node of the previous node visited
===Cycle===
A cycle in a Graph is a path that starts and ends at the same vertex, where no edges are repeated. It is similar to walking through a maze and ending up exactly where you started. A cycle as whole doesn't need to be cyclic, there can be sub-cycles in a graph that re cyclic. If there's at least one cyclic sub-graph, a graph is cuclic.
A vertex, also called a node, is a point or an object in the Graph, and an edge is used to connect two vertices with each other.
A weighted Graph is a Graph where the edges have values. The weight value of an edge can represent things like distance, capacity, time, or probability.
A connected Graph is when all the vertices are connected through edges somehow. A Graph that is not connected, is a Graph with isolated (disjoint) subgraphs, or single isolated vertices.
A directed Graph, also known as a digraph, is when the edges between the vertex pairs have a direction. The direction of an edge can represent things like hierarchy or flow.
A cyclic Graph is defined differently depending on whether it is directed or not:
A directed cyclic Graph is when you can follow a path along the directed edges that goes in circles. Removing the directed edge from F to G in the animation above makes the directed Graph not cyclic anymore.
An undirected cyclic Graph is when you can come back to the same vertex you started at without using the same edge more than once. The undirected Graph above is cyclic because we can start and end up in vertes C without using the same edge twice.
A loop, also called a self-loop, is an edge that begins and ends on the same vertex. A loop is a cycle that only consists of one edge. By adding the loop on vertex A in the animation above, the Graph becomes cyclic.
Union Find cycle detection finds a cycle when two nodes already belong to the same subset.
In DFS cycle detection,a cycle is detected if we come to a vertex during traversal, and that vertex has already been visited.
==Shortest PAth==
===Dijkstra Algorithm===
Find nearest node that has the shortest distant to beginning node
===Bellman Ford===
Suited if there are negative graphs