Practical JavaScript Data Structures

This article builds on top of what was covered in a previous article,?“What do you really know about Variables, Data Types and Immutability in JavaScript?” .?If you are new to Javascript or still think array’s and objects are immutable, you should really consider reading the previous article before this one.

This article covers, Objects, Arrays, Hash Maps, Linked Lists, Stacks, Queues, Trees, Graphs, Hash-based Data Structures and Set-based Data Structures. However, it's too long to be published on Linkedin, so instead, we'll this article will stop after Stacks. If you'd like to read the full article check it out on medium.

Built-in Data Structures: Array (Array Object), Associative arrays (Objects), and Hashmaps

In a?previous article , we went in depth about initializing, storing and retrieving values with both primitive types and non-primitive types like array’s and objects. So this article wont repeat that beyond code comments. Instead, we’ll focus explaining how to create and traverse 2D array’s, complex objects, hashmaps, etc.

Below is code snippet, I’d like to code along to. Here we define these 3 basic types. It’s important to note that in JavaScript, arrays, associative arrays, and hash maps have different characteristics and use cases, even though the terminology might sometimes be used interchangeably.

Now lets compare and contrast each because there are a lot of simularities.

In JavaScript?arrays, are ordered, indexed collections of elements. They store elements sequentially, and each element can be accessed using its numeric index,?starting from 0. Arrays can store any type of data, such as numbers, strings, objects, or other arrays.

“Associative arrays”,?are?objects?used to store key-value pairs, where keys are strings and values can be any JavaScript data type. Unlike arrays, associative arrays are?not ordered?collections, and their elements are?accessed using keys?rather than numeric indexes.

Finally,?hash maps?using?new Map()?is a built-in data structure that stores key-value pairs, similar to associative arrays. However, Map objects offer some advantages over plain objects when used as hash maps:

• The order of keys in a Map object is preserved, unlike in plain objects.
• Keys can be of any data type, including objects or functions, not just strings.
• Map objects have a size property that indicates the number of key-value pairs, which is more efficient than calculating the size of a plain object.Basic operations: insertion, deletion, and traversal

Practical Use Cases:

Now that you have an explanation of each, lets provide some practical examples.

Example 1: Using 2D Arrays / Matrix operations, such as addition, subtraction, or multiplication.

const matrixA = [
  [1, 2],
  [3, 4],
];
const matrixB = [
  [5, 6],
  [7, 8],
];

const matrixSum = matrixA.map((row, rowIndex) =>
  row.map((value, colIndex) => value + matrixB[rowIndex][colIndex])
);

//Display the original 2D Array
console.table(matrixA);
console.table(matrixB);

// Display the new 2D Array where the values from both are added
console.table(matrixSum);        

In this example, we have 2 separate 2D Array’s and we add them together.

Example 2: Complex objects — Representing a course with multiple attributes, including a nested structure for sections and lessons.

const course = {
  id: 'C001',
  title: 'Introduction to JavaScript',
  instructor: 'John Doe',
  sections: [
    {
      id: 'S001',
      title: 'Getting Started',
      lessons: [
        { id: 'L001', title: 'What is JavaScript?' },
        { id: 'L002', title: 'Setting Up Your Environment' },
      ],
    },
    {
      id: 'S002',
      title: 'JavaScript Basics',
      lessons: [
        { id: 'L003', title: 'Variables and Data Types' },
        { id: 'L004', title: 'Functions and Scope' },
      ],
    },
  ],
};

console.log('Course:', course.title);
console.log('Instructor:', course.instructor);

course.sections.forEach((section, index) => {
  console.log(`Section ${index + 1}:`, section.title);
  
  section.lessons.forEach((lesson, lessonIndex) => {
    console.log(`  Lesson ${lessonIndex + 1}:`, lesson.title);
  });
});

const flattenedCourseData = [];

course.sections.forEach((section) => {
  section.lessons.forEach((lesson) => {
    flattenedCourseData.push({
      'Course Title': course.title,
      'Instructor': course.instructor,
      'Section Title': section.title,
      'Lesson Title': lesson.title,
    });
  });
});

console.table(flattenedCourseData);        

In this example, we use an object store all the data about a JavaScript course and we use both console.log and console.table to access the data.?console.table?displays the data in a tabular format, making it easier to read and compare lessons across sections. However it’s not as useful for deeply nested data structures or when the hierarchy is important to understand the relationships between the elements.

Example 3: Hash maps — Storing a dictionary or translation table for multiple languages.

const translations = new Map([
  ['en', { hello: 'Hello', goodbye: 'Goodbye' }],
  ['es', { hello: 'Hola', goodbye: 'Adiós' }],
  ['fr', { hello: 'Bonjour', goodbye: 'Au revoir' }],
]);

function translate(lang, key) {
  const languageTranslations = translations.get(lang);
  return languageTranslations ? languageTranslations[key] : null;
}

console.log(translate('es', 'hello')); // Output: Hola        

In this example, we are storing an 2D array of objects inside a hash map. Then we use the function translate to select a language and word (key) to translate.

Linear Data Structures (Linked Lists, Stacks, Queues):

Linked Lists

Now that we’ve given some practical examples of arrays, objects and hash maps, it’s time to go into Linked Lists. Before we begin, though, it’s important to note that things like fixed sizes or dynamically growing or shrinking are less relevant in JavaScript as it is in other languages due to how array’s work.

Here are a few general points about Linked Lists when compared to Arrays and Objects:

• Elements are not stored in contiguous memory locations.
• Insertion and deletion operations can be more efficient than in arrays, as elements don’t need to be shifted.
• Accessing elements by index is slower since it requires traversing the list.
• It can grow or shrink dynamically without the need for resizing .
• Doesn’t have a fixed size, unlike arrays.

Linked List Example:

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

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

  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }
}

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

Here are a few practical use cases of Linked Lists and I highly recommend you rewrite these as prompts for AGI using different language to fully understand how linked lists in javascript differ from in their implementation with different languages:

1. Implementing a stack or queue: Linked Lists can efficiently add or remove elements at the beginning or end without the need to shift elements, unlike arrays.
2. Efficiently inserting or deleting elements in the middle: If you have a reference to the node before the insertion or deletion point, Linked Lists can efficiently perform these operations without shifting elements.
3. Implementing a cache replacement algorithm, such as Least Recently Used (LRU): Linked Lists can be used to efficiently manage the order of elements and remove the least recently used element when necessary.
4. Creating a playlist in a media player: Linked Lists can be used to manage the order of songs and efficiently perform operations like inserting, deleting, or moving songs within the list.
5. Developing a text editor with undo/redo functionality: Linked Lists can be used to maintain a history of text changes, allowing efficient traversal through the history and quick undo/redo operations.

In these use cases, LinkedLists have better performance compared to arrays or objects when it comes to insertion, deletion, or rearrangement of elements. However, if you need random access to elements or a specific order is not important, arrays or objects might be more suitable.

Stacks

Stacks are arguable one of the most important data structure in JavaScript because the entire language itself, revolves around a?“call stack”. First, we’ll provide a basic example of a stack, then we’ll provide an example of an asynchronous call stack to help provide a practical example.

Basic Stacks Example:

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

  // Add an item to the top of the stack
  push(item) {
    this.items.push(item);
  }

  // Remove and return the item at the top of the stack
  pop() {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }
    return this.items.pop();
  }

  // Return the item at the top of the stack without removing it
  peek() {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }
    return this.items[this.items.length - 1];
  }

  // Check if the stack is empty
  isEmpty() {
    return this.items.length === 0;
  }

  // Return the number of items in the stack
  size() {
    return this.items.length;
  }

  // Empty the stack
  clear() {
    this.items = [];
  }
}

// Example usage:
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek()); // 30
stack.pop();
console.log(stack.peek()); // 20        

In this example, the Stack class uses a JavaScript array (this.items) to store its elements. The class provides methods to push, pop, and peek elements, as well as to check if the stack is empty, get the stack's size, and clear the stack.

Using JavaScript’s built-in array methods for push and pop ensures good performance, as they are implemented natively and optimized for the language. The implementation is also easy to read and understand, making the code maintainable and reusable.

Please note that JavaScript arrays are implemented as dynamic arrays, which means that they can grow and shrink automatically without needing to resize them manually. This is an advantage when using arrays for stacks, as it reduces the complexity of resizing operations.

Asynchronous Stacks Example:

In this example, we will create a simple asynchronous call stack using Promises to fetch data from a fake API. Each function will be explained in detail.

// Fake API request function that returns a Promise
function fetchData(id) {
  return new Promise((resolve, reject) => {
    setTimeout(() => {
      resolve({ id, data: `Data for ID: ${id}` });
    }, 1000);
  });
}

// Fetch multiple data points in parallel
function fetchMultipleData(ids) {
  return Promise.all(ids.map(id => fetchData(id)));
}

// Main function to execute the asynchronous calls
async function main() {
  try {
    const ids = [1, 2, 3];
    const results = await fetchMultipleData(ids);
    console.log(results);
  } catch (error) {
    console.error("Error fetching data:", error);
  }
}

main();        

1. fetchData: This function simulates an asynchronous API request using setTimeout. It returns a Promise that resolves after a 1-second delay with an object containing the requested ID and some fake data.
2. fetchMultipleData: This function takes an array of IDs as input and fetches data for each ID in parallel using the?Promise.all()?function. It returns a Promise that resolves when all the individual Promises for each ID have resolved.
3. main: This is an async function that drives the execution of the asynchronous calls. It initializes an array of IDs, calls the fetchMultipleData function, and awaits the result. Once the results are available, it logs them to the console. If an error occurs, it catches the error and logs it.