DEV Community

Cover image for How To: Build a Linked List in JavaScript
Adriana DiPietro
Adriana DiPietro

Posted on • Updated on

How To: Build a Linked List in JavaScript

☁️ Hi Programmers! 🐱

Today we will be building a Linked List from scratch using JavaScript. If you are not familiar with Linked Lists, please head over to this article first and then join us after :)

Let's get started.


Goals

  1. Classes in JavaScript
  2. Class Syntax & the Constructor
  3. Declaring the LinkedList Class
  4. Building LinkedList's Constructor Method
  5. Instantiating a New Instance of LinkedList

Classes in JavaScript

JavaScript actually does not have linked lists built in. However, JavaScript, being as powerful and flexible as it is, is capable of building linked lists using ES6 class syntax.

As you may or may not know, JavaScript classes are syntactic sugar: meaning classes are not necessarily something brand new. Classes should be thought of as a blueprint for a JavaScript object. So, when you hear the term "syntactic sugar," think Classes make the code cleaner, more accessible and more readable.

Since classes are "blueprints," classes do a lot of describing. Classes will describe what the object should do (methods) and what the object has (properties).

Classes are sweet (like syntactic sugar) because each instance of the JavaScript object created out of the class will have the same properties and methods! This is amazing. This reduces a whole lot of code needed to be written and needed to be considered.

Ok - you may have guessed by now... today we will be using Class syntax to build our Linked List!


Class Syntax & the Constructor()

One way to define a class is using a class declaration. To declare a class, you use the class keyword with the name of the class.

Here is an example:

class Post {

}
Enter fullscreen mode Exit fullscreen mode

That's it! That's a class declaration. Now, there are some important AND essential aspects we need to include in our class to make it functional as a blueprint of an object:

  • constructor method
  • properties
  • methods

While the first one may be unrecognizable to you, both properties and methods should be familiar since JavaScript objects have both properties and methods.

The constructor method is used to create a new instance of our class. (THINK: The constructor method constructs a new instance.) While instances of a class can be instantiated with no properties or methods, that would be silly. Classes are amazing for just that! So, the constructor method holds the class's properties and methods and when a new instance is created by the constructor method, that instance has access to those properties and methods.

Let's see this in our example class "Post":

class Post {
   constructor(title, author){
      this.title = title;
      this.author = author;
      this.created_at = new Date()
   }
}
Enter fullscreen mode Exit fullscreen mode

An instance of our Post class when instantiated will have a title property, an author property and a created_at property. And every instance of Post instantiated from here on out will too!

Now we are familiar with class syntax and the functionality of a constructor method, let's start this linked list build!


Declaring the LinkedList Class

Knowing what we know, let's declare a class called "LinkedList" since that is what we are building:


class LinkedList {

}
Enter fullscreen mode Exit fullscreen mode

Class names will start with a capital letter and designate a new word by using another capital letter. No spaces!


Building LinkedList's Constructor Method

Onto the constructor method, we need each instance of a LinkedList to have specific things that are characteristic of a linked list:

1. Head (consisting of data, pointer)
2. Tail (consisting of data, pointer)
3. Length

Every linked list has a head representing the first node; a tail representing the last node; and a length representing how many nodes are in the linked list.

class LinkedList {
    constructor(){
        this.head = 
        this.tail =
        this.length =
    }
}
Enter fullscreen mode Exit fullscreen mode

This keyword refers to the instance instantiated.

Since both the head and the tail are nodes, and we know that nodes consist of both data and a pointer to the next node, we need to show that in the constructor.

class LinkedList {
    constructor(){
        this.head = { 
            data: ___,
            pointer: ___,
        }
        this.tail = { 
            data: ___,
            pointer: ___,
        }
        this.length = ___
    }
}
Enter fullscreen mode Exit fullscreen mode

By passing in "data" into the constructor, we can set a node's data to the data passed in.

constructor(data){
        this.head = {
            data: data,
            pointer: ___
        }
Enter fullscreen mode Exit fullscreen mode

Regarding the pointer of the head node, its value will be null. The reason is that when we instantiate a new instance of a LinkedList, there is only one node AND the tail node always points to null!

Therefore, technically, our tail node is our head node and our length is 1.

class LinkedList {
    constructor(data){
        this.head = {
            data: data,
            pointer: null
        }
        this.tail = this.head
        this.length = 1
    }
}
Enter fullscreen mode Exit fullscreen mode

Instantiating a New Instance of LinkedList

Let's see this in action.

1. In your console, paste the above code snippet from the above section and click 'enter'.

2. Then declare and assign a new instance of LinkedList to a constant called 'newLinkedList' and pass a string ('I love data structures') to LinkedList -- this string represents our data.

3. Call 'newLinkedList'.

linked list

It works! If we expand 'newLinkedList', we should see the head, the tail and the length:

new linked list

Nice!


Recap + Summary

You may notice our instance of LinkedList only has one (1) node. That is true. I plan on writing another blog soon focusing on how to append, prepend and delete nodes from a linked list. So, stay tuned.

Today's linked list is a simple one. But it is a great starting point for understanding the foundation of a what a linked list is and also understanding how powerful JavaScript is.

So, let's continue to learn together and soon enough, we can teach others.

As always, please feel free to comment, ask questions or make suggestions.

Follow for more articles and befriend me on LinkedIn too :)

🀍🀍🀍
🐱🐱🐱

Discussion (5)

Collapse
efpage profile image
Eckehard • Edited on

You should mention two benefits from using classes too:

1. Encapsulation

If you implement some methods to add, delete or serialize your nodes, the user does not need to know about the details of your list. Writing a program he can just use these methods.

If you decide to change your internal structures, you will need to change this methods to. But the program does not need to be changed. So, your code changes are only local to the class definition and your have to change your code only once. This is far less prone to side effects.

2. Inheritance

Now you have designed your class with a pointer to the data. Assume, you need a list that has different properties, let say you want to store an image. You can easily derive a new class that inherits all your methods (including add, delete and serialization). You will have to change some parts of your class to work with the new data type, but lot of the functionallity will probably need no change.

Maybe, you decide to add more capabilities to your current class sometime in the future. The derived class for images will inherit this new methods too. So you probably will save a lot of time as you do not have to add this new methods to the child classes.

And: As the classes are one family, objects are related too. So you can write a program that deals with members of this family regardless of the type.

Thank you very much for your post! ItΒ΄s good to have more practical examples of this kind.

Collapse
am20dipi profile image
Adriana DiPietro Author

Yes! I think I may have a follow-up post and these are great points to consider. Thanks.

Collapse
juli1 profile image
Julien

Wow, that is awesome! Would love to have these code snippets on the codiga snippets marketplace!

Collapse
am20dipi profile image
Adriana DiPietro Author

Hey Julien -- thanks for the comment :) I have never heard of Codiga! Do you use it often?

Collapse
juli1 profile image
Julien

As working on this product, yes, I designed it and use it every single day!