TLACYWEN - The Last Algorithm Course You Will Ever Need
By the Primeagen, on frontend masters, for free.
These are some basic notes.
Arrays vs. Lists
In this course, when we refer to an array, we’re strictly referring to an unbroken contiguous chunk of memory of fixed size.
NOT necessarily referring to a javascript array. Think of it like Node JS’s Uint8Array, not necessarily JS’s Array.
JS’s array is a List.
So, that is to say, if we’re talking about deleting an item from an array, it means we’re setting a portion of that chunk of memory to 0.
Array has no push or pop or insertAt. We can write those on top of it, but they don’t come out of the box.
Arrays vs. LinkedList
Expanding on the previous thought, assuming an array is a contiguous chunk of memory, when would we want to use a linked list instead?
There are, in fact, real world use cases for Linked Lists!! For example, if you’re doing a fifo queue, a linked list is better. Why? Removing the first item from a linked list is a CONSTANT time operation. You don’t need to walk the list, it’s just O(1) every time, because you just need to remove the head, then reassign the head to the head.next. AKA:
item := list.head
list.head = list.head.nextThat’s pop!
If we were to do this with an array, however, we’d then have to shift every item in the array up one position — item 1 now becomes item 0, item 2 now becomes item 1, etc. and we’d have to reassign the ENTIRE array.
The advantage of using an array, however, is that it supports indexed access. You can always access an item via index in the array with O(1) constant time runtime.
So, which is better? Array or linked list?
Enter Ring Buffers. An amazing data structure. Ring buffer essentially acts as an array, but without the overhead of add/remove items in the front of the array resulting in the entire array needing to be shifted.
About binary search
- Always have a plan for the plus 1 problem. For example, in binary search, it’s CRUCIAL to remember your strategy for inclusive/exclusive.