Data Structures

Data structures are fundamental building blocks for organizing and storing data in a way that allows for efficient access and modification. Understanding different data structures is crucial for writing performant and scalable software.

Common Data Structures

Arrays

Arrays are ordered collections of elements, accessed by an index. They provide fast access to elements if the index is known.

Characteristics: Fixed or dynamic size, elements stored contiguously in memory (typically), zero-based indexing.
Use Cases: Storing lists of items, implementing other data structures, lookups by index.

Example:

let numbers = [10, 20, 30, 40, 50];
console.log(numbers[0]); // Output: 10
console.log(numbers.length); // Output: 5
numbers.push(60); // Add an element to the end
console.log(numbers); // Output: [10, 20, 30, 40, 50, 60]

Linked Lists

Linked lists are linear data structures where elements are not stored contiguously. Each element (node) contains data and a reference (pointer) to the next node in the sequence.

Characteristics: Dynamic size, efficient insertion and deletion (especially at the beginning/end), slower access by index compared to arrays.
Use Cases: Implementing stacks and queues, managing dynamic collections where frequent insertions/deletions occur.

Example (Conceptual):

// Conceptual representation
// Node structure: { data: value, next: pointer }
// List: Node1 -> Node2 -> Node3 -> null
let head = { data: 'Apple', next: null };
let secondNode = { data: 'Banana', next: null };
head.next = secondNode;
// ... and so on

Stacks

Stacks are linear data structures that follow the Last-In, First-Out (LIFO) principle. Elements are added (pushed) and removed (popped) from the same end, called the top.

Characteristics: LIFO order, primary operations: push, pop, peek.
Use Cases: Function call stacks, expression evaluation, undo/redo features.

Example:

let stack = [];
stack.push('A'); // stack: ['A']
stack.push('B'); // stack: ['A', 'B']
console.log(stack.pop()); // Output: 'B', stack: ['A']
console.log(stack.peek()); // Output: 'A' (if peek is implemented)

Queues

Queues are linear data structures that follow the First-In, First-Out (FIFO) principle. Elements are added at one end (rear) and removed from the other end (front).

Characteristics: FIFO order, primary operations: enqueue, dequeue.
Use Cases: Managing tasks in order of arrival (e.g., print queues, request handling), breadth-first search.

Example:

let queue = [];
queue.push('Task 1'); // enqueue: queue: ['Task 1']
queue.push('Task 2'); // enqueue: queue: ['Task 1', 'Task 2']
console.log(queue.shift()); // dequeue: Output: 'Task 1', queue: ['Task 2']

Hash Tables (Maps/Dictionaries)

Hash tables store key-value pairs. They use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Characteristics: Efficient key-based lookups, insertions, and deletions (average O(1)), keys must be unique.
Use Cases: Caching, indexing databases, frequency counting, symbol tables.

Example:

let user = {
    id: 101,
    name: "Alice",
    email: "alice@example.com"
};
console.log(user.name); // Output: Alice
console.log(user['email']); // Output: alice@example.com

let userMap = new Map();
userMap.set('id', 101);
userMap.set('name', 'Alice');
console.log(userMap.get('name')); // Output: Alice

Trees

Trees are hierarchical data structures consisting of nodes connected by edges. They typically have a root node, and each node can have zero or more child nodes.

Characteristics: Hierarchical, efficient searching (e.g., Binary Search Trees), sorting, and representation of relationships.
Use Cases: File systems, organizational charts, syntax trees, searching algorithms.

Example (Binary Tree Node):

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

let root = new TreeNode(50);
root.left = new TreeNode(30);
root.right = new TreeNode(70);
root.left.left = new TreeNode(20);
root.left.right = new TreeNode(40);

Graphs

Graphs are non-linear data structures composed of nodes (vertices) connected by edges. They are used to represent relationships between objects.

Characteristics: Vertices and edges, can represent complex relationships (social networks, road maps), various traversal algorithms (BFS, DFS).
Use Cases: Social networks, routing algorithms, recommendation systems, network analysis.

Example (Adjacency List Representation):

// Represents a graph with vertices A, B, C, D
// A is connected to B and C
// B is connected to A and D
// C is connected to A
// D is connected to B
let graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
};

Choosing the Right Data Structure

The choice of data structure depends heavily on the specific problem requirements:

For fast access by index: Arrays
For frequent insertions/deletions: Linked Lists
For LIFO operations: Stacks
For FIFO operations: Queues
For key-value mappings and fast lookups: Hash Tables
For hierarchical relationships: Trees
For complex networks and relationships: Graphs

Understanding the time and space complexity of operations for each data structure is essential for optimizing algorithm performance.