264 - Data structure implementations (Javascript)

JavaScript Data Structures and Algorithms – Data Structure Implementations

Understanding data structures is fundamental in computer science and software development. JavaScript, a versatile language, allows developers to implement a variety of data structures. In this article, we’ll explore some common data structures and provide code examples in JavaScript to help you grasp their implementation.

Arrays

Arrays are one of the most fundamental data structures in JavaScript. They allow you to store and access multiple values using indices. Here’s an example of creating and manipulating an array:


// Creating an array
const colors = ['red', 'green', 'blue'];

// Accessing elements
const firstColor = colors[0]; // 'red'

// Modifying elements
colors.push('yellow'); // Adding 'yellow' to the end
colors.pop(); // Removing the last element

Linked Lists

A linked list is a linear data structure where elements are connected in a chain. It consists of nodes, each containing data and a reference to the next node. Here’s an example of implementing a simple linked list:


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

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

  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }
}

Stacks

A stack is a collection of elements with two main operations: push (to add an element) and pop (to remove the top element). It follows the Last-In-First-Out (LIFO) principle. Here’s an example of a stack implementation:


class Stack {
  constructor() {
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    return this.items[this.items.length - 1];
  }
}

Queues

A queue is similar to a stack but follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front. Here’s a simple queue implementation:


class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(item) {
    this.items.push(item);
  }

  dequeue() {
    return this.items.shift();
  }

  front() {
    return this.items[0];
  }
}

Binary Trees

A binary tree is a hierarchical structure with nodes, each having at most two children: left and right. Here’s an example of a binary tree node and a basic tree:


class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);

Hash Tables

A hash table is a data structure that stores key-value pairs. It uses a hash function to map keys to indexes for efficient retrieval. Here’s a simple hash table implementation:


class HashTable {
  constructor() {
    this.table = new Array(100);
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this.hash(key);
    this.table[index] = value;
  }

  get(key) {
    const index = this.hash(key);
    return this.table[index];
  }
}

Conclusion

Understanding data structures and their implementations is crucial for writing efficient code and solving complex problems. JavaScript provides the flexibility to create various data structures, as shown in these examples. By mastering these foundational concepts, developers can build more powerful and optimized applications.

264 – Data structure implementations (Javascript)