DEV Community

miku86
miku86

Posted on

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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");
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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();
Enter fullscreen mode Exit fullscreen mode

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 }
Enter fullscreen mode Exit fullscreen mode

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?

Top comments (3)

Collapse
 
miku86 profile image
miku86 • Edited

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.

Collapse
 
cooky9 profile image
Landon

Thanks buddy

Thread Thread
 
miku86 profile image
miku86

You're welcome.