# Data Structures and Algorithms 😍😍😍 ## Searching Techniques ### Binary Search Iterative {% embed url="" %} Binary search iterative {% endembed %} ### Binary Search Recursive {% embed url="" %} ## Sorting Techniques ### 1. Quick Sort / Partition Sort #### Partition procedure * Select the pivot element which is the first element of the array * Mark first element as `'i'` and the last element as `'j'` * Increment `i` if `arr[i] <= pivot` * Decrement `j` if `arr[j] > pivot` * After incrementing `i` and decrementing j as per the last two steps, swap arr\[i] and arr\[j] * Once `i` crosses `j`, in other words, if `j>i` then swap `arr[j] with pivot` and return j Now, after the partition procedure, we'll get two parts, the left partitioned and the right partitioned part. Perform quick sort recursively on both these parts. ```javascript const arr = [50, 70, 60, 90, 40, 80, 10, 20, 30]; const swap = (indexOne, indexTwo) => { // ES6 way -> array destructuring [arr[indexOne], arr[indexTwo]] = [arr[indexTwo], arr[indexOne]] /* The above line is same as doing const temp = arr[indexTwo] arr[indexTwo] = arr[indexOne] arr[indexOne] = temp */ } function partition(arr, low, high) { const pp = arr[low] let i = low, j = high while (j > i) { do { i++ } while (arr[i] <= pp) while (arr[j] > pp) { j-- } if (j > i) { swap(i, j) } } swap(low, j) return j } function quickSort(arr, low, high) { if (low < high) { const pp = partition(arr, low, high) quickSort(arr, 0, pp) quickSort(arr, pp + 1, high) } } const qs = quickSort(arr, 0, arr.length - 1) console.log(arr) //[ 10, 20, 30, 40, 50, 60, 70, 80, 90 ] ``` #### Time-complexity of quicksort * If the list is sorted in ascending or descending order then the list is traversed 1+2+3+4...+n so it'**`n^2`** * The worst case is therefore **`n^2`** * The best case happens when `j` appears at the center of the list. In this case, it will be **`nlogn`** ### 2. Bubble Sort ### 3. Selection Sort ### 4. Merge Sort ### 5. Count Sort ### 6. Radix Sort ### 7. Bin / Bucket Sort ### 8. Shell Sort ## Linked List ### Operations 1. Display linked list 2. Insert an element at first place (head) 3. Insert an element at last place 4. Insert an element at any place (index) 5. Get the element at an index 6. Delete an element 7. Delete all elements 8. Reverse linked list (2 ways -> copy to array and back, reverse links) 9. Concatenate two linked lists 10. Merge two linked lists {% tabs %} {% tab title="Linear Singly Linked List operations" %} ```javascript // Create Node class Node { constructor(element, nextNode) { this.element = element; this.nextNode = nextNode } } // Create LinkedList class LinkedList { constructor() { this.head = null; this.size = 0 } // insertAtHead insertAtHead(element) { // create a node // point this to head node -> next node of new node should be current head node const newHeadNode = new Node(element, this.head) this.head = newHeadNode this.size++ } // printList -> prints all elements printList() { let currentNode = this.head while (currentNode) { console.log(currentNode.element) currentNode = currentNode.nextNode } } // get At getAt(index) { // check of index is proper if (index > this.size && index < 0) { return null } let currentIndex = 0 let currentNode = this.head while (currentIndex <= index) { if (currentIndex === index) { return currentNode?.element || null } currentNode = currentNode.nextNode currentIndex++ } } // get All in an array getAll() { const linkedListArray = [] let currentNode = this.head while (currentNode) { linkedListArray.push(currentNode.element) currentNode = currentNode.nextNode } return linkedListArray } // insertAtTail insertAtTail(element) { const tailNode = new Node(element, null); let currentNode = this.head if (!currentNode) { this.head = tailNode return } while (currentNode) { console.log(currentNode) if (!currentNode.nextNode) { currentNode.nextNode = tailNode return } currentNode = currentNode.nextNode } } // insertAtIndex insertAtIndex(index, element) { if (index >= this.size || index < 0) return let currentIndex = 0 let previousNode = this.head let currentNode = this.head while (currentIndex <= index) { if (currentIndex === index) { if (index === 0) { // this.head = new Node(element, this.head) this.insertAtHead(element) return } previousNode.nextNode = new Node(element, currentNode) return } previousNode = currentNode currentNode = currentNode.nextNode currentIndex++ } } // removeFirst removeFirst() { this.head = this.head.nextNode } // removeLast removeLast() { let currentNode = this.head let previousNode = this.head while (currentNode) { if (!currentNode.nextNode) { previousNode.nextNode = null return } previousNode = currentNode currentNode = currentNode.nextNode } } // removeAtIndex removeAt(index) { if (index > this.size) { return } let currentIndex = 0 let currentNode = this.head let previousNode = this.head while (currentNode) { if (index === currentIndex) { //remove element if (index === 0) { this.head = currentNode.nextNode return } previousNode.nextNode = currentNode.nextNode return } previousNode = currentNode currentNode = currentNode.nextNode currentIndex++ } } // removeAll removeAll() { this.head = null } // concatenate / join two lists static concatLists(l1, l2) { let newLL = new LinkedList() let currentL1Node = l1.head let currentL2Node = l2.head while (currentL1Node) { newLL.insertAtHead(currentL1Node.element) if (!currentL1Node.nextNode) break currentL1Node = currentL1Node.nextNode } while (currentL2Node) { newLL.insertAtHead(currentL2Node.element) if (!currentL2Node.nextNode) break currentL2Node = currentL2Node.nextNode } return newLL.getAll() } // merge two lists static mergeSortedLists(l1, l2) { let firstNode = l1.head let secondNode = l2.head let thirdNode = null let lastNode = null // initially check which head is small and get the third and fourth on that head if (firstNode.element < secondNode.element) { thirdNode = lastNode = firstNode firstNode = firstNode.nextNode lastNode.nextNode = null } else { thirdNode = lastNode = secondNode secondNode = secondNode.nextNode lastNode.nextNode = null } while (firstNode && secondNode) { if (firstNode.element < secondNode.element) { lastNode.nextNode = firstNode lastNode = firstNode firstNode = firstNode.nextNode lastNode.nextNode = null } else { lastNode.nextNode = secondNode lastNode = secondNode secondNode = secondNode.nextNode lastNode.nextNode = null } } if (firstNode) { lastNode.nextNode = firstNode } else if (secondNode) { lastNode.nextNode = secondNode } while (thirdNode) { console.log(thirdNode.element) thirdNode = thirdNode?.nextNode } console.log(l1) console.log(l2) } } let ll = new LinkedList() ll.insertAtHead(70) ll.insertAtHead(30) ll.insertAtHead(10) // ll.removeAt(3) // ll.removeFirst() // ll.removeLast() // ll.removeAll() // console.log(ll.getAt(1)) // console.log(ll.getAll()) let l2 = new LinkedList() l2.insertAtHead(3000) l2.insertAtHead(2000) l2.insertAtHead(1000) // const arr = LinkedList.concatLists(ll, l2) // console.log(arr) LinkedList.mergeSortedLists(ll, l2) ``` {% endtab %} {% endtabs %} ## LinkedList vs Array ![](https://1944679227-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MVEiPUp08kYt33g51v7%2F-McelhcA9Tb0NP2-56hp%2F-Mcet9DWVeEJArtrXJNq%2Fimage.png?alt=media\&token=7c0e3f75-f6fe-45f8-9e49-0541d50fbc25)