Thirsty to learn about linked lists? You’ve come to the right place — this post is an introduction to linked list data structures — what they are, how they compare to arrays, and how to create and manipulate them in JavaScript.

A linked list is a linear data structure in which each element (node) stores both data and directions (pointer or reference) to the next node’s location in memory.

Linked lists come in three different flavours:

1. Singly Linked Lists 🍋

2. Doubly Linked Lists 🍒

3. Circular Linked Lists 🍑

This post will focus on singly linked lists, but you can read more about doubly linked and circular linked lists 🍒here🍒 and 🍑here🍑.

The first node in a linked list is called the head and is the entry point to the linked list.

The last node in a linked list is called the tail, and it points to null.

The linked list pictured above has five nodes, and each node stores data (in this case, an instruction for a lemonade recipe) and a pointer to the next node location.

class Node { 
  constructor(data, next = null) {
     this.data = data;
     this.next = next;
  }
 }
const step5 = new Node("Serve Lemonade");
const step4 = new Node("Mix with Water", step5);
const step3 = new Node("Add Sugar", step4);
const step2 = new Node("Squeeze Lemons", step3);
const step1 = new Node("Life Gives Lemons", step2);

Each node object is instantiated with two properties: data, and next*** ***(pointer).

If we print the first node, we can see that the next property of each object contains the subsequent node in the linked list (nested structure).

Notice the last (tail) node’s next property has the value of null. The recipe has been completed; there are no more steps! That means it’s time to kick back and sip our lemonade 😎🍹️.

When making a recipe, we start at the beginning and move through the steps in the same order every time — otherwise, we might end up with some pretty dubious food! 😱

Like an array, we can iterate through the list to access each node’s values:

function makeLemonade() {  let step = step1;  while (step != null) {   console.log(step.data);   step = step.next;  }}makeLemonade();

Running the above code prints out the data from each node, starting from the **head **and ending at the tail

A downside of linked lists is that we must access nodes in order, starting from the head (no random access to nodes 🙅🏻‍♀️). This makes searching much less efficient than arrays — say farewell to binary searches if you choose to use a linked list.

Introducing the new and improved ✨strawberry lemonade recipe✨!

My recipe (pictured above) doesn’t look so hot after I tried to add another step in the middle — there wasn’t enough room to write the new step, I had to re-number the subsequent steps, and it looks like I have to re-write the entire thing from scratch. This is what can happen when we try to insert/delete from an array — it may require completely reorganizing the data structure in memory.

Unlike arrays, linked list nodes are stored in non-contiguous memory (not all together in the same place) and their length is not defined at their time of creation. This makes linked lists a good choice if you need ongoing insertions/deletions from your data set.

While linked lists do take up a little bit more memory compared to arrays (because we need to store the data and a pointer, as opposed to just the data), linked list memory usage is more *flexible *and efficient than arrays.

Linked lists also have an advantage over arrays in ease of adding/removing nodes — all we need to do is add the data and adjust the pointers to fit our needs. This means we can easily insert nodes anywhere in the list, as opposed to arrays that allow insertions at only the head/tail.

Let’s get cracking on that strawberry lemonade, shall we?

We’ll need to add some functionality to our linked lists — let’s start by making a new class called LinkedList to contain all the methods we’ll need for interacting with a linked list object.

class LinkedList {   constructor() {   this.head = null}

The LinkedList object will be instantiated with a head attribute, which holds the head node object (in this case no nodes have been added to the linked list yet, so the value is null).

Next, I’ll define a method that takes two parameters: the node that will come *before *the new node (aka the previous node), and the new node’s data.

insertAfter(prevNode, data) {   const newNode = new Node(data, prevNode.next);   prevNode.next = newNode;}

Inside this function we’ll instantiate a new Node object, passing in our node’s data and a pointer previous node’s next.

We’ll then set the previous node’s next to point at our new node.

Finally, we’re going to increase the length of our LinkedList object.

That was a lot of words — have a look at the image below to help visualize what just happened:

If we needed to add a step at the end of our linked list, we can simply pass null into the new Node’s *next *parameter

What if we need to add a step at the beginning of the linked list? This process will look a bit different:

insertAtBeginning(data) {   const newNode = new Node(data, this.head);   this.head = newNode;}

You’ll notice that this method only has one parameter instead of two because there isn’t a previous node in this case.

We’re then setting our new node’s next to the current head node and then setting our new node as the linked list’s head.

At this point, you might be thinking “We’re adding sugar AND strawberry syrup to our lemonade?? Haven’t you heard of dental caries?!”

I too value my oral health — we’d better cut out the “Add Sugar” step

To delete a node from the linked list, we need to:

1. Find the target node and its previous node (if there is one!)

2. Change the next of the previous node to bypass the target node

3. Delete the target node from memory

We’ll approach this problem using another method inside our LinkedList class — this method will accept a parameter representing the data of the node we want to delete.

Have a look over the code, and we’ll talk through the steps below.

removeValue(value) {   let prevNode = null;   let currentNode = this.head;   while (currentNode) {     if (currentNode.data === value) {       if (prevNode) {         prevNode.next = currentNode.next;       } else {         this.head = currentNode.next;        }       currentNode = null;       return true     }  prevNode = currentNode;  currentNode = currentNode.next;  }}

We start by defining variables for the current node and the previous node — we’ll need both of these later.

Starting at the head, we iterate through the linked list. When the current node’s value is equal to the value we’re searching for, then we either:

1. Set the previous node’s next to point at the current node’s next

2. If the current node is the head, we set the head to be the current node’s next

We then delete the current node and exit the loop.

Again, a lot of words. Here’s a visual:

Here are a few more methods to add to your linked list toolkit:

clearList(){  this.head = null;}

findIndex(data) {   let index = 0;   let currentNode = this.head;   while (currentNode) {     if (currentNode.data === data) return index;     node = node.next;     index += 1;   }}

getFirst() {  return this.head;}

getLast() { let lastNode = this.head;    if (lastNode) {      while (lastNode.next) {       lastNode = lastNode.next;      }
  }  return lastNode;}

listLength() {   let currentNode = head;
   let length = 0;   while (currentNode !== null) {    length++;    currentNode = currentNode.next;   }  return length;}

• Linked lists are linear data structures made of non-contiguously stored nodes

• Each node contains data + pointer to the next node

• Linked lists allow for more flexible and efficient memory use compared to arrays

Adding/removing nodes is much easier to do with linked lists compared to arrays

Now you know why linked lists are simply the zest, and hopefully will feel more confident when they come up in your next coding interview!

• Ali Spittel, thank u, next: an introduction to linked lists

• Bill Waters, Beginner’s Guide to the Linked List Data Structure in Nodejs

• Geeks for Geeks, Linked List Data Structure

• Sarah Chima Atonwou, How to Implement a Linked List in Javascript

• Shubhangi Raj Atrawal, Linked Lists in JavaScript (ES6 code)

Thirsty to learn about linked lists? You’ve come to the right place — this post is an introduction to linked list data structures — what they are, how they compare to arrays, and how to create and manipulate them in JavaScript.

A linked list is a linear data structure in which each element (node) stores both data and directions (pointer or reference) to the next node’s location in memory.

Linked lists come in three different flavours:

1. Singly Linked Lists 🍋

2. Doubly Linked Lists 🍒

3. Circular Linked Lists 🍑

This post will focus on singly linked lists, but you can read more about doubly linked and circular linked lists 🍒here🍒 and 🍑here🍑.

The first node in a linked list is called the head and is the entry point to the linked list.

The last node in a linked list is called the tail, and it points to null.

The linked list pictured above has five nodes, and each node stores data (in this case, an instruction for a lemonade recipe) and a pointer to the next node location.

class Node { 
  constructor(data, next = null) {
     this.data = data;
     this.next = next;
  }
 }
const step5 = new Node("Serve Lemonade");
const step4 = new Node("Mix with Water", step5);
const step3 = new Node("Add Sugar", step4);
const step2 = new Node("Squeeze Lemons", step3);
const step1 = new Node("Life Gives Lemons", step2);

Each node object is instantiated with two properties: data, and next*** ***(pointer).

If we print the first node, we can see that the next property of each object contains the subsequent node in the linked list (nested structure).

Notice the last (tail) node’s next property has the value of null. The recipe has been completed; there are no more steps! That means it’s time to kick back and sip our lemonade 😎🍹️.

When making a recipe, we start at the beginning and move through the steps in the same order every time — otherwise, we might end up with some pretty dubious food! 😱

Like an array, we can iterate through the list to access each node’s values:

function makeLemonade() {  let step = step1;  while (step != null) {   console.log(step.data);   step = step.next;  }}makeLemonade();

Running the above code prints out the data from each node, starting from the **head **and ending at the tail

A downside of linked lists is that we must access nodes in order, starting from the head (no random access to nodes 🙅🏻‍♀️). This makes searching much less efficient than arrays — say farewell to binary searches if you choose to use a linked list.

Introducing the new and improved ✨strawberry lemonade recipe✨!

My recipe (pictured above) doesn’t look so hot after I tried to add another step in the middle — there wasn’t enough room to write the new step, I had to re-number the subsequent steps, and it looks like I have to re-write the entire thing from scratch. This is what can happen when we try to insert/delete from an array — it may require completely reorganizing the data structure in memory.

Unlike arrays, linked list nodes are stored in non-contiguous memory (not all together in the same place) and their length is not defined at their time of creation. This makes linked lists a good choice if you need ongoing insertions/deletions from your data set.

While linked lists do take up a little bit more memory compared to arrays (because we need to store the data and a pointer, as opposed to just the data), linked list memory usage is more *flexible *and efficient than arrays.

Linked lists also have an advantage over arrays in ease of adding/removing nodes — all we need to do is add the data and adjust the pointers to fit our needs. This means we can easily insert nodes anywhere in the list, as opposed to arrays that allow insertions at only the head/tail.

Let’s get cracking on that strawberry lemonade, shall we?

We’ll need to add some functionality to our linked lists — let’s start by making a new class called LinkedList to contain all the methods we’ll need for interacting with a linked list object.

class LinkedList {   constructor() {   this.head = null}

The LinkedList object will be instantiated with a head attribute, which holds the head node object (in this case no nodes have been added to the linked list yet, so the value is null).

Next, I’ll define a method that takes two parameters: the node that will come *before *the new node (aka the previous node), and the new node’s data.

insertAfter(prevNode, data) {   const newNode = new Node(data, prevNode.next);   prevNode.next = newNode;}

Inside this function we’ll instantiate a new Node object, passing in our node’s data and a pointer previous node’s next.

We’ll then set the previous node’s next to point at our new node.

Finally, we’re going to increase the length of our LinkedList object.

That was a lot of words — have a look at the image below to help visualize what just happened:

If we needed to add a step at the end of our linked list, we can simply pass null into the new Node’s *next *parameter

What if we need to add a step at the beginning of the linked list? This process will look a bit different:

insertAtBeginning(data) {   const newNode = new Node(data, this.head);   this.head = newNode;}

You’ll notice that this method only has one parameter instead of two because there isn’t a previous node in this case.

We’re then setting our new node’s next to the current head node and then setting our new node as the linked list’s head.

At this point, you might be thinking “We’re adding sugar AND strawberry syrup to our lemonade?? Haven’t you heard of dental caries?!”

I too value my oral health — we’d better cut out the “Add Sugar” step

To delete a node from the linked list, we need to:

1. Find the target node and its previous node (if there is one!)

2. Change the next of the previous node to bypass the target node

3. Delete the target node from memory

We’ll approach this problem using another method inside our LinkedList class — this method will accept a parameter representing the data of the node we want to delete.

Have a look over the code, and we’ll talk through the steps below.

removeValue(value) {   let prevNode = null;   let currentNode = this.head;   while (currentNode) {     if (currentNode.data === value) {       if (prevNode) {         prevNode.next = currentNode.next;       } else {         this.head = currentNode.next;        }       currentNode = null;       return true     }  prevNode = currentNode;  currentNode = currentNode.next;  }}

We start by defining variables for the current node and the previous node — we’ll need both of these later.

Starting at the head, we iterate through the linked list. When the current node’s value is equal to the value we’re searching for, then we either:

1. Set the previous node’s next to point at the current node’s next

2. If the current node is the head, we set the head to be the current node’s next

We then delete the current node and exit the loop.

Again, a lot of words. Here’s a visual:

Here are a few more methods to add to your linked list toolkit:

clearList(){  this.head = null;}

findIndex(data) {   let index = 0;   let currentNode = this.head;   while (currentNode) {     if (currentNode.data === data) return index;     node = node.next;     index += 1;   }}

getFirst() {  return this.head;}

getLast() { let lastNode = this.head;    if (lastNode) {      while (lastNode.next) {       lastNode = lastNode.next;      }
  }  return lastNode;}

listLength() {   let currentNode = head;
   let length = 0;   while (currentNode !== null) {    length++;    currentNode = currentNode.next;   }  return length;}

• Linked lists are linear data structures made of non-contiguously stored nodes

• Each node contains data + pointer to the next node

• Linked lists allow for more flexible and efficient memory use compared to arrays

Adding/removing nodes is much easier to do with linked lists compared to arrays

Now you know why linked lists are simply the zest, and hopefully will feel more confident when they come up in your next coding interview!

• Ali Spittel, thank u, next: an introduction to linked lists

• Bill Waters, Beginner’s Guide to the Linked List Data Structure in Nodejs

• Geeks for Geeks, Linked List Data Structure

• Sarah Chima Atonwou, How to Implement a Linked List in Javascript

• Shubhangi Raj Atrawal, Linked Lists in JavaScript (ES6 code)