JavaScript Data Structures: Singly Linked List: Setup

Intro

Last time, we talked about the theory behind a Singly Linked List.

Today, we start implementing it.

Recap from last time

• real life example: a treasure hunt, where you have a starting point and have to seek places and solve riddles in a particular order; the current place knows about the next place, but the current place doesn't know about the previous place
• consists of nodes
• each node has a value and a pointer to the next node (or null at the end of the list)
• has a head (=start), a tail (=end) and a length
• "singly" because only one connection to another node (the next one)

Setup

So we need two basic entities:

• a single place with a riddle (=> a node)
• the complete treasure hunt (=> the Singly Linked List)

Node

• create a file named singly-linked-list.js
• add this code

// name of the class
class Node {
  // the constructor runs when using the class with `new` (see later)
  constructor(value){
    // set this nodes value property to the instantiation value
    this.value = value;
    // set this nodes next property to `null`
    this.next = null;
  }
}

This is a JavaScript class. Under the hood it uses a function, but it doesn't matter, it's all about the concept. We use this object oriented approach, because it is simple to understand.

We have a class and this class acts as a blueprint for a node.

We can instantiate a new instance of this class and save it into a variable:

const newNode = new Node("Empire State Building");

The string "Empire State Building" becomes the value in the constructor, so this.value becomes "Empire State Building". this.next becomes null.

We can see this by logging it:

console.log(newNode); // Node { value: 'Empire State Building', next: null }

We can now create as many nodes as we need by using new Node()

---

Singly Linked List

• add this code to singly-linked-list.js

// name of the class
class SinglyLinkedList {
  // the constructor runs when using the class with `new`
  constructor() {
    // set this lists length property to `0`
    this.length = 0;
    // set this lists head property to `null`
    this.head = null;
    // set this lists tail property to `null`
    this.tail = null;
  }
}

Similar to our Node. Every instance of the Singly Linked List gets a length, a head and a tail.

We can instantiate a new instance of this class and save it into a variable:

const newSinglyLinkedList = new SinglyLinkedList();

Because all of our three properties are set to default values in the constructor, we don't need arguments.

We can see this by logging it:

console.log(newSinglyLinkedList); // SinglyLinkedList { length: 0, head: null, tail: null }

We can now create our Singly Linked List by using new SinglyLinkedList().

---

Next Part

We will implement how to add a node at the end of the Singly Linked List. If you want to be notified, subscribe :)

---

Questions

• Did you ever use a Singly Linked List in a project? Why?
• Did you ever use classes in JavaScript?

Comments

[miku86]

Great questions, Amir.

Use cases with benefits are:

• when you often have to add or remove data: SLL: O(1) vs. Array: best case O(1) (at the end) - worst case O(N) (at the start)

But in the end, you're very unlikely to see a Singly Linked List.

[Landon]

Thanks buddy

[miku86]

You're welcome.