Data Structures definition - rs-hash/Learning GitHub Wiki

Certainly, let's explore various data structures in-depth with JavaScript examples. We'll cover common data structures and provide code examples for each one.

1. Arrays:

An array is a linear data structure that stores a collection of elements, each identified by an index or a key.

// Creating an array
const fruits = ['apple', 'banana', 'cherry'];

// Accessing elements
console.log(fruits[0]); // Output: 'apple'

// Adding elements
fruits.push('date'); // Adds 'date' to the end
fruits.unshift('apricot'); // Adds 'apricot' to the beginning

// Removing elements
fruits.pop(); // Removes the last element ('date')
fruits.shift(); // Removes the first element ('apricot')

2. Linked Lists:

A linked list is a data structure in which each element (node) points to the next one, forming a sequence.

// Creating a simple linked list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

const node1 = new Node('apple');
const node2 = new Node('banana');
node1.next = node2;

// Traversing a linked list
let current = node1;
while (current !== null) {
  console.log(current.data); // Output: 'apple', 'banana'
  current = current.next;
}

3. Stacks:

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle.

// Creating a stack
const stack = [];

// Pushing elements onto the stack
stack.push('apple');
stack.push('banana');
stack.push('cherry');

// Popping elements from the stack
const top = stack.pop(); // Removes 'cherry'
console.log(top); // Output: 'cherry'

4. Queues:

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.

// Creating a queue
const queue = [];

// Enqueuing elements
queue.push('apple');
queue.push('banana');
queue.push('cherry');

// Dequeuing elements
const front = queue.shift(); // Removes 'apple'
console.log(front); // Output: 'apple'

5. Trees

In data structures and computer science, various types of trees are used to organize and represent data efficiently. Each type of tree has its own characteristics and use cases. Here are some common types of trees:

Binary Tree: A binary tree is a tree in which each node has at most two children, referred to as the left child and the right child. Binary trees are widely used and serve as the foundation for many other tree structures.
Binary Search Tree (BST): A binary search tree is a binary tree with the property that the left subtree of a node contains values less than the node, and the right subtree contains values greater than the node. BSTs allow for efficient searching, insertion, and deletion of elements.
Balanced Binary Tree: A balanced binary tree is a binary tree in which the height of the left and right subtrees of any node differs by at most one. Examples of balanced binary trees include AVL trees and Red-Black trees.
AVL Tree: An AVL tree is a self-balancing binary search tree in which the balance factor (the height of the left subtree minus the height of the right subtree) of each node is at most 1. AVL trees ensure logarithmic time complexity for search, insert, and delete operations.
Red-Black Tree: A Red-Black tree is another self-balancing binary search tree in which each node is colored red or black. Red-Black trees also guarantee logarithmic time complexity for search, insert, and delete operations.
Heap: A heap is a binary tree that satisfies the heap property, where each parent node has a value greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the values of its children. Heaps are often used for priority queues.

Binary Trees:

A binary tree is a hierarchical data structure consisting of nodes, where each node has at most two children.

// Creating a binary tree node
class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

// Building a binary tree
const root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);

// Traversing a binary tree (in-order traversal)
function inOrderTraversal(node) {
  if (node === null) return;
  inOrderTraversal(node.left);
  console.log(node.value);
  inOrderTraversal(node.right);
}

inOrderTraversal(root); // Output: 3, 5, 7, 10, 15

Certainly, let's continue to explore these data structures in-depth with JavaScript examples:

AVL Trees:

An AVL tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree. It ensures that the height difference between the left and right subtrees of any node (the balance factor) is at most 1, making it efficient for searching and inserting elements.

Heaps:

A heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, each parent node has a greater value than its children; in a min-heap, each parent node has a smaller value than its children.

// Using JavaScript's built-in heap (priority queue)
const maxHeap = new MaxHeap();
maxHeap.insert(10);
maxHeap.insert(20);
maxHeap.insert(5);

console.log(maxHeap.extractMax()); // Output: 20 (max element)

A heap is a specialized tree-based data structure that satisfies the heap property. In heaps, each parent node has a value greater than or equal to (in a max-heap) or less than or equal to (in a min-heap) the values of its children. Heaps are commonly used to efficiently maintain the maximum or minimum value in a collection, making them useful for priority queues and various algorithms.

In JavaScript, you can implement heaps using arrays. There are two main types of heaps: max-heaps and min-heaps. Let's explore both types with coding examples.

Max-Heap and Min-Heap in JavaScript:

Max-Heap:

In a max-heap, the parent nodes have values greater than or equal to their children. This ensures that the maximum value is at the root.

Min-Heap:

In a min-heap, the parent nodes have values less than or equal to their children. This ensures that the minimum value is at the root.

we create max-heap and min-heap data structures and perform insertion and extraction operations to demonstrate their functionality. Max-heaps are commonly used for priority queues, while min-heaps are useful for implementing algorithms like Dijkstra's shortest path algorithm.

Heaps are fundamental data structures in computer science and have various applications in algorithms and data processing, including sorting, searching, and finding extreme values.

6. Hash Tables:

A hash table is a data structure that maps keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

// Using JavaScript's built-in hash table (object)
const hashMap = {};
hashMap['name'] = 'John';
hashMap['age'] = 30;

console.log(hashMap['name']); // Output: 'John'

Hash tables, also known as hash maps or dictionaries, are data structures used to store key-value pairs efficiently. They provide quick access to values associated with keys, making them valuable for various applications. In JavaScript, you can implement a hash table using objects or the Map data structure. Let's explore hash tables in detail with a coding example using both approaches.

Hash Tables in JavaScript:

Using Objects:

Creating a Hash Table (Object):

In JavaScript, objects can be used as simple hash tables. You can create a hash table by defining an object and associating keys with values.

// Creating a hash table (object)
const phoneBook = {};

// Adding key-value pairs
phoneBook['Alice'] = '123-456-7890';
phoneBook['Bob'] = '987-654-3210';

console.log(phoneBook); // Output: { Alice: '123-456-7890', Bob: '987-654-3210' }

Operations:

Adding a key-value pair: object[key] = value
Accessing a value: object[key]
Checking existence: key in object
Deleting a key-value pair: delete object[key]

Example:

console.log(phoneBook['Alice']); // Output: '123-456-7890'
console.log('Bob' in phoneBook); // Output: true
delete phoneBook['Alice'];
console.log(phoneBook); // Output: { Bob: '987-654-3210' }

Using `Map`:

The Map data structure is a more advanced and versatile way to create hash tables in JavaScript. It allows you to use various data types as keys and offers built-in methods for manipulating key-value pairs.

Creating a Hash Table (Map):

// Creating a hash table (Map)
const phoneBookMap = new Map();

// Adding key-value pairs
phoneBookMap.set('Alice', '123-456-7890');
phoneBookMap.set('Bob', '987-654-3210');

console.log(phoneBookMap); // Output: Map { 'Alice' => '123-456-7890', 'Bob' => '987-654-3210' }

Operations:

Adding a key-value pair: map.set(key, value)
Accessing a value: map.get(key)
Checking existence: map.has(key)
Deleting a key-value pair: map.delete(key)

Example:

console.log(phoneBookMap.get('Alice')); // Output: '123-456-7890'
console.log(phoneBookMap.has('Bob')); // Output: true
phoneBookMap.delete('Alice');
console.log(phoneBookMap); // Output: Map { 'Bob' => '987-654-3210' }

Hashing Function:

Both approaches rely on a hashing function to convert keys into indices for efficient storage and retrieval. JavaScript objects and the Map data structure handle this hashing internally.

When to Use Hash Tables:

Storing key-value pairs when quick access by key is required.
Counting occurrences of elements in a collection.
Implementing caches or memoization.
Implementing sets with unique elements.
Creating lookup tables for optimized algorithms.

Hash tables are versatile and widely used in software development for solving a variety of problems that require fast and efficient key-based access to values. The choice between using objects and the Map data structure depends on the specific requirements of your application.

8. Graphs:

A graph is a collection of nodes (vertices) and edges that connect pairs of nodes. It's used to represent relationships between entities.

// Using JavaScript's built-in graph representation (adjacency list)
const graph = new Map();
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A']);
graph.set('D', ['B']);

console.log(graph.get('A')); // Output: ['B', 'C']

Graphs are versatile data structures used to represent complex relationships between objects. In JavaScript, graphs are typically implemented using various data structures such as adjacency lists or adjacency matrices. Let's explore graphs in detail with a coding example using an adjacency list.

Graphs in JavaScript:

A graph consists of a set of vertices (nodes) and a set of edges (connections) that link pairs of vertices. Graphs can be used to represent various real-world relationships, such as social networks, web pages, and transportation systems.

Representation using Adjacency List:

In an adjacency list representation, each vertex in the graph is associated with a list of its neighboring vertices. This representation is efficient for sparse graphs (where not all pairs of vertices are connected).

Creating a Graph:

Let's create a simple undirected graph using an adjacency list in JavaScript:

class Graph {
  constructor() {
    this.vertices = new Map(); // Use a Map to store vertices and their neighbors
  }

  // Add a new vertex to the graph
  addVertex(vertex) {
    if (!this.vertices.has(vertex)) {
      this.vertices.set(vertex, []);
    }
  }

  // Add an edge between two vertices
  addEdge(fromVertex, toVertex) {
    this.addVertex(fromVertex);
    this.addVertex(toVertex);

    this.vertices.get(fromVertex).push(toVertex);
    this.vertices.get(toVertex).push(fromVertex); // For undirected graph
  }

  // Display the graph
  print() {
    for (const [vertex, neighbors] of this.vertices) {
      console.log(`${vertex} -> ${neighbors.join(', ')}`);
    }
  }
}

// Create a new graph
const socialNetwork = new Graph();

// Add vertices (people)
socialNetwork.addVertex('Alice');
socialNetwork.addVertex('Bob');
socialNetwork.addVertex('Carol');
socialNetwork.addVertex('David');

// Add friendships (edges)
socialNetwork.addEdge('Alice', 'Bob');
socialNetwork.addEdge('Bob', 'Carol');
socialNetwork.addEdge('Carol', 'David');

// Display the social network
socialNetwork.print();

Output:

Alice -> Bob
Bob -> Alice, Carol
Carol -> Bob, David
David -> Carol

In this example, we created a simple social network graph using an adjacency list. We added vertices (representing people) and edges (representing friendships) between them.

Graph Traversal:

Traversal is the process of visiting all vertices and edges in a graph. Two common graph traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).

DFS (Depth-First Search):

DFS explores as far as possible along each branch before backtracking. It can be implemented using recursion.

// Depth-First Search (DFS)
function dfs(graph, startVertex, visited = new Set()) {
  if (!graph.vertices.has(startVertex)) return;
  visited.add(startVertex);
  console.log(startVertex);

  for (const neighbor of graph.vertices.get(startVertex)) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// Perform DFS traversal starting from 'Alice'
console.log('DFS traversal:');
dfs(socialNetwork, 'Alice');

Output:

DFS traversal:
Alice
Bob
Carol
David

BFS (Breadth-First Search):

BFS explores all the vertices at the current level before moving to the next level. It uses a queue data structure.

// Breadth-First Search (BFS)
function bfs(graph, startVertex) {
  if (!graph.vertices.has(startVertex)) return;

  const visited = new Set();
  const queue = [startVertex];

  while (queue.length > 0) {
    const currentVertex = queue.shift();
    if (!visited.has(currentVertex)) {
      visited.add(currentVertex);
      console.log(currentVertex);

      for (const neighbor of graph.vertices.get(currentVertex)) {
        if (!visited.has(neighbor)) {
          queue.push(neighbor);
        }
      }
    }
  }
}

// Perform BFS traversal starting from 'Alice'
console.log('BFS traversal:');
bfs(socialNetwork, 'Alice');

Output:

BFS traversal:
Alice
Bob
Carol
David

In this example, we implemented both DFS and BFS traversal algorithms to explore the social network graph starting from the 'Alice' vertex.

Graphs are powerful data structures that have numerous applications in computer science, including route planning, network analysis, and recommendation systems. Understanding graph representations and traversal algorithms is essential for solving problems involving complex relationships.

9. Sets and Maps:

- Sets are collections of unique elements, while maps are collections of key-value pairs.

// Set
const uniqueNumbers = new Set();
uniqueNumbers.add(1);
uniqueNumbers.add(2);
uniqueNumbers.add(1); // Ignored because it's a duplicate

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

// Map
const person = new Map();
person.set('name', 'Alice');
person.set('age', 25);

console.log(person.get('name')); // Output: 'Alice'

Certainly! Let's dive into the details of Sets and Maps in JavaScript, along with coding examples.

Sets in JavaScript:

A Set is a built-in data structure in JavaScript that represents a collection of unique values. It can store various data types, including primitives and objects. Sets are designed for efficient membership testing (checking if a value exists in the set) and do not allow duplicate values.

Methods and Operations:

Sets come with various methods for adding, deleting, and checking the presence of elements:

add(value): Adds a new value to the Set.
delete(value): Removes a value from the Set.
has(value): Checks if a value exists in the Set.
clear(): Removes all values from the Set.
size: Returns the number of unique values in the Set.

const colors = new Set();
colors.add('red');
colors.add('green');
colors.add('blue');

console.log(colors.has('red')); // Output: true
console.log(colors.size); // Output: 3

colors.delete('green');
console.log(colors); // Output: Set { 'red', 'blue' }

colors.clear();
console.log(colors); // Output: Set {}

Iterating Through a Set:

You can iterate through a Set using methods like forEach, for...of, or the spread operator (...):

const fruits = new Set(['apple', 'banana', 'cherry']);

// Using forEach
fruits.forEach((fruit) => {
  console.log(fruit);
});

// Using for...of
for (const fruit of fruits) {
  console.log(fruit);
}

Maps in JavaScript:

A Map is another built-in data structure in JavaScript that allows you to store key-value pairs. Unlike objects, which only allow string or symbol keys, Maps can use any data type as keys and preserve the order of insertion. Maps are commonly used for associating values with unique identifiers.

Methods and Operations:

Maps provide methods for adding, deleting, retrieving, and checking the presence of key-value pairs:

set(key, value): Sets a key-value pair in the Map.
get(key): Retrieves the value associated with a key.
has(key): Checks if a key exists in the Map.
delete(key): Removes a key-value pair from the Map.
clear(): Removes all key-value pairs from the Map.
size: Returns the number of key-value pairs in the Map.

const student = new Map();
student.set('name', 'Bob');
student.set('age', 22);

console.log(student.get('name')); // Output: 'Bob'
console.log(student.has('age')); // Output: true
console.log(student.size); // Output: 2

student.delete('name');
console.log(student); // Output: Map { 'age' => 22 }

student.clear();
console.log(student); // Output: Map {}

Iterating Through a Map:

You can iterate through a Map using methods like forEach or for...of:

const countryInfo = new Map([
  ['name', 'USA'],
  ['population', 331],
  ['capital', 'Washington, D.C.'],
]);

// Using forEach
countryInfo.forEach((value, key) => {
  console.log(`${key}: ${value}`);
});

// Using for...of
for (const [key, value] of countryInfo) {
  console.log(`${key}: ${value}`);
}

Sure, here's a comparison of Sets and Maps in a table format:

Feature	Sets	Maps
Data Structure Type	Set	Map
Primary Use	Storing unique values	Storing key-value pairs
Key Type	Values can be of any data type	Keys can be of any data type
Handling Duplicates	Automatically removes duplicates	Allows duplicate values with unique keys
Order of Elements	No guaranteed order of elements	Preserves insertion order
Size (Number of Elements)	`size` property	`size` property
Adding Elements	`add(value)`	`set(key, value)`
Removing Elements	`delete(value)`	`delete(key)`
Checking Existence	`has(value)`	`has(key)`
Clearing All Elements	`clear()`	`clear()`
Iteration	`forEach(callback)`, `for...of`, Spread Operator	`forEach(callback)`, `for...of`, Entries
Typical Use Cases	Removing duplicates, maintaining unique collections	Associating data with unique identifiers
Example	`javascript const colors = new Set(); colors.add('red'); colors.add('green'); colors.add('blue');`	`javascript const person = new Map(); person.set('name', 'Alice'); person.set('age', 25);`

Remember that the choice between Sets and Maps depends on the specific requirements of your application. Sets are useful for managing collections of unique values, while Maps are suitable for associating values with unique keys.

Use Cases

Certainly! Here's a list of common data structures, along with their use cases and easy-to-understand example scenarios:

Arrays:
- Use Case: Storing a list of items of the same type.
- Example Use Case: Storing a list of integers [1, 2, 3, 4, 5].
Linked Lists:
- Use Case: Dynamic data storage where elements can be efficiently inserted and removed.
- Example Use Case: Implementing a to-do list where tasks can be added or removed easily.
Stacks:
- Use Case: Managing function calls, undo functionality, and tracking state changes.
- Example Use Case: Implementing the "Undo" feature in a text editor.
Queues:
- Use Case: Task scheduling, managing requests, and handling print jobs.
- Example Use Case: Print queue in a printer, where documents are processed in the order they are received.
Hash Tables:
- Use Case: Implementing dictionaries, caches, and efficient data retrieval.
- Example Use Case: Storing user data in a web application, where user IDs are used as keys to access user information.
Binary Trees:
- Use Case: Organizing hierarchical data, representing file systems, and optimizing search operations.
- Example Use Case: Representing the file structure of a computer with directories and subdirectories.
Binary Search Trees (BST):
- Use Case: Efficient searching, insertion, and deletion operations.
- Example Use Case: Implementing a dictionary where words are stored in a sorted order for quick lookups.
Heaps (e.g., Min-Heap):
- Use Case: Priority queues, finding the smallest (or largest) item, and scheduling tasks.
- Example Use Case: Task scheduling in an operating system, where tasks with higher priority are executed first.
Tries (Prefix Trees):
- Use Case: Efficient searching for words, autocomplete, and IP routing.
- Example Use Case: Implementing an autocomplete feature in a search engine.
Graphs (e.g., Adjacency Lists):
- Use Case: Modeling relationships between objects, social networks, and route planning.
- Example Use Case: Representing connections between users in a social media platform.
Hash Sets:
- Use Case: Storing a collection of unique items and checking for duplicates.
- Example Use Case: Keeping track of unique email addresses in a mailing list.
Hash Maps:
- Use Case: Associating values with keys for fast retrieval.
- Example Use Case: Implementing a shopping cart in an e-commerce website where products are stored with their quantities.
Segment Trees:
- Use Case: Range queries, such as finding the sum or minimum/maximum in a range of values.
- Example Use Case: Calculating the total sales for a specific time period in a sales database.
B-Trees (e.g., B+Tree):
- Use Case: File systems, databases, and efficient indexing for large datasets.
- Example Use Case: Organizing and indexing data records in a large database.
Splay Trees:
- Use Case: Optimizing access patterns for frequently accessed items.
- Example Use Case: Caching frequently accessed web pages to reduce load times.
Octrees:
- Use Case: 3D computer graphics, spatial partitioning, and 3D modeling.
- Example Use Case: Modeling the structure of a 3D environment in a video game.
Huffman Trees:
- Use Case: Data compression and variable-length encoding.
- Example Use Case: Compressing text or multimedia files to reduce storage space.

These examples illustrate how each data structure can be applied to real-world scenarios. Choosing the right data structure depends on the specific needs of your application and the type of operations you need to perform efficiently.

Data Structures definition - rs-hash/Learning GitHub Wiki

1. Arrays:

2. Linked Lists:

3. Stacks:

4. Queues:

5. Trees

Binary Trees:

AVL Trees:

Heaps:

Max-Heap and Min-Heap in JavaScript:

Max-Heap:

Min-Heap:

6. Hash Tables:

Hash Tables in JavaScript:

Using Objects:

Using Map:

Hashing Function:

When to Use Hash Tables:

8. Graphs:

Graphs in JavaScript:

Representation using Adjacency List:

Graph Traversal:

DFS (Depth-First Search):

BFS (Breadth-First Search):

9. Sets and Maps:

Sets in JavaScript:

Maps in JavaScript:

Use Cases

Using `Map`: