loading...

JavaScript Data Structures: Singly Linked List: Setup

miku86 profile image miku86 ・2 min read

JavaScript Data Structures (40 Part Series)

1) JavaScript Data Structures: Singly Linked List 2) JavaScript Data Structures: Singly Linked List: Setup 3 ... 38 3) JavaScript Data Structures: Singly Linked List: Push 4) JavaScript Data Structures: Singly Linked List: Pop 5) JavaScript Data Structures: Singly Linked List: Unshift 6) JavaScript Data Structures: Singly Linked List: Shift 7) JavaScript Data Structures: Singly Linked List: Get 8) JavaScript Data Structures: Singly Linked List: Set 9) JavaScript Data Structures: Singly Linked List: Insert 10) JavaScript Data Structures: Singly Linked List: Remove 11) JavaScript Data Structures: Singly Linked List: Recap 12) JavaScript Data Structures: Doubly Linked List: Intro and Setup 13) JavaScript Data Structures: Doubly Linked List: Push / Add data to the end 14) JavaScript Data Structures: Doubly Linked List: Pop / Remove data from the end 15) JavaScript Data Structures: Doubly Linked List: Unshift / Add data to the beginning 16) JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning 17) JavaScript Data Structures: Doubly Linked List: Get a specific node by its index 18) JavaScript Data Structures: Doubly Linked List: Set / Update a specific node 19) JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index 20) JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index 21) JavaScript Data Structures: Doubly Linked List: Recap 22) JavaScript Data Structures: Stack: Intro 23) JavaScript Data Structures: Stack: Push / Add a new node 24) JavaScript Data Structures: Stack: Pop / Remove the last node 25) JavaScript Data Structures: Stack: Recap 26) JavaScript Data Structures: Queue: Intro 27) JavaScript Data Structures: Queue: Enqueue 28) JavaScript Data Structures: Queue: Dequeue 29) JavaScript Data Structures: Queue: Recap 30) JavaScript Data Structures: Recap: Lists, Stack, Queue 31) JavaScript Data Structures: Hash Table: Intro 32) JavaScript Data Structures: Hash Table: Hash Function 33) JavaScript Data Structures: Hash Table: Collisions 34) JavaScript Data Structures: Hash Table: Setup 35) JavaScript Data Structures: Hash Table: Add data 36) JavaScript Data Structures: Hash Table: Get data 37) JavaScript Data Structures: Hash Table: Get keys 38) JavaScript Data Structures: Hash Table: Get values 39) JavaScript Data Structures: Hash Table: Get all entries 40) JavaScript Data Structures: Hash Table: Recap

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?

JavaScript Data Structures (40 Part Series)

1) JavaScript Data Structures: Singly Linked List 2) JavaScript Data Structures: Singly Linked List: Setup 3 ... 38 3) JavaScript Data Structures: Singly Linked List: Push 4) JavaScript Data Structures: Singly Linked List: Pop 5) JavaScript Data Structures: Singly Linked List: Unshift 6) JavaScript Data Structures: Singly Linked List: Shift 7) JavaScript Data Structures: Singly Linked List: Get 8) JavaScript Data Structures: Singly Linked List: Set 9) JavaScript Data Structures: Singly Linked List: Insert 10) JavaScript Data Structures: Singly Linked List: Remove 11) JavaScript Data Structures: Singly Linked List: Recap 12) JavaScript Data Structures: Doubly Linked List: Intro and Setup 13) JavaScript Data Structures: Doubly Linked List: Push / Add data to the end 14) JavaScript Data Structures: Doubly Linked List: Pop / Remove data from the end 15) JavaScript Data Structures: Doubly Linked List: Unshift / Add data to the beginning 16) JavaScript Data Structures: Doubly Linked List: Shift / Remove data from the beginning 17) JavaScript Data Structures: Doubly Linked List: Get a specific node by its index 18) JavaScript Data Structures: Doubly Linked List: Set / Update a specific node 19) JavaScript Data Structures: Doubly Linked List: Insert a new node at a specific index 20) JavaScript Data Structures: Doubly Linked List: Remove a node at a specific index 21) JavaScript Data Structures: Doubly Linked List: Recap 22) JavaScript Data Structures: Stack: Intro 23) JavaScript Data Structures: Stack: Push / Add a new node 24) JavaScript Data Structures: Stack: Pop / Remove the last node 25) JavaScript Data Structures: Stack: Recap 26) JavaScript Data Structures: Queue: Intro 27) JavaScript Data Structures: Queue: Enqueue 28) JavaScript Data Structures: Queue: Dequeue 29) JavaScript Data Structures: Queue: Recap 30) JavaScript Data Structures: Recap: Lists, Stack, Queue 31) JavaScript Data Structures: Hash Table: Intro 32) JavaScript Data Structures: Hash Table: Hash Function 33) JavaScript Data Structures: Hash Table: Collisions 34) JavaScript Data Structures: Hash Table: Setup 35) JavaScript Data Structures: Hash Table: Add data 36) JavaScript Data Structures: Hash Table: Get data 37) JavaScript Data Structures: Hash Table: Get keys 38) JavaScript Data Structures: Hash Table: Get values 39) JavaScript Data Structures: Hash Table: Get all entries 40) JavaScript Data Structures: Hash Table: Recap

Posted on May 25 by:

miku86 profile

miku86

@miku86

Developer & Explorer with a passion for web development, learning and the world we live in | Need some mentoring? => https://miku86.com/mentoring

Discussion

markdown guide
 

I would like to know:

  • Does it actually make JavaScript run faster?
  • What are the use case of this in JavaScript.

Since using singly linked list in C let you use as many nodes you want to but since an array in JavaScript allows you to pop and push an split and locate and index it.

(Simply -> an array in JavaScript is a singly linked list with a lot more abilities included)

Is there any other way to bring it to use rather than "Educational" purposes?

 

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.