Data Structures in JavaScript: A Comprehensive Guide

Introduction to Data Structures

Welcome to this exploration of JavaScript data structures. This chapter will guide you step-by-step through the fundamental concepts and practical applications of data structures in programming, specifically within the JavaScript ecosystem. We will begin by examining the built-in data structures provided by JavaScript, including sets, maps, arrays, and objects. Subsequently, we will delve into the creation and utilization of custom data structures, such as stacks, queues, trees (including binary search trees), priority queues, heaps, and graphs.

This course is designed to be thorough and detailed, explaining the problems each data structure is designed to solve and equipping you with the skills to build and manipulate these structures independently.

Prerequisites:

To maximize your learning experience in this chapter, a foundational understanding of JavaScript algorithms and time complexity is recommended. Familiarity with these concepts, perhaps from a prior course on JavaScript algorithms, will be beneficial.

Let’s embark on this journey to understand and master data structures in JavaScript.

What are Data Structures and Why are They Important?

The fundamental question we must address is: What exactly are data structures in programming, and why are they essential?

Data structures are the mechanisms within your code that enable you to effectively manage data. In essence, they are the tools you use to:

• Store data.
• Retrieve data.
• Delete data.
• Manage data in general.

In JavaScript, and across most programming languages, common examples of data structures include:

• Arrays
• Objects
• Maps
• Sets

These are the foundational building blocks for organizing and manipulating information within your programs.

To illustrate, consider these JavaScript examples:

• Arrays: Used for storing ordered lists of data, such as a sequence of numbers or strings.

  [10, 20, 30, 40, 50] // An array of numbers
  ["apple", "banana", "cherry"] // An array of strings

• Objects: Used for grouping related data together, often as key-value pairs. For instance, representing a person with their name and age.

  {
    name: "Alice",
    age: 30
  } // An object representing a person

• Maps: Similar to objects but offer more flexibility, especially in key types. (We will explore maps in detail later).

• Sets: Collections of unique values, useful when you need to ensure no duplicates exist.

  new Set([1, 2, 2, 3, 4, 4, 5]) // A set will only store unique values: {1, 2, 3, 4, 5}

You will encounter data structures analogous to these in virtually every programming language. They are the universal tools for data management in the world of coding.

The Necessity of Diverse Data Structures

Why do we require such a variety of data structures? The answer lies in the nature of programs and the tasks they perform. Programs are inherently about doing something, and that “something” invariably involves working with data. This data could be:

• Input data that the program receives.
• Intermediate results generated during computation.
• Output data that the program produces.

Different tasks demand different ways of managing data. Consider these common scenarios:

• Ordered Lists with Duplicates: Sometimes, you need to maintain a list where the order of items is crucial, and duplicate entries are acceptable or even desired.
• Unordered Unique Values: In other cases, the order might be irrelevant, and you might need to ensure that all values are unique, without any repetitions.
• Key-Value Pair Mappings: You might need to associate values with specific identifiers (keys), creating key-value pairs. These pairs could be ordered or unordered, depending on the requirements.

For each of these use cases, different data structures offer optimal solutions.

Arrays for Ordered Lists

Arrays are ideal when you need ordered lists of data where duplicate values are permitted.

Ordered List: In the context of data structures, “ordered” signifies that the sequence of elements is maintained based on their insertion order. It does not necessarily imply that the elements are sorted in ascending or descending order based on their values.

In JavaScript, arrays are created using square brackets []:

[10, 5, 25, 15, 30] // An array in JavaScript

It’s crucial to understand that in this context, “ordered” means the insertion order is preserved. For instance, in the example above, 5 will always be the second element, and its position will not change unless you explicitly modify the array. This order is fundamental to how arrays function.

Sets for Unique Values

If the order of data is not important and you require unique values only, a set is the appropriate choice.

Sets in JavaScript are created using the Set constructor:

const mySet = new Set();
mySet.add(10);
mySet.add(20);
mySet.add(10); // Adding a duplicate value - will be ignored

Sets inherently ensure uniqueness; any attempt to add a duplicate value will be disregarded.

Objects and Maps for Key-Value Pairs

When you need to work with key-value pairs, JavaScript offers both objects and maps. Objects are a fundamental part of JavaScript and allow you to group data with named properties (keys).

const person = {
  firstName: "Maximilian",
  age: 31
}; // An object with key-value pairs

You can assign keys (identifiers) of your choice and retrieve the associated values using these keys.

Maps in JavaScript serve a similar purpose to objects but offer some distinct advantages and differences, which we will explore in more detail later in this chapter.

Focus on Custom Data Structures

This chapter’s primary focus will be on custom data structures. These are data structures that you, as a developer, build yourself, typically based on the built-in data structures of the language (like arrays and objects). Custom data structures enhance and extend the functionalities of these built-in structures to meet specific needs.

To effectively delve into custom data structures, we will first thoroughly examine the built-in data structures in JavaScript. Understanding the fundamentals of arrays, sets, objects, and maps is crucial because custom data structures are often built upon these foundations. This foundational knowledge will empower you to grasp how custom structures are derived and how they function.

Following our exploration of built-in data structures, we will transition to examining and constructing custom data structures. We will begin with a practical example of a custom data structure to solidify your understanding and demonstrate the power of building your own data management tools.

Built-in Data Structures in Detail

Let’s now delve into a detailed examination of JavaScript’s built-in data structures, starting with arrays.

Arrays: Ordered Lists in Depth

Arrays are fundamental data structures for managing lists of data. In JavaScript, arrays are created using the square bracket notation []. They are essentially ordered lists of comma-separated data.

const numbers = [1, 3, 2, 4, 5]; // Example array

Arrays in JavaScript possess several key characteristics:

• Insertion Order is Preserved: JavaScript remembers the order in which elements are added to the array. The element 3 in the example above will always be the second element, unless explicitly moved or removed. This order is maintained consistently.

• Index-Based Access: Elements in an array are accessed using an index, which represents the element’s position in the array. Indices start at 0.

  Index: In the context of arrays (and other ordered data structures), an index is a numerical value that denotes the position of an element within the structure. Indices typically start from zero for the first element.

• Iterable: Arrays are iterable, meaning you can easily loop through their elements using constructs like the for...of loop. This allows for straightforward iteration over all values in the array.

  Iterable: An iterable object is an object that can be looped over, meaning its elements can be accessed sequentially, often using a for...of loop in JavaScript. Arrays, Sets, and Maps in JavaScript are examples of iterable objects.

• Dynamic Size: Arrays in JavaScript are dynamic. Their size adjusts automatically as you add or remove elements. You don’t need to predefine the array’s length. This is a significant advantage compared to some other programming languages where array sizes are fixed.

  Dynamic Array: A dynamic array (also known as a resizable array or growable array) is an array that can automatically resize itself as elements are added or removed. Unlike static arrays, dynamic arrays do not have a fixed size defined at the time of creation.

  This dynamic nature simplifies development and memory management as JavaScript handles the resizing process behind the scenes.

• Duplicate Values Allowed: Arrays can contain duplicate values. You can have multiple instances of the same value within a single array.

• Mixed Data Types: JavaScript arrays are flexible enough to hold elements of mixed data types. You can combine numbers, strings, objects, and even nested arrays within the same array.

  const mixedArray = [10, "hello", { name: "John" }, [1, 2, 3]]; // Array with mixed data types

Performance Considerations with Arrays

Despite their versatility, arrays have a potential downside: deletion and searching for elements can be less performant in certain scenarios.

• Deletion Overhead: When you delete an element from an array (especially from the middle or beginning), JavaScript might need to shift subsequent elements to fill the gap. This shifting process can be computationally intensive, especially for large arrays.
• Search Efficiency: Finding a specific element in an array (when you don’t know its index) often requires iterating through the array from the beginning until the element is found. This is known as a linear search and can be time-consuming for large arrays.

Let’s illustrate these points with a practical code example.

Array Code Example: Exploring Functionality

Consider a simple JavaScript setup with an index.html file (containing a script import to app.js) and an app.js file. We will use the browser’s JavaScript console to observe the behavior of arrays.

// app.js
const names = ["Max", "Manu", "Julie"];

// Mixed types and duplicates are allowed
names.push(25);
names.push(["sports", "cooking"]);
names.push("Max");

console.log(names); // Output: ["Max", "Manu", "Julie", 25, ["sports", "cooking"], "Max"]

// Accessing element by index
console.log(names[1]); // Output: "Manu" (index starts at 0)

// Iterating through an array
for (const name of names) {
  console.log(name);
}
// Output:
// Max
// Manu
// Julie
// 25
// ["sports", "cooking"]
// Max

// Dynamic length adjustment
console.log(names.length); // Output: 6 (initial length)
names.push("Julie");
console.log(names.length); // Output: 7 (length after push)

// Finding element index
const julieIndex = names.findIndex(element => element === "Julie");
console.log("Index of Julie:", julieIndex); // Output: Index of Julie: 2

// Deleting element using splice
names.splice(2, 1); // Remove 1 element starting from index 2 (Julie)
console.log(names); // Output: ["Max", "Manu", 25, ["sports", "cooking"], "Max", "Julie"]

In this example, we demonstrate:

• Array creation and initialization.
• Mixing data types and adding duplicates.
• Accessing elements by index.
• Iteration using for...of.
• Dynamic length adjustment with push().
• Finding an element’s index using findIndex().
• Deleting elements using splice().

The findIndex() method iterates through the array until it finds an element that satisfies the provided condition (in this case, being equal to “Julie”). Similarly, splice() modifies the array by removing elements and potentially shifting subsequent elements. These operations can become less efficient as the array size grows, especially for deletions in the middle of large arrays.

Sets: Collections of Unique Values

Now, let’s explore sets, another fundamental built-in data structure in JavaScript. Sets are designed to store collections of unique values. Unlike arrays, sets do not allow duplicate elements.

Sets are created using the Set constructor:

const idSet = new Set();
idSet.add("abc");
idSet.add(123);
idSet.add("abc"); // Duplicate - will be ignored

Key characteristics of sets include:

• Uniqueness of Elements: Sets inherently store only unique values. If you attempt to add a value that is already present in the set, it will be ignored.
• No Insertion Order Guarantee: Unlike arrays, sets do not guarantee to maintain the insertion order of elements. While in some JavaScript implementations, the order might appear to be preserved, it is not a reliable feature, and you should not depend on it.
• No Index-Based Access: You cannot access elements in a set using an index. Sets are not designed for index-based retrieval.
• Iterable: Sets are iterable, allowing you to loop through their elements using for...of. However, the order of iteration is not guaranteed to be the insertion order.
• Dynamic Size: Like arrays, sets are dynamic and adjust their size automatically as elements are added or removed.
• Efficient Element Lookup and Deletion: Sets are optimized for efficient checking of whether a value exists in the set and for deleting elements. These operations are generally faster in sets compared to arrays, especially for large collections.

Performance Advantages of Sets

Sets offer performance advantages in specific scenarios compared to arrays:

• Faster Lookups (Existence Checks): Checking if a value is present in a set is typically faster than searching for a value in an array, especially for large collections. Sets often use hash-based implementations internally, which allow for near-constant time complexity for lookups on average.
• Faster Deletions: Deleting elements from a set is generally more efficient than deleting elements from an array, as sets do not require shifting elements to fill gaps after deletion.

Set Code Example: Exploring Functionality

// app.js
const uniqueIds = new Set();

uniqueIds.add("abc");
uniqueIds.add(1);
uniqueIds.add("bb2");
uniqueIds.add(1); // Duplicate - ignored

console.log(uniqueIds); // Output: Set(3) {"abc", 1, "bb2"} (Order may vary)

// Iterating through a set
for (const id of uniqueIds) {
  console.log(id);
}
// Output: (Order may vary)
// abc
// 1
// bb2

// Checking for element existence
console.log(uniqueIds.has("abc")); // Output: true
console.log(uniqueIds.has("xyz")); // Output: false

// Deleting an element
uniqueIds.delete("bb2");
console.log(uniqueIds); // Output: Set(2) {"abc", 1} (bb2 removed)

In this example, we observe:

• Set creation using new Set().
• Adding elements using add(), noting that duplicates are ignored.
• Iteration using for...of (order not guaranteed).
• Checking for element existence using has().
• Deleting elements using delete().

The key takeaway is that sets are optimized for managing collections of unique values where order is not a primary concern and efficient lookups and deletions are important.

Arrays vs. Sets: A Comparative Summary

When to Choose Sets over Arrays:

Consider using sets instead of arrays when:

• Uniqueness is paramount: You must ensure that all values in your collection are unique.
• Order is not important: You don’t rely on the order of elements.
• Frequent lookups or deletions: You perform many operations to check if a value exists or to remove values from the collection, especially in large datasets.

However, arrays remain the go-to data structure for general-purpose lists in JavaScript due to their flexibility and ordered nature.

Objects: Key-Value Pairs with Properties and Methods

Moving on, let’s explore objects in JavaScript. Objects are fundamental for representing structured data as unordered collections of key-value pairs. They are created using curly braces {}.

const personObject = {
  name: "Alice",
  age: 30,
  hobbies: ["reading", "hiking"],
  greet: function() {
    console.log("Hello, my name is " + this.name);
  }
}; // Example object

Objects in JavaScript have several important characteristics:

• Unordered Key-Value Pairs: Objects store data as key-value pairs. The order of these pairs is not guaranteed. You should not rely on the order in which properties are defined.

• Key-Based Access: You access values in an object using their keys (property names). Keys are typically strings, but can also be Symbols or Numbers.

• Not Directly Iterable (For…in Loop): Objects are not directly iterable with for...of loops (unlike arrays, sets, and maps). However, you can iterate over the keys of an object using the for...in loop or methods like Object.keys().

• Unique Keys: Keys within an object must be unique. If you define the same key multiple times, the last definition will overwrite any previous ones. Values, however, can be duplicated.

• Keys as Strings, Numbers, or Symbols: Property keys in objects must be strings, numbers, or Symbols. They cannot be objects or arrays themselves.

• Methods as Properties: Objects can contain methods, which are functions associated with the object. Methods can operate on the object’s properties and provide functionality related to the object’s data.

• Prototypes and Constructor Functions: JavaScript objects have a prototype mechanism, and you can create objects using constructor functions. These are advanced features that extend the capabilities of objects beyond simple data storage.

  Prototype (in JavaScript): In JavaScript, every object has a prototype, which is another object from which it inherits properties and methods. Prototypes enable inheritance and delegation in JavaScript. Constructor Function (in JavaScript): A constructor function is a function used to create and initialize objects. When used with the new keyword, it creates a new object instance and sets up its initial properties and prototype.

Objects as More Than Just Data Stores

Objects in JavaScript are more than just simple data containers. They can encapsulate both data (properties) and behavior (methods), making them powerful tools for structuring code and representing entities.

Object Code Example: Exploring Functionality

// app.js
const person = {
  firstName: "Max",
  age: 31,
  hobbies: ["sports", "cooking"],
  greet: function() {
    console.log("Hi, I am " + this.firstName);
  }
};

console.log(person);
// Output: {firstName: "Max", age: 31, hobbies: Array(2), greet: ƒ}

// Accessing properties
console.log(person.firstName); // Output: "Max" (dot notation)
console.log(person["age"]);     // Output: 31 (bracket notation)

// Calling a method
person.greet(); // Output: "Hi, I am Max"

// Adding new property
person.lastName = "Schwarzmüller";
console.log(person);
// Output: {firstName: "Max", age: 31, hobbies: Array(2), greet: ƒ, lastName: "Schwarzmüller"}

// Deleting a property
delete person.age;
console.log(person);
// Output: {firstName: "Max", hobbies: Array(2), greet: ƒ, lastName: "Schwarzmüller"}

In this example, we demonstrate:

• Object creation using {} with key-value pairs.
• Accessing properties using dot notation (.) and bracket notation ([]).
• Defining and calling a method (greet()).
• Adding new properties dynamically.
• Deleting properties using the delete operator.

Objects are versatile and widely used for grouping related data and functionalities in JavaScript. They are central to many programming paradigms, including object-oriented programming.

Maps: Ordered Key-Value Pairs with Flexible Keys

Finally, let’s examine maps in JavaScript. Maps, like objects, are used for storing key-value pairs. However, maps offer some important distinctions from objects. Maps are created using the Map constructor.

const resultMap = new Map();
resultMap.set("average", 1.53);
resultMap.set("lastResult", null);
resultMap.set({ name: "Germany", population: 82000000 }, 0.89); // Object as key

Key characteristics of maps include:

• Ordered Key-Value Pairs (Insertion Order): Maps maintain the insertion order of key-value pairs. When you iterate through a map, you will get the entries in the same order they were added. This is a key difference from objects, where order is not guaranteed.
• Key Flexibility: In maps, keys can be of any data type, including primitive values (strings, numbers, booleans, symbols, null, undefined) and reference values (objects, arrays, functions). This is a significant advantage over objects, where keys are typically limited to strings and Symbols.
• Iterable: Maps are iterable, and iterating over a map using for...of yields key-value pairs in the insertion order.
• Pure Data Storage: Maps are primarily designed for data storage. Unlike objects, they are not intended to have methods attached to them in the same way. While you can store functions as values in a map, they are not considered methods of the map itself. Maps are focused on being efficient key-value stores.

Maps vs. Objects: Key Differences

When to Choose Maps over Objects:

Consider using maps instead of objects when:

• Key order matters: You need to preserve the order in which key-value pairs are added.
• You need keys that are not strings or Symbols: You want to use objects, arrays, or other non-primitive values as keys.
• Performance for lookups and deletions is critical: You are working with large collections and need efficient key-based operations.
• Pure data storage is the primary goal: You need a data structure focused solely on storing and retrieving key-value pairs without the need for methods attached to the structure itself.

However, objects remain more common in JavaScript due to their versatility and ease of use, especially when representing entities with both data and associated behavior (methods).

Map Code Example: Exploring Functionality

// app.js
const results = new Map();

results.set("average", 1.53);
results.set("lastResult", null);
const germany = { name: "Germany", population: 82000000 };
results.set(germany, 0.89); // Object as key

console.log(results);
// Output: Map(3) {"average" => 1.53, "lastResult" => null, {…} => 0.89} (Order preserved)

// Iterating through a map
for (const [key, value] of results) {
  console.log(key, value);
}
// Output: (Order preserved)
// average 1.53
// lastResult null
// {name: "Germany", population: 82000000} 0.89

// Getting value by key
console.log(results.get("average")); // Output: 1.53
console.log(results.get("nonExistentKey")); // Output: undefined

// Deleting by key
results.delete(germany);
console.log(results);
// Output: Map(2) {"average" => 1.53, "lastResult" => null} (Germany entry removed)

// Note on object keys: using the exact same object reference is crucial for deletion and retrieval
const germany2 = { name: "Germany", population: 82000000 }; // Different object reference
results.delete(germany2); // Will not delete the original germany entry
console.log(results); // Output: Map(2) {"average" => 1.53, "lastResult" => null} (Still no change)

In this example, we demonstrate:

• Map creation using new Map().
• Adding key-value pairs using set().
• Using an object as a key.
• Iteration using for...of, yielding key-value pairs in insertion order.
• Retrieving values using get().
• Deleting entries using delete(), emphasizing the importance of using the exact same object reference when using objects as keys.

Understanding the nuances of arrays, sets, objects, and maps is crucial for effective data management in JavaScript. Choosing the right data structure for a given task can significantly impact performance and code clarity.

Weak Sets and Weak Maps: Memory Management Considerations

Before moving on to custom data structures, it’s important to briefly touch upon weak sets and weak maps in JavaScript. These are variations of sets and maps that introduce a concept called “weak referencing.”

Weak Reference: A weak reference is a reference to an object that does not prevent the object from being garbage collected if there are no other strong references to it.

The key difference between Set/Map and WeakSet/WeakMap lies in how they handle garbage collection.

Garbage Collection: Garbage collection is an automatic memory management process in programming languages like JavaScript. It reclaims memory occupied by objects that are no longer referenced or reachable by the program, freeing up resources.

• Weak Sets: In a WeakSet, values are held weakly. If an object stored in a WeakSet is no longer referenced from anywhere else in your program (except by the WeakSet itself), it becomes eligible for garbage collection. Once garbage collected, the WeakSet automatically removes the object from its collection. WeakSet can only store objects.
• Weak Maps: In a WeakMap, keys are held weakly. If a key in a WeakMap is an object and that object is no longer referenced elsewhere, it becomes eligible for garbage collection. When the key object is garbage collected, the corresponding key-value pair is automatically removed from the WeakMap. WeakMap keys must be objects, but values can be of any type.

Memory Management Advantages:

Weak sets and weak maps can offer memory management advantages in specific scenarios, particularly in performance-intensive applications or when building frameworks. They allow JavaScript’s garbage collector to reclaim memory more aggressively when objects are no longer actively used, even if they are still present in a WeakSet or WeakMap.

Limitations:

• Weak Sets: Can only store objects.
• Weak Maps: Keys must be objects.
• No Iteration: Weak sets and weak maps are not iterable. You cannot directly loop through their contents because the presence of an object in them is dependent on garbage collection, which is non-deterministic.
• No size Property: They do not have a size property because the number of elements can change unpredictably due to garbage collection.

Use Cases:

Weak sets and weak maps are often used in scenarios like:

• Associating metadata with objects without preventing garbage collection: You can use a WeakMap to store information related to objects without keeping the objects alive if they are otherwise no longer needed.
• Implementing caches: You can create caches where entries are automatically removed when the keys are no longer in use.
• Framework development: In scenarios where fine-grained memory control is important.

Practical Relevance in This Course:

While weak sets and weak maps are valuable tools for specific use cases, they are not essential for most common application development scenarios. For the purposes of this course and for many typical JavaScript applications, you may not frequently need to use them. However, understanding their existence and memory management implications is beneficial for a comprehensive knowledge of JavaScript data structures.

Introduction to Custom Data Structures: The Linked List

Having explored JavaScript’s built-in data structures, we now transition to the core focus of this chapter: custom data structures. We will begin by constructing our first custom data structure: the linked list.

Custom Data Structure: A custom data structure is a data structure that is not built into a programming language but is created by developers using the language’s existing features, often by combining and extending built-in data structures.

Understanding the Linked List

A linked list, as the name suggests, is a list data structure. It serves a similar purpose to an array in that it stores a sequence of values. However, linked lists differ significantly from arrays in their underlying structure and how they manage data.

In a linked list:

• No Indices: Unlike arrays, linked lists do not use indices to access elements.

• Elements (Nodes) and Pointers: Each element in a linked list, often called a node, stores not only its value but also a pointer (a reference) to the next element in the sequence. This “pointer” is the “link” in “linked list.”

  Node (in Linked List): A node is a fundamental unit in a linked list. Each node typically contains two parts: the data element (value) being stored and a pointer (reference) to the next node in the list. Pointer (in Data Structures): A pointer, in the context of data structures, is a reference or link from one node to another. In a linked list, pointers are used to connect nodes sequentially, forming the list structure.

• Sequential Linking: Nodes are linked together in a sequential manner, forming a chain. Each node points to the next one, creating a linear progression through the list.

• Head and Tail: To manage a linked list efficiently, we typically keep track of two special nodes:

  • Head: The first node in the linked list. It is the entry point to the list.

  Head (of Linked List): The head is the first node in a linked list. It serves as the starting point for traversing the list and is often used to reference the entire list.

  • Tail: The last node in the linked list. Its “next” pointer typically points to null, indicating the end of the list.

  Tail (of Linked List): The tail is the last node in a linked list. Its “next” pointer usually points to null or nothing, signifying the end of the list.

Visual Representation:

Imagine a linked list as a chain of paperclips. Each paperclip represents a node, holding a value (e.g., a number or a string). Each paperclip is also connected to the next paperclip in the chain (the pointer). The first paperclip in the chain is the “head,” and the last one is the “tail.”

Head --> [Value: 5, Next: Pointer to Node 2] --> [Value: "Hi", Next: Pointer to Node 3] --> [Value: 8, Next: Pointer to Node 4] --> [Value: 2, Next: null] <-- Tail

In this representation:

• Head points to the first node.
• Each node contains a Value and a Next pointer.
• The Next pointer of each node points to the subsequent node in the list, except for the last node (tail), whose Next pointer is null.

Why Use a Linked List? Advantages

Linked lists were historically significant and continue to offer specific advantages in certain scenarios:

• Dynamic Resizing and Memory Management (Historically): In older programming environments where memory was more constrained and array sizes were fixed, linked lists were valuable because they could dynamically resize. You didn’t need to pre-allocate a fixed size; the list could grow or shrink as needed. However, in JavaScript, built-in arrays are already dynamic, so this historical advantage is less critical in JavaScript specifically.
• Efficient Insertion and Deletion at the Beginning/End: Linked lists excel at insertions and deletions, especially at the beginning of the list. Inserting at the beginning of a linked list is very efficient (constant time complexity). In contrast, inserting at the beginning of an array can be less efficient as it may require shifting existing elements.
• Flexibility in List Resizing: Linked lists are inherently flexible in terms of resizing. Adding or removing nodes is straightforward and does not typically involve moving large blocks of memory as might occur with arrays in some languages.

When to Consider Linked Lists:

While arrays are generally more versatile and often the default choice for lists in JavaScript, consider using a linked list if:

• Frequent Insertions/Deletions at the Beginning: Your application involves a high frequency of adding or removing elements at the beginning of a list, and performance in these operations is critical.
• Dynamic List Size and Memory Efficiency: In scenarios where memory efficiency and dynamic resizing are paramount, although JavaScript’s dynamic arrays already address many of these concerns.

It’s important to note that for many typical JavaScript programming tasks, built-in arrays provide sufficient performance and functionality. Linked lists are more specialized and are often chosen when their specific strengths align with the application’s requirements.

Implementing a Custom Linked List in JavaScript

Now, let’s put theory into practice and build our own custom linked list data structure in JavaScript. We will create a LinkedList class that encapsulates the logic and behavior of a linked list.

Class-Based Implementation

We will use a class to define our LinkedList data structure. Classes in JavaScript provide a blueprint for creating objects (instances) that share common properties and methods. This approach aligns with how built-in data structures like Set and Map are also conceptually class-based.

class LinkedList {
  constructor() {
    // Constructor to initialize an empty linked list
    this.head = null; // Initially, the head is null (empty list)
    this.tail = null; // Initially, the tail is also null
  }

  // Methods will be added here for operations like append, prepend, delete, etc.
}

In the constructor of our LinkedList class:

• We initialize this.head to null. This indicates that initially, the linked list is empty, and there is no first node.
• We initialize this.tail to null. Similarly, there is no last node in an empty list.

We will now add methods to our LinkedList class to implement core linked list operations.

append(value): Adding to the End

The append(value) method will add a new node with the given value to the end of the linked list.

class LinkedList {
  // ... constructor ...

  append(value) {
    const newNode = { value: value, next: null }; // Create a new node

    if (!this.tail) { // If the list is empty (no tail)
      this.head = newNode; // New node becomes the head
      this.tail = newNode; // And also the tail (single node list)
    } else { // If the list is not empty
      this.tail.next = newNode; // Link current tail's 'next' to the new node
      this.tail = newNode;      // Update tail to be the new node
    }
  }
}

In the append method:

1. Create a New Node: We create a newNode object. Each node is an object with two properties:

   • value: Stores the actual data value passed to the append method.
   • next: Initially set to null because when appending, the new node becomes the last node, and it doesn’t point to any subsequent node (yet).

2. Handle Empty List Case: We check if this.tail is falsy (e.g., null). If it is, it means the linked list is currently empty. In this case:

   • The newNode becomes both the head and the tail of the list, as it’s the only node.

3. Handle Non-Empty List Case: If this.tail is truthy (meaning the list is not empty):

   • We set this.tail.next = newNode. This is crucial: we take the current tail node and update its next property to point to the newNode. This links the new node to the end of the existing list.
   • We update this.tail = newNode. Now, the newNode becomes the new tail of the linked list, as it’s the last node after appending.

toArray(): Converting to Array for Inspection

To easily inspect the contents of our linked list and verify its functionality, let’s add a toArray() method. This method will convert the linked list into a standard JavaScript array.

class LinkedList {
  // ... constructor, append ...

  toArray() {
    const elements = []; // Initialize an empty array
    let currentNode = this.head; // Start from the head node

    while (currentNode) { // Loop as long as there is a current node
      elements.push(currentNode.value); // Add the current node's value to the array
      currentNode = currentNode.next; // Move to the next node in the list
    }

    return elements; // Return the array of values
  }
}

In the toArray method:

1. Initialize an Array: We create an empty array elements to store the values from the linked list.
2. Start at the Head: We initialize currentNode to this.head. This is our starting point for traversing the linked list.
3. Traverse the List: We use a while loop that continues as long as currentNode is truthy (i.e., not null). Inside the loop:
   • elements.push(currentNode.value): We extract the value from the currentNode and add it to the elements array.
   • currentNode = currentNode.next: We move to the next node in the list by setting currentNode to currentNode.next. This effectively advances us along the chain of nodes.
4. Return Array: Once the loop finishes (when currentNode becomes null, indicating the end of the list), we return the elements array, which now contains all the values from the linked list in order.

Testing append() and toArray()

Let’s test our LinkedList class and its append() and toArray() methods:

// app.js
class LinkedList {
  // ... (LinkedList class implementation from above) ...
}

const myList = new LinkedList();
myList.append(10);
myList.append("Hello");
myList.append(true);
myList.append({ name: "Object" });

console.log(myList.toArray());
// Output (expected): [10, "Hello", true, { name: "Object" }]

When you run this code, you should see an array in the console that reflects the values you appended to the linked list, in the order they were appended. This confirms that our append() and toArray() methods are working correctly.

prepend(value): Adding to the Beginning

Now, let’s implement prepend(value) to add a new node to the beginning of the linked list.

class LinkedList {
  // ... constructor, append, toArray ...

  prepend(value) {
    const newNode = { value: value, next: this.head }; // New node points to current head

    this.head = newNode; // New node becomes the new head

    if (!this.tail) { // If the list was empty (no tail before prepending)
      this.tail = newNode; // New node also becomes the tail (single node list)
    }
  }
}

In the prepend method:

1. Create a New Node: We create a newNode object. The key difference here is in setting the next property:

   • next: this.head: We set the next pointer of the newNode to be the current this.head. This means the new node will point to what was previously the first node in the list.

2. Update Head: this.head = newNode: We update this.head to be the newNode. This makes the newNode the new first node of the linked list.

3. Handle Empty List Case: We check if this.tail is falsy (e.g., null). If it is, it means the list was empty before we prepended the node. In this case, the newNode also becomes the tail because it’s now the only node in the list.

Testing prepend()

Let’s test prepend() along with append():

// app.js
class LinkedList {
  // ... (LinkedList class implementation including prepend) ...
}

const myList = new LinkedList();
myList.append(2);
myList.append(3);
myList.prepend(1); // Prepend at the beginning
myList.prepend(0); // Prepend again

console.log(myList.toArray());
// Output (expected): [0, 1, 2, 3]

When you run this, you should see that the values prepended using prepend() appear at the beginning of the array representation, confirming that prepend() is working as expected.

delete(value): Removing Nodes by Value

The delete(value) method will remove all nodes from the linked list that have a value equal to the given value.

class LinkedList {
  // ... constructor, append, toArray, prepend ...

  delete(value) {
    if (!this.head) { // If the list is empty, nothing to delete
      return;
    }

    // Delete all head nodes that match the value
    while (this.head && this.head.value === value) {
      this.head = this.head.next; // Move head to the next node
    }

    let currentNode = this.head;
    while (currentNode && currentNode.next) {
      if (currentNode.next.value === value) {
        currentNode.next = currentNode.next.next; // Skip the node to be deleted
      } else {
        currentNode = currentNode.next; // Move to the next node
      }
    }

    // Update tail if the last node was deleted
    if (this.tail && this.tail.value === value) {
      currentNode = this.head;
      if (!currentNode) { // If the list became empty after deleting tail
        this.tail = null; // Tail should be null
      } else {
        while (currentNode.next) { // Traverse to find the new tail
          currentNode = currentNode.next;
        }
        this.tail = currentNode; // Set the last non-deleted node as the new tail
      }
    }
  }
}

In the delete method:

1. Handle Empty List: If this.head is falsy, the list is empty, so there’s nothing to delete. We simply return.

2. Delete Head Nodes: We use a while loop to handle cases where one or more head nodes have the value to be deleted. As long as this.head exists and its value matches the value to delete, we update this.head to this.head.next, effectively removing the current head node.

3. Delete Non-Head Nodes: We use another while loop to traverse the rest of the list (starting from the new head, which might have changed in the previous step). In this loop:

   • We check currentNode.next.value === value. If the value of the next node matches the value to delete, we perform the deletion: currentNode.next = currentNode.next.next. This is the core deletion step: we bypass the node to be deleted by making the current node’s next pointer point to the node after the one to be deleted.
   • If the next node’s value does not match, we simply move to the next node: currentNode = currentNode.next.

4. Update Tail: After deleting nodes, we need to update the tail pointer, especially if the last node(s) were deleted.

   • We check if this.tail exists and its value matches the value to delete. If so, it means the tail node (or possibly multiple tail nodes) was deleted.
   • We handle two cases:
     • If the list becomes empty after deleting the tail (i.e., !currentNode after setting currentNode = this.head), we set this.tail = null.
     • Otherwise, we need to find the new tail. We traverse the list from the head until we reach the last node (the one whose next is null). We then set this.tail to this last non-deleted node.

Testing delete()

Let’s test the delete() method:

// app.js
class LinkedList {
  // ... (LinkedList class implementation including delete) ...
}

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

myList.delete(2); // Delete all nodes with value 2
console.log(myList.toArray());
// Output (expected): [1, 3, 4]

When you run this, you should see that all nodes with the value 2 have been removed from the linked list, and the remaining nodes are in their original order.

find(value): Searching for a Value

The find(value) method will search for the first node in the linked list that has a value equal to the given value and return that node. If no such node is found, it should return null.

class LinkedList {
  // ... constructor, append, toArray, prepend, delete ...

  find(value) {
    if (!this.head) { // Empty list, nothing to find
      return null;
    }

    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.value === value) {
        return currentNode; // Value found, return the node
      }
      currentNode = currentNode.next; // Move to the next node
    }

    return null; // Value not found in the list
  }
}

In the find method:

1. Handle Empty List: If this.head is falsy, the list is empty, so we return null as nothing can be found.

2. Traverse and Search: We start from currentNode = this.head and traverse the list using a while loop.

   • Inside the loop, we check currentNode.value === value. If the value of the current node matches the value we are searching for, we have found it. We immediately return currentNode, which is the node object itself.
   • If the value does not match, we move to the next node: currentNode = currentNode.next.

3. Value Not Found: If the loop completes without finding a matching value (i.e., currentNode becomes null), it means the value is not in the list. In this case, we return null to indicate that the value was not found.

Testing find()

Let’s test the find() method:

// app.js
class LinkedList {
  // ... (LinkedList class implementation including find) ...
}

const myList = new LinkedList();
myList.append("apple");
myList.append("banana");
myList.append("cherry");

const bananaNode = myList.find("banana");
const grapeNode = myList.find("grape");

console.log(bananaNode); // Output (expected): {value: "banana", next: {…}} (Node object)
console.log(grapeNode);  // Output (expected): null (Not found)

When you run this, you should see that bananaNode is logged as an object representing the node with the value “banana”, and grapeNode is logged as null, confirming that find() correctly locates existing values and returns null for non-existent ones.

insertAfter(value, afterValue): Inserting After a Specific Value

The insertAfter(value, afterValue) method will insert a new node with the given value immediately after the first node in the list that has a value equal to afterValue. If afterValue is not found in the list, the new node will not be inserted.

class LinkedList {
  // ... constructor, append, toArray, prepend, delete, find ...

  insertAfter(value, afterValue) {
    const existingNode = this.find(afterValue); // Find the node after which to insert

    if (existingNode) { // If the 'afterValue' node is found
      const newNode = { value: value, next: existingNode.next }; // New node points to existing node's next
      existingNode.next = newNode; // Existing node's next now points to the new node
    }
    // If 'afterValue' node is not found, do nothing (no insertion)
  }
}

In the insertAfter method:

1. Find Existing Node: We first use this.find(afterValue) to search for the first node in the list that has a value equal to afterValue. The result is stored in existingNode.

2. Check if Node Exists: We check if existingNode is truthy (i.e., not null). If it is, it means we found a node with the afterValue. Only in this case do we proceed with the insertion.

3. Create and Insert New Node: If existingNode is found:

   • const newNode = { value: value, next: existingNode.next };: We create a newNode. Its next pointer is set to existingNode.next. This means the newNode will point to whatever was originally the node after existingNode.
   • existingNode.next = newNode;: We update the next pointer of existingNode to point to newNode. This effectively inserts the newNode into the list, right after existingNode.

4. No Insertion if afterValue Not Found: If existingNode is falsy (i.e., null), it means no node with the afterValue was found in the list. In this case, we do nothing, and no new node is inserted.

Testing insertAfter()

Let’s test the insertAfter() method:

// app.js
class LinkedList {
  // ... (LinkedList class implementation including insertAfter) ...
}

const myList = new LinkedList();
myList.append("a");
myList.append("c");
myList.append("d");

myList.insertAfter("b", "a"); // Insert "b" after "a"
myList.insertAfter("e", "z"); // Try to insert "e" after "z" (not in list)

console.log(myList.toArray());
// Output (expected): ["a", "b", "c", "d"] (No "e" inserted, "b" inserted after "a")

When you run this, you should see that “b” is inserted into the list after “a”, and “e” is not inserted because “z” is not found in the list. This confirms that insertAfter() is working correctly, inserting nodes in the desired positions and handling cases where the afterValue is not found.

With these methods (append, prepend, delete, find, insertAfter), we have implemented a functional custom linked list data structure in JavaScript. You can further extend this linked list with additional methods as needed for specific use cases.

Linked Lists vs. Arrays: Performance and Use Cases

Now that we have constructed a custom linked list, let’s compare it to JavaScript’s built-in arrays in terms of performance and typical use cases. Understanding these comparisons will help you decide when a linked list might be a more appropriate choice than an array, and vice versa.

Time Complexity Comparison (Big O Notation)

We can analyze the time complexity of common operations for both linked lists and arrays using Big O notation. Big O notation describes how the execution time of an algorithm or operation grows as the input size (in this case, the number of elements in the data structure) increases.

Time Complexity: Time complexity is a measure of how the execution time of an algorithm or operation scales with the size of the input. It is often expressed using Big O notation. Big O Notation: Big O notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is used to classify algorithms according to how their run-time or space requirements grow as the input size grows.

Here’s a table summarizing the time complexities of common operations for linked lists (as implemented in this chapter) and arrays:

| Operation | Linked List (Our Implementation) | Array | Big O Notation Explanation Arrays have constant time (O(1)) complexity for element access by index because you can directly jump to the memory location of the element using its index. | Access by Index | N/A (Not Applicable) | O(1) | Arrays allow direct access to elements using their index, which takes constant time regardless of array size.