Beginner's Guide to Data Structures in JavaScript

As you may or may not know, data structures are the key to efficient algorithms and data management. In this article, we'll take a look at the most popular data structures, how to implement them in JavaScript, and how they can be used to your advantage.

What are data structures?

In computer science, a data structure is a data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

When I first started programming, I found data structures and algorithms to be incredibly confusing. Hopefully this article will help developers who are new to these concepts understand how to use some of the more common data structures.

Data structures are used to store data in a computer in an organized way so that it can be used efficiently. Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, trees are particularly well-suited for implementing databases, while compiler implementations usually use hash tables to look up identifiers.

Common Data Structures

There are many ways to store data, but the data structures I'll be talking about today are Arrays, Linked Lists, Hash Tables, and Trees.

Arrays

Arrays are the simplest data structure. They are just a list of items, where each item can be accessed by its index. For example, an array of numbers might look like this:

const arr = [1, 2, 3, 4, 5];

To access an item in the array, we just use its zero-index. For example, to get the third item, we would do this:

const x = arr[2]

Arrays have some drawbacks, though. They are not very flexible, and they can be slow to access items if the array is large.

Linked Lists

Linked lists are a more flexible data structure than arrays. They are made up of nodes, which are connected together like a chain. Each node contains data, and a pointer to the next node in the list. A linked list of numbers could be visualized like this:

1 -> 2 -> 3 -> 4 -> 5

To access an item in the linked list, we just follow the pointers until we reach the desired node.

To create a linked list in JavaScript, we can create a class that maintains a head pointer in the list:

class LinkedList {
  constructor() {
    this.head = null;
  }
}

We can then create nodes for our list. Each node will have a value and a pointer to the next node in the list:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

We can now create methods on our LinkedList class to add nodes to the list:

class LinkedList {
  constructor() {
    this.head = null;
  }

  // adds a node to the end of the list
  add(value) {
    const node = new Node(value);

    // if the list is empty, set the node as the head
    if (this.head === null) {
      this.head = node;
      return;
    }

    // otherwise, traverse the list until we find the last node
    let current = this.head;
    while (current.next !== null) {
      current = current.next;
    }

    // set the last node's next pointer to the new node
    current.next = node;
  }

  // removes a node from the list with the given value
  remove(value) {
    // if the list is empty, do nothing
    if (this.head === null) return;

    // otherwise, check if the head node needs to be removed
    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }

    // otherwise, traverse the list until we find the node to remove
    let current = this.head;
    while (current.next !== null) {
      if (current.next.value === value) {
        // set the next pointer of the current node to the node after the one we're removing
        current.next = current.next.next;
        return;
      }

      current = current.next;
    }
  }

  // returns true if the list contains a node with the given value, false otherwise
  contains(value) {
    // if the list is empty, return false
    if (this.head === null) return false;

    // otherwise, traverse the list until we find the value or reach the end
    let current = this.head;
    while (current !== null) {
      if (current.value === value) return true;

      current = current.next;
    }

    return false;
  }
}

We can now create a list and add nodes to it:

const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);

And we can remove nodes:

list.remove(2);

Finally, we can check if the list contains a certain value:

list.contains(3); // true
list.contains(4); // false

Linked lists are more flexible than arrays because we can easily insert and remove items without changing the rest of the list. They can also be slower to access items, though, because we have to follow the pointers.

Hash Tables

Hash tables are used to store key-value pairs. The key is used to look up the value, like a dictionary. A hash table of numbers can be visualized like this:

1 -> 2
3 -> 4
5 -> 6

To implement a hash table in JavaScript, we can use an object to store the key-value pairs. The keys can be used as the object's properties, and the values can be stored as the property values.

For example, we could store a user's name and age in a hash table like this:

const user = {
  name: "John",
  age: 30
};

To lookup a value in the hash table, we can use the key as the index:

const name = user.name; // "John"
const age = user.age; // 30

To add a new key-value pair to the hash table, we can simply create a new property on the object and assign it a value:

user.city = "New York";

To remove a key-value pair from the hash table, we can use the delete operator:

delete user.city;
``

You can also use `Map` to implement hash tables. Using JavaScript's `Map` class for hash tables has some advantages over using a standard object. For instance, `Map` keeps track of the order in which keys are added, which is important for some algorithms. It also provides some handy methods like `forEach()` and `values()` that make iteration more straightforward.

Here's how you might create a hash table with `Map`:

```javascript
const hashTable = new Map();

hashTable.set('foo', 'bar');
hashTable.set('baz', 'qux');

console.log(hashTable.get('foo')); // 'bar'
console.log(hashTable.get('baz')); // 'qux'

Just be careful not to accidentally use the same key twice. If you do, the second value will overwrite the first:

hashTable.set('baz', 'bar');

console.log(hashTable.get('baz')); // 'bar'

Hash tables are very fast to access items, because the key is used to directly look up the value. They are not very flexible, though, because the keys have to be unique.

Trees

Trees are a type of data structure that is used to store data in a hierarchical way. That is, each item has a parent and zero or more children. For example, a tree of numbers might look like this:

Each node has a value, and a link to another node (or null, if there is no child node).

To access an item in the tree, we just follow the path from the root to the desired node.

Here is an example of how this might be implemented in JavaScript:

class Node {
  constructor(value) {
    this.value = value;
    this.child = null;
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  // add a node to the tree
  addNode(value) {
    const node = new Node(value);

    // if the tree is empty, the node is the root node
    if (this.root === null) {
      this.root = node;
    } else {
      // find the correct place to add the node

      // start at the root node
      let current = this.root;

      // loop until we find an empty spot
      while (current.child) {
        current = current.child;
      }

      // add the node
      current.child = node;
    }
  }

  // remove a node from the tree
  removeNode(value) {
    if (this.root === null) {
      // tree is empty
      return;
    }

    // start at the root node
    let current = this.root;

    // keep track of the parent node
    let parent = null;

    // loop until we find the node to remove
    while (current.value !== value) {
      // update the parent node
      parent = current;

      // move to the child node
      current = current.child;

      // if there is no current node, the value is not in the tree
      if (current === null) {
        return;
      }
    }

    // if we get here, we've found the node to remove

    // if the node to remove is the root node, just set the root to null
    if (this.root === current) {
      this.root = null;
      return;
    }

    // if the node to remove is not the root node,
    // we need to find the parent node

    // if the node to remove is the parent's only child,
    // just set the parent's child to null
    if (parent.child === current) {
      parent.child = null;
      return;
    }

    // if the node to remove is the parent's first child,
    // we need to find the node's next sibling

    // start at the parent's first child
    let sibling = parent.child;

    // loop until we find the node's next sibling
    while (sibling.child !== current) {
      sibling = sibling.child;
    }

    // if we get here, we've found the node's next sibling

    // set the node's next sibling to the node's current child
    sibling.child = current.child;
  }

  // search for a node in the tree
  search(value) {
    if (this.root === null) {
      // tree is empty
      return null;
    }

    // start at the root node
    let current = this.root;

    // loop until we find the node or reach the end of the tree
    while (current.value !== value && current.child) {
      current = current.child;
    }

    // if we get here and current.value is not equal to value,
    // the node was not found

    return current;
  }
}

Here's how we would use the Tree class:

const tree = new Tree();

tree.addNode(1);
tree.addNode(2);
tree.addNode(3);
tree.addNode(4);

tree.search(3); // returns the node with value 3
tree.search(5); // returns null

tree.removeNode(3); // removes the node with value 3

Trees are very flexible, because we can easily add and remove items. They can be slower to access items, though, because we have to follow the path from the root.

Conclusion

Data structures are important in programming because they provide a way to store and retrieve data efficiently. Without data structures, it would be very difficult to write programs that could manipulate data in a useful way.

I hope you found this article helpful and that you now have a better understanding of how to use data structures in your own code.

Let me know in the comments if you found this article helpful or if you have any questions.

Be sure to follow me for more like this!

Beginner's Guide to Data Structures in JavaScript

Comments

Beginner's Guides

Beginner's Guide to Deno

More from this blog

Streamlining Chrome Extension Development with Bun

Making a Spotify “Now Playing” Widget for tmux

Transitioning to a Full-Time Job as a Developer

The Pros and Cons of Python

Take Care of That Beautiful Brain!

What are data structures?

Common Data Structures

Arrays

Linked Lists

Hash Tables

Trees

Conclusion

Command Palette

Comments

Beginner's Guides

Beginner's Guide to Deno

More from this blog

What are data structures?

Common Data Structures

Arrays

Linked Lists

Hash Tables

Trees

Conclusion