Skip to main content

Introduction to Data Structures

Why Data Structures Matter​

Data structures are specialized formats for organizing, processing, retrieving, and storing data. They form the backbone of efficient algorithms and are essential for solving complex computational problems. The right data structure can:

  • Significantly improve application performance
  • Reduce memory consumption
  • Simplify code and improve readability
  • Enable elegant solutions to otherwise difficult problems

As a developer, understanding data structures is not just an academic exercise—it's a practical skill that directly impacts your ability to write efficient and maintainable code.

Types of Data Structures​

Data structures can be broadly categorized into two types:

1. Primitive Data Structures​

These are the basic data types provided by programming languages:

  • Numbers (integers, floating-point)
  • Strings
  • Booleans
  • Null/Undefined values

2. Non-Primitive (Composite) Data Structures​

These are more complex structures built using primitive types and other composite structures. They can be further categorized as:

Linear Data Structures​

Elements are arranged in sequential order:

  • Arrays: Collection of elements identified by index
  • Linked Lists: Collection of nodes connected via references
  • Stacks: Last-In-First-Out (LIFO) collection
  • Queues: First-In-First-Out (FIFO) collection

Non-Linear Data Structures​

Elements are not arranged sequentially:

  • Trees: Hierarchical structure with a root node and child nodes
  • Graphs: Collection of nodes (vertices) connected by edges
  • Hash Tables: Key-value pairs with efficient lookups
  • Heaps: Specialized tree-based structure for priority operations

Key Operations and Complexity​

For each data structure, we analyze performance based on common operations:

  • Access: Retrieving an element (by index, key, etc.)
  • Search: Finding an element
  • Insertion: Adding a new element
  • Deletion: Removing an element
  • Traversal: Visiting all elements

The efficiency of these operations is measured using Big O notation, which describes how the performance scales with input size.

Arrays​

Arrays are among the most fundamental data structures, offering direct access to elements via indices.

Implementation​

// Creating arrays in JavaScript
const fruits = ['apple', 'banana', 'orange'];
const numbers = new Array(1, 2, 3, 4, 5);
const matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; // 2D array

Key Operations​

// Access - O(1)
const firstFruit = fruits[0]; // apple

// Search - O(n)
const hasApple = fruits.includes('apple'); // true

// Insertion - O(1) at the end, O(n) elsewhere
fruits.push('grape'); // Add to end
fruits.unshift('pear'); // Add to beginning
fruits.splice(2, 0, 'kiwi'); // Add at specific position

// Deletion - O(1) at the end, O(n) elsewhere
fruits.pop(); // Remove from end
fruits.shift(); // Remove from beginning
fruits.splice(1, 1); // Remove at specific position

// Traversal - O(n)
fruits.forEach(fruit => console.log(fruit));

Time Complexity Analysis​

OperationAverage CaseWorst Case
AccessO(1)O(1)
SearchO(n)O(n)
InsertionO(n)O(n)
DeletionO(n)O(n)

Arrays offer constant-time access but linear-time insertions and deletions (except at the end).

Linked Lists​

A linked list consists of nodes, each containing data and a reference to the next node.

Implementation​

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

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  
  // Add a node to the end of the list
  append(data) {
    const newNode = new Node(data);
    
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    
    this.size++;
  }
  
  // Add a node to the beginning of the list
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }
  
  // Insert at a specific position
  insertAt(data, index) {
    if (index < 0 || index > this.size) {
      return false;
    }
    
    if (index === 0) {
      this.prepend(data);
      return true;
    }
    
    const newNode = new Node(data);
    let current = this.head;
    let previous;
    let count = 0;
    
    while (count < index) {
      previous = current;
      current = current.next;
      count++;
    }
    
    newNode.next = current;
    previous.next = newNode;
    this.size++;
    return true;
  }
  
  // Remove a node at a specific position
  removeAt(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }
    
    let current = this.head;
    let previous;
    let count = 0;
    
    if (index === 0) {
      this.head = current.next;
    } else {
      while (count < index) {
        previous = current;
        current = current.next;
        count++;
      }
      
      previous.next = current.next;
    }
    
    this.size--;
    return current.data;
  }
  
  // Find a node by its data
  find(data) {
    let current = this.head;
    let index = 0;
    
    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }
    
    return -1;
  }
  
  // Print the linked list
  printList() {
    let current = this.head;
    const values = [];
    
    while (current) {
      values.push(current.data);
      current = current.next;
    }
    
    return values.join(' -> ');
  }
  
  // Get the size of the linked list
  getSize() {
    return this.size;
  }
  
  // Check if the linked list is empty
  isEmpty() {
    return this.size === 0;
  }
}

// Usage example
const list = new LinkedList();
list.append(10);
list.append(20);
list.prepend(5);
list.insertAt(15, 2);
console.log(list.printList()); // Output: 5 -> 10 -> 15 -> 20
console.log(list.find(15)); // Output: 2
list.removeAt(1);
console.log(list.printList()); // Output: 5 -> 15 -> 20

Time Complexity Analysis​

OperationAverage CaseWorst Case
AccessO(n)O(n)
SearchO(n)O(n)
InsertionO(1) or O(n)O(n)
DeletionO(1) or O(n)O(n)

Linked lists excel at insertions and deletions (when the position is known) but have slower access times compared to arrays.

Stacks​

Stacks follow the Last-In-First-Out (LIFO) principle, similar to a stack of plates.

Implementation​

class Stack {
  constructor() {
    this.items = [];
  }
  
  // Add an element to the top of the stack
  push(element) {
    this.items.push(element);
  }
  
  // Remove and return the top element
  pop() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    return this.items.pop();
  }
  
  // Return the top element without removing it
  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }
  
  // Check if the stack is empty
  isEmpty() {
    return this.items.length === 0;
  }
  
  // Return the size of the stack
  size() {
    return this.items.length;
  }
  
  // Clear the stack
  clear() {
    this.items = [];
  }
  
  // Print the stack elements
  print() {
    return this.items.join(' ');
  }
}

// Usage example
const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.print()); // Output: 10 20 30
console.log(stack.peek()); // Output: 30
console.log(stack.pop()); // Output: 30
console.log(stack.print()); // Output: 10 20

Applications of Stacks​

  • Function call management (call stack)
  • Expression evaluation and syntax parsing
  • Undo mechanisms in applications
  • Browser history (back button implementation)
  • Depth-first traversal of trees and graphs

Time Complexity Analysis​

OperationTime Complexity
PushO(1)
PopO(1)
PeekO(1)
SearchO(n)
SizeO(1)

Queues​

Queues follow the First-In-First-Out (FIFO) principle, similar to a line of people.

Implementation​

class Queue {
  constructor() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }
  
  // Add an element to the back of the queue
  enqueue(element) {
    this.items[this.backIndex] = element;
    this.backIndex++;
  }
  
  // Remove and return the front element
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow";
    }
    
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;
    return item;
  }
  
  // Return the front element without removing it
  front() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[this.frontIndex];
  }
  
  // Check if the queue is empty
  isEmpty() {
    return this.frontIndex === this.backIndex;
  }
  
  // Return the size of the queue
  size() {
    return this.backIndex - this.frontIndex;
  }
  
  // Clear the queue
  clear() {
    this.items = {};
    this.frontIndex = 0;
    this.backIndex = 0;
  }
  
  // Print the queue elements
  print() {
    const values = [];
    for (let i = this.frontIndex; i < this.backIndex; i++) {
      values.push(this.items[i]);
    }
    return values.join(' ');
  }
}

// Usage example
const queue = new Queue();
queue.enqueue('A');
queue.enqueue('B');
queue.enqueue('C');
console.log(queue.print()); // Output: A B C
console.log(queue.front()); // Output: A
console.log(queue.dequeue()); // Output: A
console.log(queue.print()); // Output: B C

Applications of Queues​

  • Task scheduling in operating systems
  • Handling of requests on a single shared resource (printer, CPU)
  • Buffering for data streams
  • Breadth-first traversal of trees and graphs
  • Message queues in distributed systems

Time Complexity Analysis​

OperationTime Complexity
EnqueueO(1)
DequeueO(1)
FrontO(1)
SearchO(n)
SizeO(1)

Hash Tables​

Hash tables store key-value pairs and provide efficient lookups using a hash function.

Implementation​

class HashTable {
  constructor(size = 53) {
    this.table = new Array(size);
    this.size = size;
  }
  
  // Simple hash function
  _hash(key) {
    let total = 0;
    let prime = 31;
    
    // Use only the first 100 characters of the key to limit computation
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96; // 'a' is 1, 'b' is 2, etc.
      total = (total * prime + value) % this.size;
    }
    
    return total;
  }
  
  // Set a key-value pair
  set(key, value) {
    const index = this._hash(key);
    
    if (!this.table[index]) {
      this.table[index] = [];
    }
    
    // Check if key exists and update
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index][i][1] = value;
        return;
      }
    }
    
    // If key doesn't exist, add new key-value pair
    this.table[index].push([key, value]);
  }
  
  // Get a value by key
  get(key) {
    const index = this._hash(key);
    
    if (!this.table[index]) {
      return undefined;
    }
    
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        return this.table[index][i][1];
      }
    }
    
    return undefined;
  }
  
  // Remove a key-value pair
  remove(key) {
    const index = this._hash(key);
    
    if (!this.table[index]) {
      return false;
    }
    
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        return true;
      }
    }
    
    return false;
  }
  
  // Get all keys
  keys() {
    const keysArr = [];
    
    for (let i = 0; i < this.table.length; i++) {
      if this.table[i]) {
        for (let j = 0; j < this.table[i].length; j++) {
          keysArr.push(this.table[i][j][0]);
        }
      }
    }
    
    return keysArr;
  }
  
  // Get all values
  values() {
    const valuesArr = [];
    
    for (let i = 0; i < this.table.length; i++) {
      if (this.table[i]) {
        for (let j = 0; j < this.table[i].length; j++) {
          valuesArr.push(this.table[i][j][1]);
        }
      }
    }
    
    return valuesArr;
  }
}

// Usage example
const ht = new HashTable(17);
ht.set("maroon", "#800000");
ht.set("yellow", "#FFFF00");
ht.set("olive", "#808000");
ht.set("salmon", "#FA8072");

console.log(ht.get("maroon")); // Output: #800000
console.log(ht.get("yellow")); // Output: #FFFF00
console.log(ht.keys()); // Output: ['maroon', 'yellow', 'olive', 'salmon']
ht.remove("olive");
console.log(ht.keys()); // Output: ['maroon', 'yellow', 'salmon']

Time Complexity Analysis​

OperationAverage CaseWorst Case
InsertO(1)O(n)
DeleteO(1)O(n)
SearchO(1)O(n)

Hash tables provide near-constant time operations on average, but performance degrades with many collisions.

Trees​

Trees are hierarchical data structures with a root node and child nodes.

Binary Search Tree Implementation​

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

class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  
  // Insert a value into the BST
  insert(value) {
    const newNode = new TreeNode(value);
    
    if (!this.root) {
      this.root = newNode;
      return this;
    }
    
    let current = this.root;
    
    while (true) {
      if (value === current.value) return undefined; // Duplicate values not allowed
      
      if (value < current.value) {
        if (!current.left) {
          current.left = newNode;
          return this;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          return this;
        }
        current = current.right;
      }
    }
  }
  
  // Find a value in the BST
  find(value) {
    if (!this.root) return false;
    
    let current = this.root;
    let found = false;
    
    while (current && !found) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        found = true;
      }
    }
    
    if (!found) return false;
    return current;
  }
  
  // Check if a value exists in the BST
  contains(value) {
    if (!this.root) return false;
    
    let current = this.root;
    
    while (current) {
      if (value < current.value) {
        current = current.left;
      } else if (value > current.value) {
        current = current.right;
      } else {
        return true;
      }
    }
    
    return false;
  }
  
  // Breadth-First Search (level by level)
  bfs() {
    const data = [];
    const queue = [];
    let node = this.root;
    
    if (!node) return data;
    
    queue.push(node);
    
    while (queue.length) {
      node = queue.shift();
      data.push(node.value);
      
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    
    return data;
  }
  
  // Depth-First Search: Pre-order (node, left, right)
  dfsPreOrder() {
    const data = [];
    
    function traverse(node) {
      data.push(node.value);
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    }
    
    if (this.root) traverse(this.root);
    return data;
  }
  
  // Depth-First Search: In-order (left, node, right)
  dfsInOrder() {
    const data = [];
    
    function traverse(node) {
      if (node.left) traverse(node.left);
      data.push(node.value);
      if (node.right) traverse(node.right);
    }
    
    if (this.root) traverse(this.root);
    return data;
  }
  
  // Depth-First Search: Post-order (left, right, node)
  dfsPostOrder() {
    const data = [];
    
    function traverse(node) {
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
      data.push(node.value);
    }
    
    if (this.root) traverse(this.root);
    return data;
  }
}

// Usage example
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(6);
bst.insert(15);
bst.insert(3);
bst.insert(8);
bst.insert(20);

console.log(bst.bfs()); // Output: [10, 6, 15, 3, 8, 20]
console.log(bst.dfsPreOrder()); // Output: [10, 6, 3, 8, 15, 20]
console.log(bst.dfsInOrder()); // Output: [3, 6, 8, 10, 15, 20]
console.log(bst.dfsPostOrder()); // Output: [3, 8, 6, 20, 15, 10]

Time Complexity Analysis​

OperationAverage CaseWorst Case
AccessO(log n)O(n)
SearchO(log n)O(n)
InsertionO(log n)O(n)
DeletionO(log n)O(n)

Binary search trees provide efficient operations when balanced, but can degrade to linear time if unbalanced.

Red-Black Trees​

Red-Black Trees are self-balancing binary search trees that maintain balance through a set of properties and rebalancing operations, ensuring O(log n) worst-case time complexity for basic operations.

Key Properties​

  1. Every node is either red or black
  2. The root is always black
  3. No red node has a red child (red nodes can only have black children)
  4. Every path from the root to any leaf contains the same number of black nodes
  5. All NULL pointers (leaves) are considered black

Implementation​

class RedBlackNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.color = "RED"; // New nodes are always red
  }
}

class RedBlackTree {
  constructor() {
    this.NIL = new RedBlackNode(null); // Sentinel node
    this.NIL.color = "BLACK";
    this.NIL.left = null;
    this.NIL.right = null;
    this.root = this.NIL;
  }
  
  // Left rotation for balancing
  leftRotate(x) {
    const y = x.right;
    x.right = y.left;
    
    if (y.left !== this.NIL) {
      y.left.parent = x;
    }
    
    y.parent = x.parent;
    
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
    
    y.left = x;
    x.parent = y;
  }
  
  // Right rotation for balancing
  rightRotate(y) {
    const x = y.left;
    y.left = x.right;
    
    if (x.right !== this.NIL) {
      x.right.parent = y;
    }
    
    x.parent = y.parent;
    
    if (y.parent === null) {
      this.root = x;
    } else if (y === y.parent.left) {
      y.parent.left = x;
    } else {
      y.parent.right = x;
    }
    
    x.right = y;
    y.parent = x;
  }
  
  // Insert a new value
  insert(value) {
    const newNode = new RedBlackNode(value);
    newNode.left = this.NIL;
    newNode.right = this.NIL;
    
    let y = null;
    let x = this.root;
    
    // Find the position to insert
    while (x !== this.NIL) {
      y = x;
      if (newNode.value < x.value) {
        x = x.left;
      } else {
        x = x.right;
      }
    }
    
    newNode.parent = y;
    
    if (y === null) {
      this.root = newNode; // Tree was empty
    } else if (newNode.value < y.value) {
      y.left = newNode;
    } else {
      y.right = newNode;
    }
    
    // If tree was empty, color the root black and return
    if (newNode.parent === null) {
      newNode.color = "BLACK";
      return;
    }
    
    // If grandparent is null, we're done
    if (newNode.parent.parent === null) {
      return;
    }
    
    // Fix the tree to maintain Red-Black properties
    this.fixInsert(newNode);
  }
  
  // Fix Red-Black Tree properties after insertion
  fixInsert(k) {
    let u;
    
    while (k.parent.color === "RED") {
      if (k.parent === k.parent.parent.right) {
        u = k.parent.parent.left; // Uncle
        
        if (u.color === "RED") {
          // Case 1: Uncle is red - recolor
          u.color = "BLACK";
          k.parent.color = "BLACK";
          k.parent.parent.color = "RED";
          k = k.parent.parent;
        } else {
          if (k === k.parent.left) {
            // Case 2: Uncle is black and k is a left child
            k = k.parent;
            this.rightRotate(k);
          }
          
          // Case 3: Uncle is black and k is a right child
          k.parent.color = "BLACK";
          k.parent.parent.color = "RED";
          this.leftRotate(k.parent.parent);
        }
      } else {
        u = k.parent.parent.right; // Uncle
        
        if (u.color === "RED") {
          // Case 1: Uncle is red - recolor
          u.color = "BLACK";
          k.parent.color = "BLACK";
          k.parent.parent.color = "RED";
          k = k.parent.parent;
        } else {
          if (k === k.parent.right) {
            // Case 2: Uncle is black and k is a right child
            k = k.parent;
            this.leftRotate(k);
          }
          
          // Case 3: Uncle is black and k is a left child
          k.parent.color = "BLACK";
          k.parent.parent.color = "RED";
          this.rightRotate(k.parent.parent);
        }
      }
      
      if (k === this.root) {
        break;
      }
    }
    
    this.root.color = "BLACK";
  }
  
  // Search for a value
  search(value) {
    return this._searchRecursive(this.root, value);
  }
  
  _searchRecursive(node, value) {
    if (node === this.NIL) return false;
    
    if (value === node.value) {
      return true;
    }
    
    if (value < node.value) {
      return this._searchRecursive(node.left, value);
    }
    
    return this._searchRecursive(node.right, value);
  }
  
  // Inorder traversal
  inOrder() {
    const result = [];
    this._inOrderRecursive(this.root, result);
    return result;
  }
  
  _inOrderRecursive(node, result) {
    if (node === this.NIL) return;
    
    this._inOrderRecursive(node.left, result);
    result.push(`${node.value}(${node.color})`);
    this._inOrderRecursive(node.right, result);
  }
}

// Usage example
const rbTree = new RedBlackTree();
[7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13].forEach(val => rbTree.insert(val));

console.log(rbTree.search(8)); // true
console.log(rbTree.search(9)); // false
console.log(rbTree.inOrder()); // Sorted list with color information

Visualization​

To understand Red-Black Trees better, let's see what happens when we insert values:

  1. Initial empty tree: Just the root (BLACK)
  2. Insert 7: Root is always BLACK
  3. Insert 3: 3 is RED, as a child of BLACK 7
  4. Insert 18: 18 is RED, as a right child of BLACK 7
  5. Insert 10: 10 is RED, but its parent (18) is also RED, violating property 3
    • After rebalancing: 7 is BLACK, with children 3 (BLACK) and 18 (BLACK)
    • 10 becomes a RED child of 18

Each insertion may trigger rotations and color changes to maintain the Red-Black properties.

Time Complexity Analysis​

OperationAverage CaseWorst Case
AccessO(log n)O(log n)
SearchO(log n)O(log n)
InsertionO(log n)O(log n)
DeletionO(log n)O(log n)

Red-Black Trees guarantee O(log n) worst-case performance for basic operations, making them suitable for applications where consistent performance is critical, such as in database indexes and system implementations.

Applications​

  1. Implementing associative arrays in languages like Java (TreeMap) and C++ (std::map)
  2. Process scheduling in operating systems
  3. Database indexing for consistent lookup times
  4. Computational geometry algorithms
  5. K-means variant algorithms for nearest neighbor search

Graphs​

Graphs consist of vertices (nodes) connected by edges, representing relationships between entities.

Implementation: Adjacency List​

class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  
  // Add a vertex to the graph
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  
  // Add an edge between two vertices
  addEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
      this.adjacencyList[vertex1].push(vertex2);
      this.adjacencyList[vertex2].push(vertex1); // For undirected graph
    }
  }
  
  // Remove an edge between two vertices
  removeEdge(vertex1, vertex2) {
    if (this.adjacencyList[vertex1] && this.adjacencyList[vertex2]) {
      this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
        v => v !== vertex2
      );
      this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
        v => v !== vertex1
      );
    }
  }
  
  // Remove a vertex and all its edges
  removeVertex(vertex) {
    if (!this.adjacencyList[vertex]) return;
    
    while (this.adjacencyList[vertex].length) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    
    delete this.adjacencyList[vertex];
  }
  
  // Depth-First Traversal (recursive)
  depthFirstRecursive(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;
    
    (function dfs(vertex) {
      if (!vertex) return null;
      
      visited[vertex] = true;
      result.push(vertex);
      
      adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          return dfs(neighbor);
        }
      });
    })(start);
    
    return result;
  }
  
  // Depth-First Traversal (iterative)
  depthFirstIterative(start) {
    const result = [];
    const visited = {};
    const stack = [start];
    visited[start] = true;
    
    while (stack.length) {
      const currentVertex = stack.pop();
      result.push(currentVertex);
      
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    
    return result;
  }
  
  // Breadth-First Traversal
  breadthFirst(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    visited[start] = true;
    
    while (queue.length) {
      const currentVertex = queue.shift();
      result.push(currentVertex);
      
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    
    return result;
  }
}

// Usage example
const g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addVertex("C");
g.addVertex("D");
g.addVertex("E");
g.addVertex("F");

g.addEdge("A", "B");
g.addEdge("A", "C");
g.addEdge("B", "D");
g.addEdge("C", "E");
g.addEdge("D", "E");
g.addEdge("D", "F");
g.addEdge("E", "F");

console.log(g.depthFirstRecursive("A")); // Output: ['A', 'B', 'D', 'E', 'C', 'F']
console.log(g.breadthFirst("A")); // Output: ['A', 'B', 'C', 'D', 'E', 'F']

Time Complexity Analysis​

OperationAdjacency ListAdjacency Matrix
Add VertexO(1)O(V²)
Add EdgeO(1)O(1)
Remove VertexO(V + E)O(V²)
Remove EdgeO(E)O(1)
QueryO(V)O(1)
StorageO(V + E)O(V²)

V = number of vertices, E = number of edges

Heaps​

Heaps are specialized tree-based data structures that satisfy the heap property.

Implementation: Max Heap​

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  
  // Helper methods for index calculations
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  
  getLeftChildIndex(index) {
    return 2 * index + 1;
  }
  
  getRightChildIndex(index) {
    return 2 * index + 2;
  }
  
  // Insert a value into the heap
  insert(value) {
    this.values.push(value);
    this.bubbleUp();
    return this;
  }
  
  // Move the last element up to its correct position
  bubbleUp() {
    let index = this.values.length - 1;
    const element = this.values[index];
    
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);
      const parent = this.values[parentIndex];
      
      if (element <= parent) break;
      
      // Swap with parent
      this.values[parentIndex] = element;
      this.values[index] = parent;
      index = parentIndex;
    }
  }
  
  // Extract the maximum element
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    
    return max;
  }
  
  // Move the root element down to its correct position
  sinkDown() {
    let index = 0;
    const length = this.values.length;
    const element = this.values[0];
    
    while (true) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);
      let leftChild, rightChild;
      let swap = null;
      
      if (leftChildIndex < length) {
        leftChild = this.values[leftChildIndex];
        if (leftChild > element) {
          swap = leftChildIndex;
        }
      }
      
      if (rightChildIndex < length) {
        rightChild = this.values[rightChildIndex];
        if (
          (swap === null && rightChild > element) || 
          (swap !== null && rightChild > leftChild)
        ) {
          swap = rightChildIndex;
        }
      }
      
      if (swap === null) break;
      
      // Swap with child
      this.values[index] = this.values[swap];
      this.values[swap] = element;
      index = swap;
    }
  }
}

// Usage example
const heap = new MaxBinaryHeap();
heap.insert(41);
heap.insert(39);
heap.insert(33);
heap.insert(18);
heap.insert(27);
heap.insert(12);
heap.insert(55);

console.log(heap.values); // [55, 39, 41, 18, 27, 12, 33]
console.log(heap.extractMax()); // 55
console.log(heap.values); // [41, 39, 33, 18, 27, 12]

Time Complexity Analysis​

OperationTime Complexity
InsertionO(log n)
RemovalO(log n)
SearchO(n)
PeekO(1)
HeapifyO(n)

Choosing the Right Data Structure​

Selecting the appropriate data structure depends on:

  1. Operations Required: What operations will be performed most frequently?
  2. Time Complexity: What performance characteristics are needed?
  3. Memory Constraints: How much memory is available?
  4. Data Volume: How much data needs to be handled?
  5. Data Organization: What is the natural structure of the data?

Common Use Cases​

Data StructureBest For
ArraySequential access, direct indexing
Linked ListFrequent insertions/deletions at various positions
StackLIFO operations, function calls, undo mechanisms
QueueFIFO operations, order processing, BFS algorithms
Hash TableFast lookups, caches, dictionaries
Binary Search TreeOrdered data, range queries, moderate insertions
HeapPriority processing, scheduling, finding min/max
GraphRelationship mapping, networks, pathfinding

Conclusion​

Data structures provide the foundation for efficient algorithms and software. Understanding their properties, operations, and performance characteristics allows you to make informed decisions about which structure to use for a particular problem.

As your applications grow in complexity, the importance of choosing the right data structure becomes more significant. A well-chosen data structure can be the difference between an application that scales gracefully and one that breaks under load.

In the upcoming articles, we'll dive deeper into each data structure, exploring advanced operations, variants, and real-world applications. We'll also examine specialized data structures designed for specific use cases and constraints.