Data Structures and Algorithms 😍😍😍

Quick info of Data Structures and Algorithms to code these data structures

Searching Techniques

Binary Search Iterative

Binary search iterative

Binary Search Recursive

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.

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

Linear Singly Linked List operations

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

LinkedList vs Array