DSA For The Rest Of Us - Part 1

Introduction to Linked Lists.

Photo by Olav Ahrens Røtne on Unsplash

Maybe you’re like me, or maybe not. You’ve been plodding along through Data Engineering life like those oxen of old who pulled those wagons across the prairie, over the never-ending rolling hills of life and software. And, truth be told, you’ve never come across the fabled DSA (Data Structure and Algorithms) so lauded by the rest of your compatriots.

Now you’re too afraid to ask.

No matter what those too smart for the rest of people on Stackoverflow and Reddit trolls might say, the obvious fact that most of us know but few will say out loud …

Unless you are a Data Engineer building the underlying complex distributed systems, the reality is you will most likely never run across the need to use DSA.

Does that mean we should not care? Of course not. If you want to live in this world and pass any interview, understand how software works, and generally become a better version of yourself, of course, you should probably learn at least something about DSA.

Thanks to Delta for sponsoring this newsletter! I personally use Delta Lake on a daily basis, and I believe this technology represents the future of Data Engineering. Check out their website below.

What’s Ahead.

This is Part 1 of what I hope is a semi-regular set of sessions where I bring you along for the ride while I teach myself some of these DSA topics. But, I want to do it somewhat differently than most of what you will find on Google.

What I mean by that is, I’m going to try to teach myself DSA like I’m 12. I don’t want a bunch of junk that muddies the water, that stuff can come later.

I’m going to attempt to cover introductory DSA topics like we are sitting on the moon looking back at earth.

With that being said, I’m going to tackle this DSA stuff in no particular order, just whatever strikes my fancy. And these will not be long-winded explanations. They will be short, to the point, and hopefully make you think “Oh, that’s what that looks like, maybe I will go Google that and learn some more about it.”

What’s a Linked List?

Photo by Kelly Sikkema on Unsplash

Since you are an astute Data Engineer and writer of much software, you’ve probably at least heard of a Linked List.

What is it, let’s ask the internet.

“A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers …”

This probably means these nodes are stored in heap memory. But, let’s keep it high level. I mean it sounds fairly simple, right? We just use lists everywhere, especially all of you Python folks, probably one of the most common data structures.

So a linked list, theoretically, would be similar (maybe not under the hood), in the sense that each item in the list would point to the next item in the line.

But, you say, what’s the practical real-world idea behind this linked list? Something that is common to anyone in manufacturing or shipping would know this as FIFO. First In, First Out.

Linked List in Rust.

So we kept that brief, now we know sorta what a Linked List is. Probably not enough to make all those Stackoverflow and Reddit trolls happy, but we are learning something! The next course of action is going to be to make a simple Linked List in Rust.

Why Rust? Because of static typing, I think writing a new DSA concept in a language you are not familiar with can help solidify the idea in your mind.

First, we are going to go back to the picture we drew above, what would we make first? How about a Node. This Node can hold a value, but more importantly, it needs to have something that points to the next Node in the list.

Simple enough, uh? Don’t worry if you don’t know Rust well, neither do I. `Option` lets me have a null, nill, none for next, and the `Box` allows me to have a recursive struct (aka the `next` will reference itself, a `Node`.

And now of course we need a LinkedList to hold all our Nodes.

Our LinkedList will hold a `head` that is, our first Node, which in turn will hold a pointer to the next Node, and so on.

So how can we string this together into a really simple Linked List?

We create 3 nodes above and give them each a value. The `next` is set to None out of the box (next is what would point to the following Node, in whatever order the list will be in.)

After that, we set, for example, node_2.next equal to node_3. The same with node_1.next, we point it to node_2. Make sense?

And print the resulting Linked List?

LinkedList { head: Some(Node { value: 1, next: Some(Node { value: 2, next: Some(Node { value: 3, next: None }) }) }) }

That my friend is my very very very simple introduction to Linked Lists.

Conclusion.

Well, we probably aren’t going to pass any FAANG or MAANG interviews with that uh? But I guess that’s not the point. The point of this DSA series is going to give us a very high level of most of the popular DSA topics, giving us at least a solid foundation to start understanding some of the concepts.

Even if we don’t use them in our daily Data Engineering life, I’m convinced at least having some idea of these concepts will make us better engineers.

Now for Spring Break, see you next week!!