Data Structures and Algorithms

[wind juniper]

POV: You're a Computer Science student and you have to learn DSA, but all you can find is poorly-written, non-idiomatic blogs where someone strokes their "I know someone who works at Google" card.

Here's your one-stop-shop for DSA, coming from someone who is learning how to apply, create, and design these structures and algos. Throughout my ramblings here, I'll post material that I found helpful.

Everything will be implemented using TypeScript unless otherwise mentioned, because we're a primarily JavaScript-using Discord, and TypeScript allows me to demonstrate the various types.

Arrays vs. Lists

Storing data, what's the big deal?

Arrays are a fixed-size, consecutively placed grouping of data.
Think of a public bus:

• Driver (start of the bus)
• Passengers (middle of the bus)
• Caboose (end of the bus)
  The bus doesn't shrink or grow based on how many people are in it, it can fit a max of 20 people.
  There might be someone in front of you or someone behind you, or maybe not at all, but there's a possibility of someone being there.
  Arrays behave the exact same way.

const bus = ["driver", "seat", "seat", "me", "joe", "billy", "caboose"];

However, in many languages, you have to state the size of the array:

// C++
string bus[20] = { "driver", "seat", "seat", "me", "joe", "billy", "caboose" };

Now what about Lists?
Well, there's a lot of technical, super complex answers to this, but essentially a List is an array that can grow. In C++ this is called a vector, in Python it's just a list, in JavaScript/TypeScript... well... I'm sorry but const bus = [ ... ] was actually a List. Yeah.

Using Arrays/Lists

So you have passengers in the bus, now what?

Let's search to see if "joe" is in the bus, (he didn't pay his bus fare).

const bus = ["driver", "seat", "seat", "me", "joe", "billy", "caboose"];

for (let i = 0; i < bus.length; i++) {
  let passenger = bus[i];

  if (passenger === "joe") {
    return true;
  }
}

return false;

This is the simplest search there is:

1. Loop over all elements in the array
2. Compare the element's value to something you want to find
3. Return true if its found, otherwise return false once everything has been searched.

This is a called a Linear Search, and is where Big O notation comes into play.
Big O states the complexity (how hard the computer works to run the code) of an algorithm. In this case, Linear Search is O(N), where there can be a number of N people in the bus, and we check every person.

What if we want to find other people?
Let's make a function!

function findBusPassenger(busToSearch: string[], passengerToFind: string) {
  for (let i = 0; i < busToSearch.length; i++) {
    let currentPassenger = busToSearch[i];
  
    if (currentPassenger === passengerToFind) {
      return true;
    }
  }

  return false;
}

Now we can search for anyone!

const foundJoe = findBusPassenger(bus, "joe");
if (foundJoe) console.log("Joe, you need to pay your bus fare!");

const foundBilly = findBusPassenger(bus, "billy");
if (foundBilly) console.log("Billy, you need to pay your bus fare!");

But what if I want to find Joe, and find who sits before and after him?
If you know how to index, it might seem as simple as saying [joe - 1] and [joe + 1], but what if joe is the driver, or if joe is the caboose? Then we can't simply index since it would break the array.