Data Structures For Dummies: Linked Lists

Source: Hello Big Idea

As a part of my journey to understand blockchain more in depth, I’ve begun learning about the fundamental data structures of computer science. Before you do anything with any data at all, it’s important to organize it in a way that will be easily accessed and read, tailored to your own needs. This series will be the result of my learning! In every article we’ll learn about how each data structure works, and how you can code one yourself.

Before we dive into linked lists, let’s start building up from the basics first.

Arrays

An array is super simple: it’s essentially a list — an array — of data that is stored in memory. So, instead of having to individually define hundreds of variables, you can just store a bunch of values into an array and make the entire array one single variable. Each value in the array has an index to facilitate access, and the first value has an index of 0. Here’s what it looks like in code:

var fruits = ["oranges", "apples", "mangoes"];
var citrus = fruits.[0]
var doctor = fruits.[1]

In the above code, we made an array called fruits, in which we stored the strings “oranges”, “apples” and “mangoes”. Then, in the next two lines, we created a variable called citrus, in which we called the first value of the fruits array (item 0). The resulting string would therefore be “oranges”. In the next line, we created a variable called doctor, in which we called the second value of the fruits array, which is the string “apples”.

So far so good! Let’s move on.

Structs

Structs are used to store groups of variables together. Say you wanted to create profiles for users of a certain application. It would look something like this:

function userProfile(firstName, lastName, age) {
    this.firstName = firstName;
    this.lastName = lastName;
    this.age = age;
};
var users = [
    new userProfile("Ramy", "Zhang", 17),
    new userProfile("John", "Doe", 17)
];

In the above, we made a class of variables in Javascript relating to the user profile to emulate a struct. The class contains the three variables firstName, lastName and age.

Linked Lists

Linked lists are made up of nodes, which are essentially structs that contain two things: any variable, and a pointer. A pointer is a special variable that will point to another location in memory. In linked lists, each node points to the next node, thus creating a “list”. You can make the list circular (meaning the “last” node will point back to the first one), or you can end it at a node by making the last value null.

Because of these properties of nodes, in a linked list you must walk through the entire list to get to a certain value; you can’t just access random values instantly like in an array. However, with linked lists you can quickly re-order the data, trim it, split it, make deletions and add insertions.

Source

Computer science uses something called Big O notation to grasp the amount of time it will take to perform certain actions on a data structure. We say it takes linear time — in Big O notation, O(n) — to perform random access and appends (adding new values to the end) on a linked list. On the other hand, we say it takes constant time — in Big O notation, O(1) — to make insertions (prepends) and deletions on a linked list.

To understand this, we can use the analogy of carrier pigeons. What’s the difference between electronically transferring data to another computer in another building, and putting that data onto a USB stick and giving it to a carrier pigeon to send to the same building? No matter how much data you put into the USB stick, the pigeon will always take the same amount of time to send it over. Constant time! However, the more data you try to transfer between the computers electronically, the longer it will take — linear time.

Code it!

There’s no better way to really learn something than simply creating it. Let’s code our own linked list to understand how it really works under the hood!

We’ll start with the most important part — creating the first node.

public class Node {
  Node next;
  int data;
  public Node(int data) {
    this.data = data;
    }
}

Remember when I said the node contains two things — a variable for whatever you need and a pointer? This class Node contains exactly that — a pointer towards the next node (Node next), and a variable that will contain some data (int data). There is also constructor included (public Node(int data)) that will allow us the set data values more easily later on.

public class Node {
  Node next;
  int data;
  public Node(int data) {
    this.data = data;
    }
}
public class LinkedList {
  Node head;
  public void append(int data) {
    if (head == null) {
      head = new Node(data);
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
      }
    current.next = new Node(data);
  }
}

The above is the append method for insertions at the end of a linked list. Within the class of LinkedList, we created a function that will take in some data (int data) and walk through the linked list from the head node (the first node) until it gets to the end, in which the last node will be null. When the last node is null, the code will know that that’s the end of the linked list. So, if current.next is in fact null, we can simply add a new node with the data we want.

However, the “walking” needs to start somewhere. What if the head node was null? In that case, the if statement that checks whether the head is null or not will simply create a head node with some data to start the walking process.

Another consideration is, what happens if before we used the append method, we already prepended a new value to the beginning of the linked list? The head node where the “walking” starts to get to the end of the list (Node current = head) will be different. To address this, there is an overarching class LinkedList that wraps the head node of the linked list (Node head) in order to make sure every node has access to the same head node at all times.

public class Node {
  Node next;
  int data;
  public Node(int data) {
    this.data = data;
    }
}
public class LinkedList {
  Node head;
  public void append(int data) {
    if (head == null) {
      head = new Node(data);
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
      }
    current.next = new Node(data);
  }
  public void prepend(int data) {
    Node newHead = new Node(data);
    newHead.next = head;
    head = newHead;
  }
}

The above that’s bolded is the new method addition: the prepend method. In this method, we take in some data to create a new head node for the linked list. It’s relatively straightforward: first, the new head node is created, taking in data; then, we make sure the node after the new head node is the original head node (head); finally, we set the head node as the newHead.

public class Node {
  Node next;
  int data;
  public Node(int data) {
    this.data = data;
    }
}
public class LinkedList {
  Node head;
  public void append(int data) {
    if (head == null) {
      head = new Node(data);
      return;
    }
    Node current = head;
    while (current.next != null) {
      current = current.next;
      }
    current.next = new Node(data);
  }
  public void prepend(int data) {
    Node newHead = new Node(data);
    newHead.next = head;
    head = newHead;
  }
  public void deleteWithValue(int data) {
    if (head == null) return;
    if (head.data == data) {
      head = head.next;
      return;
    }
    
    Node current = head;
    while (current.next != null) {
      if (current.next.data == data) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
}

The new method we’ve added is a deletion method which takes in some data (int data) that it wants to delete from the linked list. First, it checks whether there is a linked list at all by stopping the function if the head node is already null. Then, it checks whether the head’s data is the same as the data we want to delete. If so, then we set the head to the node after the head (head.next).

If none of these conditions are true, we can start “walking” through the linked list starting from the head (Node current = head) to find the data we want to delete. The goal here is that, once we get to the data we want to delete, we re-orient the previous node’s pointer to simply skip over the node we want to delete and point directly to the node after that.

To do this, we first make sure the next node isn’t null (while (current.next != null)), so that we don’t walk right off the edge of the linked list. Then, we create an if statement indicating that if the next node’s data is the data we want to delete, we cut out that node by setting the next node to the node after the next (current.next.next).

There you go! You’ve created your very own linked list.

Applications of Linked Lists

So at this point you’re probably wondering: what do I actually need linked lists for?

Linked lists can serve as great, reliable underlying structures for more complex data structures to be built on top. For example, if you were to create a queue, a stack, or a hash table, a linked list would be an excellent foundation to build upon.

Thank you for reading! If you found this helpful, here’s some next steps you can take:

1. Send some claps my way!
2. Follow me on Medium and connect with me on LinkedIn to be updated when next article of this series is out!
3. Get some more practice by doing some problems with linked lists!
4. Check out the next article in this series on Binary Search Trees!