A Developer’s Travels Episode 1: Linked Lists

8 min readMar 7, 2019

A guide to help you understand linked lists, written by someone who just learned them.

I often describe myself to people I meet as both a designer and a developer—a designer so that people think I have a personality, and a developer so recruiters think I’m worthy of a job.

But I digress. While I wear the emblem of both D’s, I’ve spent more of my blogging efforts writing about design than I have about the wonderful world of code. More specifically, given m design articles and n coding articles, I’ve written m more design articles than I have coding articles. So uh, how many coding articles is that?

Oh boy do I have a lot of work to do. Time to get right to it!

This article will serve as a very, very basic introduction to a very, very important data structure in computer science: the linked list. In this installment, you will learn what a linked list is, how it works, and how to set up one in code.

Speaking of code, all code in this article will be written in C++. You need not know C++ in order to understand what a linked list is, but you should if you want to understand the code sections of this article. Feel free to post in the comments if you’d like to see this done in another language (i.e. JavaScript, Python, etc). I know, pointers can still frightened even the most seasoned of developers.

What Is A Linked List?

A linked list is a type of data structure. A data structure is a type of container which organizes data in a particular way. A very common data structure is one with which you are probably already familiar: an array. Arrays structure data in a sequential and contiguous way: sequential in that each block of data can be accessed with an index number( like array[1], array[2] etc), and contiguous in that all of the data occupies a single region of memory.

Linked lists are a bit different from arrays. Arrays can be thought of as a collection of lego pieces snapped together to form a rectangular block…

Linked lists, on the other hand, can be thought of as a chain…

The block-chain analogy (no pun intended) makes more sense when you think about how blocks and chains function in the real world. You cannot “bend” a block of legos, otherwise that specific block will no longer exist. Arrays are inherently structured in this way: every piece of data inside an array is adjacent to one another in memory.

Chains, on the other hand, you can bend. Chains can form a line—or they can form a circle, or a zig-zag, or whatever—while still maintaining their underlying structure. Likewise, linked lists are structured in this sort of way: their data can be anywhere in memory and yet are still connected to one another.

Got it? Good! Let’s keep digging deeper.

Digging Deeper

Technically speaking, a linked list is a collection of interconnected data structures called nodes. A node is an abstract data type (ADT) which has two components: the data we’re interested in, and an another component which links the current node to another node in a list (in our case, this component is represented by a pointer). In C++, a node would look something like this…

struct Node {
  int data;
  Node *next;
};

For this node, our data is some integer value. However, in practice, our data can be anything — even multiple values (e.g. data1, data2) — but we’ll stick to using a single integer variable for simplicity’s sake.

In any linked list, we will always have two kinds of nodes: The first node in a linked list is known as the head node, while the last node in the list is known as the tail node. Basically, they allow us to determine where a list starts and where it ends.

Before moving forward, it’s worth noting that there are different types of linked lists out there, but since I said this was a very, very basic introduction, I’ll cover my ass and focus on only singly-linked lists, the most basic type of linked list there is.

A very, very basic design for a very, very basic linked list, as told in a very, very basic article.

Looking at the diagram above, we start to notice a couple of things. First, we see that the nodes in a singly linked list are connected going only one way: forward. In other words, if we are at one node in the list, we can jump to the node right after it, but not one right before it. Second, the tail node’s node pointer points to NULL (try saying that 10 times fast). This is how the tail node indicates that we have reached the end of the list.

Making A List…

Now that we have our node, it’s time to make our list. We’ll do this by creating a class called LinkedList, and doing some initial setup below.

class LinkedList {
  public:  //Constructor to prep our list for use
    LinkedList() {
      //stuff to go here later
    }  private:
    Node *head;
    Node *tail;
};

By default, every new linked list is empty—i.e. there are no nodes. By “no nodes”, we mean, literally, there are no nodes. By “literally, no nodes”, we mean no head node or tail node. In code then, “no head node or tail node” means:

head = NULL;
tail = NULL;

With this in mind, we can define the LinkedList’s constructor as follows:

LinkedList() {
  head = NULL;
  tail = NULL;
}

And so, our code now looks like this…

class LinkedList {
  public://Constructor to prep our list for use
    LinkedList() {
      head = NULL;
      tail = NULL;
    }private:
    Node *head;
    Node *tail;
};

But I Thought You Said…

That there is always a head and a tail node? Yes, yes I did. To wrap your head around the fact that an empty list has no head or tail node, think of these as “titles” bestowed on two nodes. When the list is empty, we still have the titles of our royal couple, the honorable Mr. and Mrs. Head and Tail, but those titles are vacant. Hence, we set them to NULL. Or put another way, a corporation always has a CEO title (I think?), even if the CEO is no longer there.

Two developers looking at their non-existent CEO (image courtesy of hardwoodandhollywood.com)

…And Adding To It

Now that we have our list, it’s time to figure out how we can add to it. After all, what’s the point of a list if you can’t list anything in it? First, let’s set up the class method which will allow us to do this. We’ll call it addNode(), which will take an integer as an argument.

class LinkedList {
  public://Constructor to prep our list for use
    LinkedList() {
      head = NULL;
      tail = NULL;
    }    void addNode(int value) {
    //do the add node stuff here
    }private:
    Node *head;
    Node *tail;
};

You might be wondering why our addNode() method takes in an integer instead of a Node. Well, in order to add a node to our list, we need some data to go in that node. Therefore, our method doesn’t take in a node, but rather the data we want to insert in the new node, hence the integer.

With that said, it’s time to create the node which will contain our new data:

Node *newNode = new Node;

Oh, and to set it up with our value and other important things…

tempNode->data = value;
tempNode->next = NULL;

So the addNode() now looks like this:

void addNode(int value) {
    Node *newNode = new Node;
    tempNode->data = value;
    tempNode->next = NULL;
}

Our node is all set and ready to be added to our list. The first step to adding our node is to figure out where we’re adding it to. This is determined by checking whether or not the list is empty. If the list is indeed empty, then our new node will be the first node in the list. This means, you guessed it, it’ll become the head node. However, this would mean it becomes the tail node as well. Basically, if we only have one node in the list, it is both the head node and the tail node. Below is what all of the above is saying but in code:

void addNode(int value) {
    Node *newNode = new Node;
    tempNode->data = value;
    tempNode->next = NULL;
    
    if(head == NULL) {
      head = newNode;
      tail = newNode;
    }
}

If the list is empty, then adding a new node is simple: set it as both the head and the tail node and get on with your life. Then again, there’s no point in making a list if all you have to list is one item. So, let’s look at the other case where we’re adding a node to a list which already has data.

else {
//Do that add node to a non-empty list magic
}

Because our list is not empty, the original tail node is no longer the tail node. In other words, the tail’s next pointer no longer points to NULL, but rather to our new node. This gives us:

else {
  tail->next = newNode;
}

Because our new node has been added to our list, it itself is now the new tail node:

else {
  tail->next = newNode;
  tail = tail->next;
}

Now we have everything we need to add a node to our list. Putting it all together gives us…

class LinkedList {
  public:  //Constructor to prep our list for use
    LinkedList() {
      head = NULL;
      tail = NULL;
    }    void addNode(int value) {
      Node *newNode = new Node;
      tempNode->data = value;
      tempNode->next = NULL;
    
      if(head == NULL) {
        head = newNode;
        tail = newNode;
      } else {
          tail->next = newNode;
          tail = tail->next;
        }
     } private:
    Node *head;
    Node *tail;
};

Where We Go From Here

Great! We have our very, very basic linked list. This is indeed a very, very basic linked list, because there are other things we can do with even a singly linked list besides add data to it. We could traverse it, we could add data to somewhere inside it, and even delete data from it. I’ll save those for either another article, or just slap it into this one when I’m finished. Thank you for reading my first developer post! I hope you enjoyed it, and don’t forget to clap!