Linked Lists in JavaScript

A linked list is a fundamental concept in computer science that represents a collection of items in a linear order. Unlike arrays (for example), which are built-in data structures in JavaScript, linked lists must be implemented from scratch. Each item in the linked list is called a "node," and every node has two parts: the data it holds and a reference to the next node in the list.

To create a linked list in JavaScript, you can use a class - or, as in our examples, you can create your linked list using a functional approach. Using the functional approach you might write factory functions that define the structure of the list and its nodes. A reference between nodes serves as a connector that maintains the order of the elements in the list.

Linked lists vs. arrays

Compared to arrays linked lists are dynamic data structures, which means they can easily grow or shrink in size. They can be more efficient than arrays for certain operations, such as inserting or deleting elements at the beginning or in the middle of the list, since only the references (or links) between nodes need to be updated. However, linked lists have a higher overhead compared to arrays because they store an additional reference for each node.

In the following tutorial, we'll explore how to create a simple linked list using a functional approach in JavaScript.

Create a Node factory function.

We'll create a factory function to create new nodes. Each node will have two properties: the data it holds and a reference to the next node in the list.

function createNode(data) {
  return {
    data: data,
    next: null,
  };
}

Create a LinkedList factory function

This function will be responsible for managing the linked list. It'll have a head property that represents the first node in the list and a set of utility functions for list operations.

function createLinkedList() {
  return {
    head: null,

    append: function (data) {
      const newNode = createNode(data);
      if (!this.head) {
        this.head = newNode;
        return;
      }

      let currentNode = this.head;
      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    },

    printList: function () {
      let currentNode = this.head;
      while (currentNode) {
        console.log(currentNode.data);
        currentNode = currentNode.next;
      }
    },
  };
}

Now, let's create a linked list and add some nodes to it

const myList = createLinkedList();
myList.append("Alice");
myList.append("Bob");
myList.append("Charlie");
myList.printList();

This will output:

Alice;
Bob;
Charlie;

In this JavaScript implementation, we used a functional approach and factory functions to create the linked list and its nodes. Each node holds data and a reference to the next node, connecting the nodes together in the list.

To learn more about how to work with linked lists, check out the next tutorial here.