Every Programmer Should Understand This

I have worked with a large variety of programmers. Some were what the industry call “junior” developers (beginners) and some were “senior” developers (experts). While working with these people I started to notice that the better programmers (not necessarily the seniors) seemed to understand certain concepts much better than others.

Surprisingly, this knowledge didn’t have a direct correlation with the “level” of experience that the developer possessed. Some junior developers understood these topics better than their senior counterparts. However, some junior developers were completely oblivious to the subject matter at all. This subject matter doesn’t seem to be something that is learned on the job so much until you begin to work on more complicated systems, however, the benefits of understanding these concepts pay off greatly when developing any piece of software and should thereby be understood as fundamental knowledge for any competent programmer.

It might surprise everyone reading this to find out that the topics and subjects I am referring to are computer science basics. In fact, most of them are covered in the early stages of the computer science curriculum.

Why is this?? Why don’t some of the most “senior” developers at some companies not understand the basics?

I’m sure everyone has their theories, but I attribute it to more and more people learning to program by unconventional ways such as boot camps, websites that teach you how to code (like code academy), and people just teaching themselves how to code an application and get it up an running.

There is nothing at all wrong with learning like this (I’ve learned many subjects this way), but please realize that after completing a boot camp or code academy course, on say JavaScript, there is still A LOT more to be learned. I believe some people fall into a false sense of security thinking that they have all the tools they need to code anything and everything, but then end up failing miserably at a project that takes a much deeper understanding of computer science.

Developers need to understand data structures, algorithm development, and topics such as recursion. These are the building blocks of computer science! These aren’t as “fun” for your average new programmer that just wants to type  alert(“Hello World”) into a script and see the console print his statement. No, these are more fun when you actually have difficult problems to be solved and need an efficient and elegant solution to do the job.

Strangely, the same “senior” developers that are not familiar with these general fundamental topics are for some reason well versed in specialized topics such as the idiosyncratic behavior of a certain compiler for a certain language or the details of a certain system methods that may produce better timings in certain situations.

While the latter may be important to know and understand in certain situations (and I’m not implying that these people are not very useful), you can’t neglect the fundamentals. I believe a basic understanding of data structures and algorithms is crucial before you start using the .Sort() function in your language of choice or any other basic algorithm that is implemented for you by the API. I'm not saying that you have to be able to write library efficient code, but to be completely oblivious to what is happening can only result in using the wrong functions at the wrong times.

It may sound harsh, but a programmer that builds applications and doesn't understand how they work is, in my eyes, like a surgeon that doesn't understand basic biology. Will he/she have to understand how the mitochondria's job is to be able to produce the energy currency of the cell, ATP (i.e., phosphorylation of ADP), through respiration, and to regulate cellular metabolism on a day to day basis? No, probably not. However, if he is my surgeon, you can bet your ass I am hoping he knows these things. I feel the same way about a programmer and understanding computer science basics.

If you are programming by coincidence, then you aren’t sure why your code works the way it does, and more importantly you won’t understand why it doesn’t work. 

If you still aren’t sure what I’m talking about then here is a test. Can you reverse a singly linked list?

Proving that you can do this will mean that you at least understand the basics of computer science. To successfully develop an algorithm to do this you will need to understand pointers, recursion or iteration, and algorithm development. Like I’ve stated earlier, all of these are subject covered in computer science 101.

A linked list is probably the most basic data structure in computer science and is the main building block that other data structures consist of. Knowing this you should be able to develop an algorithm that, given the head node, will return the reversed node.

Test yourself. See if you can implement an efficient algorithm. Then check out my solution. Was it like yours?

The Idea behind Reversing a Singly Linked List

The idea is to iterate through the complete linked list and maintain three pointers as listed below:

• Pointer to the head of unreversed list headOfUnReversedLL.
• Pointer to the head of reversed list headOfReversedLL.
• Pointer to the node to be reversed nodeToReverse.

In each iteration we follow the below steps:

1. The headOfReversedLL pointer must point to the nodeToReverse. Initially the node to reverse is null, so the head of reversed linked list will point to null.
2. The nodeToReverse pointer should point to the head of the unreversed list as we are trying to reverse that particular node.
3. The headOfUnReversedLL pointer should move one step forward in the unreversed linked list.

The next pointer of nodeToReverse node should point to the head of the reversed linked list.

We repeat the above four steps until the headOfUnReversedLL points to null. 

Here is a pictorial representation of the iteration. Each row represents the state of the linked list after one iteration:

So, if we observe closely, the first step is actually the finalizing step of the iteration. That is the step which correctly positions the headOfReversedLL to the node which was reversed in the last iteration.

But, when the loop exits out, we never get a chance to do that one last time. So at the end, let us re-position the headOfReversedLL to the correct node nodeToReverse

Source Code – Reversing a Singly Linked List

Analysis – Reversing a Singly Linked List

Running Time

We just run through the linked list once and hence the time complexity is O(N) where N is the size of the linked list.

Space Complexity

We use just three pointers and the amount of pointers is not dependent on the size of the linked list, its O(1). Hence, we can say that the space used is constant.

If you were able to come to this solution or one like it then you are one of the better developers! Congrats! If not, that is okay too! You can't become better and master a subject until you realize what you don't fully understand. If this was difficult for you then I suggest picking up a basic computer science book and going over the basics a little more until you have a firm grasp and understanding of the subject matter.

I hope you liked this post. If you did then please "like" and share it so more people can benefit from it. Please comment and let me know if you disagree or agree with the article. If you enjoy posts like this then please subscribe to my blog at jasonroell.com.