Introduction

A Linked List is a data structure. It contains nodes that are connected to each other, similar to a train that has carriages connected.

Arrays offer similar functionality, and you are better off using them in JavScript. However, as a master of your craft, knowing about Linked Lists will help you in both interviews as well as the rare situation where you’d need to implement one.

How it works

A linked list contains a head (start) node. Additional nodes are then connected one after the other. Each node contains information about the node that is connected to it.

We can insert a node at the start of the list or the end of the list.

Example

Below is an example of a Linked List implemented in JavaScript using classes.

class Node {
  key;
  data;
  next;

  constructor(key, data) {
    this.key = key;
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  head;

  constructor(head) {
    this.head = head;
  }

  display() {
    let currentNode = this.head;
    while (currentNode !== null) {
      console.log(currentNode.data);
      currentNode = currentNode.next;
    }
  }

  getData() {
    let currentNode = this.head;
    let result = '';
    while (currentNode !== null) {
      result += currentNode.data + ' ';
      currentNode = currentNode.next;
    }
    return result.trim();
  }

  insertFirst(key, data) {
    const newNode = new Node(key, data);
    newNode.next = this.head;
    this.head = newNode;
  }

  insertLast(key, data) {
    const newNode = new Node(key, data);

    let currentNode = this.head;
    let lastNode = this.head;
    while (currentNode !== null) {
      if (currentNode.next) {
        lastNode = currentNode.next;
      }
      currentNode = currentNode.next;
    }
    if (lastNode) {
      lastNode.next = newNode;
    }
  }

  reverse() {
    let previous = null;
    let current = this.head;
    let next;

    while (current != null) {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }
    this.head = previous;
  }

  length() {
    let length = 0;
    for (let current = this.head; current !== null; current = current.next) {
      length++;
    }
    return length;
  }

  find(key) {
    let current = this.head;

    // List is empty
    if (current === null) {
      return null;
    }

    while (current.key !== key) {
      // Check if the last node
      if (current.next === null) {
        return null;
        // Go to next element
      } else {
        current = current.next;
      }
    }
    return current;
  }

  delete(key) {
    let current = this.head;
    let previous = null;

    if (current === null) {
      return null;
    }

    while (current.key !== key) {
      if (current.next === null) {
        return null;
      } else {
        previous = current;
        current = current.next;
      }
    }

    // Match was found
    if (current === this.head) {
      this.head = this.head.next;
    } else {
      // Bypass the current element
      if (previous) {
        previous.next = current.next;
      }
    }

    return current;
  }
}

const node1 = new Node('a', 5);
const node2 = new Node('b', 10);
const node3 = new Node('c', 15);

node2.next = node3;
node1.next = node2;

const list = new LinkedList(node1);

list.display();
// Logs:
// 5
// 10
// 15
list.delete('b');
// Deletes 10 from the linked list
list.display();
// Logs:
// 5
// 15

Lesson task

Knowing how to implement a Linked List is beneficial to your career as a developer. We are going to dive deeper into understanding how it works.

Goal

You will work through the Linked List to get a better understanding of how it works.

Brief

Complete the Level 1 process.

NOTE: Lesson tasks do not get submitted on Moodle and are not assessed by tutors. They are mainly there for you to practise what you have learned in the lesson.

Level 1 process

  1. Work through the Linked List code above. If you are unsure of the code at any point, console.log the values to get a better understanding of what is going on.

  2. Once you have a good understanding of the Linked List, see if you can implement the very basics of one where you are simply linking Nodes.

Additional resources

tutorialspoint: Data Structure and Algorithms - Linked List

Geeksforgeeks: Linked List Data Structure

Stack Overflow: Would you ever implement a linked list in Javascript?

Tags: