Why I love Linked Lists

If you are the kind of person who doesn't get even a little spooked when you hear the word "Data-Structure", then you're either a madman or an engineer.

Such was the case when I first dipped my toe into the vast world of "Data Structures and Algorithms". Oh how my head used to wrap around itself trying to understand all the jargons narrated by my teacher in class; Time Complexity, Trees, Maps, Graphs and so on. Early on in the course, things seemed to be calm, manageable even when we heard words we were accustomed to such as "Stack" and "Queue". We even seemed to be getting the hang of the code, until one fine day our teacher dropped a term in class we had never heard before, "Linked List". We thought to ourselves, "Sounds simple enough, a list that's linked in some way." Oh how wrong we were.

You see, we had never worked with things like nodes before, the data structures we were accustomed to were very straight-forward, a continuous series of data that were made up of smaller pieces of data encapsulating a singular value that were navigable by incrementing or decrementing the corresponding index value. Sounds simple enough? Just picture a certain set of marbles, you place your finger on the first one, then pace your finger past each of them consecutively and add a marble to the end. Done!

But with Linked Lists,

you have a significant advantage over the other data structures, you are now able to allocate data dynamically into any part of your list. This is possible crediting to Linked List's node structure that encapsulates 2 pieces of data per node rather than 1. One that stores the actual data and the other that stores the address to the next node. You are not playing with marbles anymore, but trains.

If you are anything like me, you would do what I did, and that is run straight to the code out of sheer curiosity to know what we're dealing with, and if you are anything like me, chances are that you are quite intimidated. But not to worry, we can tackle this! To understand the code, we must first have a clear picture in our heads of what linked lists actually are. Rather than reading out syntax and hoping that our brain will create a picture for us, its better we start imagining first. This is the first thing that stood out to me about linked lists. I found that the more I actually started picturing what I was working with, the faster the code materialized in my head.

Think of a Linked list like a train.

The head is the engine. That is, the node at the start of every linked list and the succeeding nodes as the railcars. Each individual railcar and the engine has 2 data slots as mentioned before, the data and the address that points to the next node.

Node(int t){
        next=null;
        data=t;
    }

After we initialize the constructor Node, we pass the number we wish to store from the main function, that is, the variable 't'. The address space is null because it then makes it easier to point it to other nodes. Also the initial node will always point to null because we build the list in reverse and we change the position of the head to compensate for it. We do this because if we move the head forwards, we have no way of reaching the elements at the back, due to the inability to go backwards in a singly linked list.

Here is the code:

void insert(int data) {
        Node2 t=new Node2(data);
        if(head==null) {
            head=t;
        }
        else {
            t.next=head;
            head=t;
        }
    }

The fact that we just pass a value to a function and a node with a structure as specific as this is generated feels like magic in itself. Ah, who knew abstraction and encapsulation could be so beautiful! But wait, we are yet to dive into the juicy parts.

Alright, we have the base for our linked list, but what if we wanted to make more use of the linked list's power. Let's try inserting a value in between the head and the next node. Like I said, first let's picture the engine that is, the head and the railcar that is, the succeeding node. The coupling will take place like this:

Insertion of a node in between two nodes

If it wasn't already apparent from the illustration, not to worry. It's either my awful drawing skills or we just relate better to practical examples.

So what's happening here is,

a new railcar comes into the picture and it needs to be coupled between the engine and the other railcar. So keeping that image in mind, for the coupling to take place the engine will have to make way for the new railcar. But code is slightly different from reality. In reality, the new railcar could just as easily couple with the other railcar without the engine's help, but in code, if we detached the head (i.e. the engine), the other railcar and all the corresponding railcars would be lost because we hadn't stored the address. So to make sure the connection (i.e. the address to the next node) is never lost, we assign the new node's address to the subsequent node's (In this case, head.next is the address of the next node) address first before we detach the engine (i.e. the head). Now that we made sure the connection to the other railcars is always present, we can safely detach the engine. Now that the connection between the new node and the succeeding node is established, all we need to do is connect the head to the new node (i.e. the engine to the new railcar) and Voila! We now have an even bigger train. Cool no? Now let us take a look at the code, you should have a good enough idea of what's goin on now.

Node inbtw(int data) {
        Node t=new Node(data);
        if(head==null) {
            head=t;
        }
        else if(head.next==null) {
            head.next=t;
        }
        else {
            t.next=head.next;
            head.next=t;
        }
        return head;
}

We have made this intricate system with just a few lines of code inside of a function. Gives us a little insight into the beautiful, yet complex nature of simple things.

Now that we have the basics down, let's quickly move on to

how to delete a node from your linked list.

You now have a train with an engine and 2 railcars, but there may come a time when you will need to let one of them go. So how do you go about it?
It's easy! When it comes to the connection of nodes, your address (i.e. the 'next' object) is the key. Just like how you assigned the address of your new node to a node currently residing in your list when you wanted to connect it, all you need to do is change the address of the node preceding the node you wish to delete to the node that is present after the node you wish to delete. Taking the railcar example, you alter the connection of one railcar to the railcar that succeeds it 2 steps later, effectively pretending the railcar between them never existed. Taking the code into account,

void delete() {
        if(head==null) {
            System.out.println("The list is empty");
            return;
        }
        if(head.next==null) {
            System.out.println("The list doesn't have a second element");
            return;
        }
        if(head.next.next==null) {
            head.next=null;
            return;
        }
        head.next=head.next.next;
    }

In this code, we delete the second element in the list, that is, the node between head and head.next.next. Observe that after resolving all the null cases, the address to the next node from the head is appointed to the node that comes after that node (i.e. The node that comes 2nd after the head), thereby pretending that node (i.e. The first node after the head) was never there.

In the illustration, the dotted line signifies that a relation used to be present between the 2 nodes. You can see that we have shifted the address of head.next that pointed to head.next.next to the head, in that case you might be wondering if the node between them would still be in the memory. The answer is yes, but since we do not have an address that points to that node from our list, it is considered to be "erased".

Finally let's wrap up the fundamental functions of our linked list with the display function that displays all of the elements. A relatively simple code that needs no explanation if you made it this far.

Node display(Node s) {
        if(s==null||s.next==null) {
            System.out.println(s.data);
            return head;
        }
        Node e=display(s.next);
        s.next.next=e;
        s.next=null;
        System.out.println(s.data);
        return e;
}

With that, concludes our brief look into the world of Linked Lists. Well, how was it?

If you feel even more confused than ever, I would first like to apologize if I had made it seem harder than it really was and would like to tell you to not give up. When I first started out, I was really confused as well, along with many others, but with persistence and practice, slowly but surely we got the hang of it and so will you.

On the flipside, if you believe this article helped you in some way, I am glad we got to share this experience together. Just remember, this is just a glance into the vast world of Data Structures. Have you ever tried reversing a singly linked list? Sounds easy right? Well, try doing it using recursion for a good challenge. If you feel like getting in more practice, check out this problem on HackerRank. Speaking of linked lists, we have only discussed the singly model. Other models like the Doubly and the Circular Linked Lists are just waiting to be explored by you.

To end this with a thought,

I love linked lists not only because it was the first data structure I tackled with a completely different paradigm from the rest, not because I spent weeks to understand it and not because of its extensive use of encapsulation and abstraction. But mainly because it gave me a new perspective on coding as a whole. Don't get me wrong, I am no master of linked lists, and certainly not a master of Data Structures. Not in the slightest. But that's okay, neither should you. It's okay if you take weeks to understand 10 lines of code, it's okay to feel frustrated and drink a glass of water and take a break to read a book when you feel overwhelmed by a problem. At the end of the day, what matters is what that problem taught you and how it made you feel at the end of it all.

Did you hate the problem initially but eventually find yourself enjoying the boosts of adrenaline looking back? Did you enjoy the feeling of being stumped and realizing that you're not done yet? Well then, you're a coder my friend! In the end, these are the emotions that linked lists made me feel, and why I still code to this day, hoping and waiting for the next problem to show itself and test my skills.