JavaScript - Data Structures

A data structure is a way of organizing, managing, and storing data in a computer so that it can be accessed and modified efficiently. It defines the relationship between data elements, as well as the operations that can be performed on them, such as insertion, deletion, traversal, and searching. Data structures are fundamental to creating efficient algorithms and software, as they impact the way data is handled in a program.

 

Benefits of Data Structures:

1. Organization: Defines how data is arranged in memory, whether in contiguous blocks (like arrays) or linked nodes (like linked lists).
2. Efficiency: Data structures are chosen based on their efficiency for particular operations, like quick access, minimal memory usage, or optimized processing time.
3. Functionality: Some data structures are better suited for specific functions, such as stacks for undo operations or queues for scheduling tasks.
4. Data Relationships: They define how elements relate to one another, like parent-child relationships in trees or connections in graphs.

Built-in JavaScript Data Structures

1. Arrays

Arrays are one of the most commonly used data structures in JavaScript. They are ordered collections of elements, which can be of any data type (numbers, strings, objects, etc.). Arrays are indexed starting from 0, and they grow dynamically as new elements are added.

Characteristics:

• Indexed: Elements are accessed via their index, starting at 0.
• Dynamic size: Arrays can grow or shrink in size dynamically.
• Ordered: Elements maintain the order in which they were added.

 

Key Methods:

• push(): Adds an element to the end of the array.
• pop(): Removes the last element.
• shift(): Removes the first element.
• unshift(): Adds an element to the beginning.
• map(): Transforms each element in the array based on a function.
• filter(): Filters elements based on a condition.
• reduce(): Reduces the array to a single value by applying a function.

 

Example:

let fruits = [‘apple’, ‘banana’, ‘cherry’];

fruits.push(‘orange’);  // Adds ‘orange’ to the end

console.log(fruits);     // [‘apple’, ‘banana’, ‘cherry’, ‘orange’]

Arrays are ideal for ordered lists of data, such as a list of products in a shopping cart, where you need to access, modify, or iterate through elements efficiently.

 

2. Objects

An object is another fundamental data structure in JavaScript. It stores data as key-value pairs, where each key is a string or symbol, and the associated value can be any data type.

Characteristics:

• Key-value pairs: Each key must be unique, and the values can be of any type.
• Dynamic: Objects can be modified by adding, updating, or deleting key-value pairs.
• Unordered: The order of key-value pairs is not guaranteed.

 

Key Methods:

• Object.keys(): Returns an array of the object’s keys.
• Object.values(): Returns an array of the object’s values.
• delete: Removes a key-value pair from the object.

 

Example:

let person = { name: ‘Alice’, age: 25 };

console.log(person.name);  // Output: ‘Alice’

Objects are perfect for representing structured data, such as user profiles or configurations, where you need to access values by their keys.

3. Set

A Set is a collection of unique values, meaning it automatically removes duplicates. Unlike arrays, the values in a Set are not ordered and cannot be accessed by index.

Characteristics:

• Unique values: No duplicates are allowed.
• Unordered: Elements are not guaranteed to be in a specific order.
• Iterable: You can loop through the elements in a Set.

 

Key Methods:

• add(): Adds a new value.
• has(): Checks if a value exists in the set.
• delete(): Removes a value from the set.
• clear(): Removes all elements.

 

Example:

let uniqueNumbers = new Set([1, 2, 3, 3, 4]);

console.log(uniqueNumbers);  // Output: Set {1, 2, 3, 4}

Set is useful when you want to maintain a collection of unique items, such as tracking unique visitors to a website or ensuring no duplicate entries in a user input form.

4. Map

A Map is similar to an object but offers more flexibility with key types. Unlike objects, which can only have strings or symbols as keys, a Map can have keys of any type, including functions, objects, and primitive values.

Characteristics:

• Key-value pairs: Similar to objects, but keys can be of any type.
• Ordered: The key-value pairs maintain the order of insertion.
• Efficient lookup: Accessing a value via a key is faster than with an object in certain scenarios.

 

Key Methods:

• set(): Adds a key-value pair to the map.
• get(): Retrieves the value associated with a key.
• has(): Checks if a key exists in the map.
• delete(): Removes a key-value pair.

Example:

let scores = new Map();

scores.set(‘Alice’, 90);

scores.set(‘Bob’, 85);

console.log(scores.get(‘Alice’));  // Output: 90

Map is particularly useful when you need to store complex data or perform frequent lookups where the key can be of any type, such as associating metadata with DOM elements in a web application.

5. WeakMap

WeakMap is a special type of Map where keys must be objects, and the key-value pairs are weakly referenced. This means that if there are no other references to the key object, it can be garbage-collected, making WeakMap ideal for scenarios where memory management is critical.

Characteristics:

• Object keys: Keys must be objects.
• Weak references: Allows garbage collection of key objects when they are no longer referenced elsewhere.
• Non-iterable: You cannot loop through a WeakMap.

Example:

let wm = new WeakMap();

let obj = {};wm.set(obj, ‘value’);

WeakMap is useful for managing resources like caching or associating private data with objects without preventing them from being garbage-collected, ensuring efficient memory usage.

6. WeakSet

Similar to WeakMap, a WeakSet only stores objects and allows for garbage collection of objects if there are no other references to them.

Characteristics:

• Object-only: Only objects can be stored in a WeakSet.
• Weak references: Objects can be garbage-collected when no longer needed.
• Non-iterable: You cannot loop through a WeakSet.

Example:

let ws = new WeakSet();

let obj = {};ws.add(obj);

WeakSet is ideal when you need to keep track of objects without preventing them from being garbage-collected, such as keeping track of DOM elements for event handling or other temporary purposes.

Custom Data Structures

Custom data structures are user-defined data structures built to meet specific requirements that cannot be efficiently managed by standard, built-in data structures. Unlike built-in types (e.g., arrays, objects, sets, and maps in JavaScript), custom data structures are manually constructed by the developer to handle complex operations or specific functionalities, such as organizing data in unique ways or optimizing for particular access patterns.

Characteristics of Custom Data Structures:

1. Tailored Functionality: Custom data structures allow developers to define exactly how data is organized, accessed, and manipulated.
2. Optimized Performance: They can be tailored for optimal performance in specific use cases, improving time and space complexity over generic structures.
3. Encapsulation of Data and Methods: Custom structures encapsulate both data and the methods to manipulate that data, creating a cohesive, modular solution.
4. Adaptability: Developers can easily adapt or expand these structures by adding new methods, handling edge cases, or implementing custom behaviors.

1. Stack

A stack is a data structure that operates in a Last-In-First-Out (LIFO) order, meaning that the most recently added element is the first to be removed. Stacks are typically visualized as vertical structures where elements are added and removed from the “top.”

Characteristics:

• Follows LIFO order.
• Elements are added and removed only from the top of the stack.
• Commonly implemented using arrays or linked lists in JavaScript.

 

Key Methods:

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the top element.
• peek(): Returns the top element without removing it.
• isEmpty(): Checks if the stack has any elements.
• size(): Returns the count of elements in the stack.

Example:

const stack = new Stack();

stack.push(5);

stack.push(10);

console.log(stack.pop()); // Output: 10

console.log(stack.peek()); // Output: 5

Stack is useful in undo functionality in text editors (e.g., each action is “pushed” onto the stack), Browser history tracking and Expression evaluation and parsing in compilers.

 

2. Queue

A queue is a First-In-First-Out (FIFO) data structure where elements are added at the end and removed from the front. It’s useful for situations that require ordering, where the first element added is the first to be processed.

Characteristics:

• Follows FIFO order.
• Elements are added at the rear and removed from the front.
• Commonly implemented with arrays or linked lists.

Key Methods:

• enqueue(element): Adds an element to the rear of the queue.
• dequeue(): Removes and returns the front element.
• front(): Returns the front element without removing it.
• isEmpty(): Checks if the queue has any elements.
• size(): Returns the count of elements in the queue.

Example:

const queue = new Queue();

queue.enqueue(5);

queue.enqueue(10);

console.log(queue.dequeue()); // Output: 5

console.log(queue.front()); // Output: 10

Queue is useful in Task scheduling, such as handling print jobs or processes in an operating system, handling requests in web servers and Breadth-First Search (BFS) traversal in graphs and trees.

 

3. Linked List

A linked list is a linear data structure consisting of nodes where each node contains a value and a reference (or pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory allocation and can grow dynamically.

Characteristics:

• Composed of nodes, each holding a value and a next pointer.
• Dynamic size; can easily grow or shrink.
• No direct access by index, making it slower for indexed access compared to arrays.

 

Key Methods: