Decoding Data Structures with Dogs: Singly Linked Lists

Learning all the ins and outs of JS can be overwhelming, but especially when one starts to tackle data structures. In this series I will try to break down some of the basics, easing all of our pain with pictures of dogs, starting with Singly Linked Lists.

In an array, elements are indexed based on their position.

One of the first data structures we learn to use as newbie coders is arrays. To recap, arrays are a list of items that are assigned an index, or a numeric value based on their place in the array. Think of an array like a staircase with a cute pupper sitting on each step. Each step has a value, and we can find each pupper by counting the step that they are on. The first pup is at the bottom, not quite a step yet so we give it the value or index of 0, the next pupper is on the first step so it is at the index of 1.

Linked lists are a little bit different. Instead of every pup (or node, instead of element) having an index, each node is just pointing to the next node. Think of it like a train, each car is connected to the next car, which is connected to the next car, and so forth. In an array we can say “Give me the sixth pup,” but in a linked list we have to start at the beginning of the train, and go from the first car, to the second car, and so forth.

In a linked list, each node is connected to the next, like a train!

The nodes in a linked list each have a value, and a pointer to another node, otherwise pointing to null if it is at the end of the list.

Linked lists have 3 properties:

• Head - the beginning of the list
• Tail - the end of the list
• Length - the length between the head and tail

We can’t pet one pup without petting all the pups!

So why use a linked list over an array? Array elements seem easier to access than list nodes, right? Because arrays are indexed, insertion and deletion can be very expensive in terms of memory. Arrays support direct access, which means all of the elements are stored next to each other in a continuous block of memory, which makes it easy to grab any random element we want, but takes up more memory. If we want to add an element to an array, every other element in the array has to be reindexed, and based on how much memory we have around the array, the entire array might have to be relocated in memory.

All elements in an array are stored in a continuous block of memory.

Linked lists support sequential access, which means the nodes can be stored anywhere in memory, but do not have indexes, only pointers to the next node. What this means is that nodes can be added and removed to the linked list much faster than with an array, and the memory allocated for the rest of the list won’t need to be relocated, the new node can just be created wherever we have space in memory.

Nodes can be stored anywhere in memory, and are connected together by pointers.

The set up and design of a singly linked list is fairly simple. We will be using Javascript classes to demonstrate this, so if you are not familiar with JS classes, please check out the docs here. The most important part of a linked list is the way the nodes are structured: every node needs some type of data, and a pointer to the next node. We’ll start by creating a Node class like so:

The data property contains whatever we want the list to store, and the next property is what we will use to access the next node in the list. We initially set next to null, because we don’t know what the next node will be yet.

We call the first node in a linked list called the head, so we create the head variable to represent the first node. We are then able to create our subsequent Nodes by using the next pointers, to indicate that they are the next link. The final next pointer in the list will remain null.

Our next step in setting up our linked list is by creating a LinkedList class so we can clean things up a bit so we don’t have to keep adding next pointers every time we want to add a new node to our list. Let’s start out by defining our class and adding our constructor. Remember a singly linked list always takes in a couple of things: the head, the tail, and the length. So we can add these as our properties. We’ll set both the head and tail to null to start, because we have yet to pass anything in yet, and also set the length to 0. Now that our constructor is done we can pass in a bunch of methods, and actually start utilizing our Singly Linked List!

Our push function will need to do the following:

• Accept a value as an argument
• Create a new node with said value
• If there is no head property already, assign the value to be the head as well as the tail,
• Otherwise set the next property on the current tail to be the new node
• Set the new node to be the new tail
• Increment the length by 1
• Return the list

We’ll start by assigning our new Node to a variable, in this case I just called it newNode. Then we check if there is not a head, if not, then assign both the head and tail to be the newNode. Otherwise, if there is a head, then assign the tail to be the newNode. Then, we increment the length, and return the list.

Now, we get the same result when we send in a value to our push method, and don’t have to keep track of how many next pointers we have. This SinglyLinkedList class creates the following data structure:

Data structures can be a lot to wrap our heads around as developers, but breaking them down (with dogs) is hopefully at least a little bit helpful!

JavaScript In Plain English

Enjoyed this article? If so, get more similar content by subscribing to Decoded, our YouTube channel!