---
id: 699c2dd0e2e1f947791f33fc
title: Data Structures Review
challengeType: 31
dashedName: review-data-structures-js
---

# --interactive--
 
## Algorithms and Big O Notation

- **Algorithms**: A set of unambiguous instructions for solving a problem or carrying out a task. Algorithms must finish in a finite number of steps and each step must be precise and unambiguous.

- **Big O Notation**: Describes the worst-case performance, or growth rate, of an algorithm as the input size increases. It focuses on how resource usage grows with input size, ignoring constant factors and lower-order terms.

### Common Time Complexities

- **O(1) - Constant Time**: Algorithm takes the same amount of time regardless of input size.

:::interactive_editor

```js
function checkEvenOrOdd(number) {
  if (number % 2 === 0) {
    return "Even";
  } else {
    return "Odd";
  }
}

console.log(checkEvenOrOdd(4)) // "Even"
console.log(checkEvenOrOdd(5)) // "Odd"
```

:::

- **O(log n) - Logarithmic Time**: Time increases slowly as input grows. Common in algorithms that repeatedly reduce problem size by a fraction (like Binary Search).

- **O(n) - Linear Time**: Running time increases proportionally to input size.

```js
for (const grade of grades) { // grades is an array
  console.log(grade);
}
```

- **O(n log n) - Log-Linear Time**: Common time complexity of efficient sorting algorithms like Merge Sort and Quick Sort.

- **O(n²) - Quadratic Time**: Running time increases quadratically. Often seen in nested loops.

:::interactive_editor

```js
const n = 3;

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    console.log("Hello, World!");
  }
}
```

:::

### Space Complexity

- **O(1) - Constant Space**: Algorithm uses same amount of memory regardless of input size.
- **O(n) - Linear Space**: Memory usage grows proportionally with input size.
- **O(n²) - Quadratic Space**: Memory usage grows quadratically with input size.

## Problem-Solving Techniques

- **Understanding the Problem**: Read the problem statement multiple times. Identify the input, expected output, and how to transform input to output.

- **Pseudocode**: High-level description of algorithm logic that is language-independent. Uses common written language mixed with programming constructs like `IF`, `ELSE`, `FOR`, `WHILE`.

```md
GET original_string
SET reversed_string = ""
FOR EACH character IN original_string:
  ADD character TO THE BEGINNING OF reversed_string
DISPLAY reversed_string
```

- **Edge Cases**: Specific, valid inputs that occur at the boundaries of what an algorithm should handle. Always consider and test edge cases.

## Arrays

- **Static Arrays**: Have a fixed size determined at initialization. Elements stored in adjacent memory locations. Size cannot be changed during program execution.

- **Dynamic Arrays**: Can grow or shrink automatically during program execution. Handle resizing through automatic copying to larger arrays when needed.

### Dynamic Arrays Implementation in JavaScript

:::interactive_editor

```js
let numbers = [3, 4, 5, 6];
// Access elements
console.log(numbers[0])  // 3

// Update elements
numbers[2] = 16
console.log([...numbers]);  // [3, 4, 16, 6]

// Add elements
numbers.push(7)
console.log([...numbers]);  // [3, 4, 16, 6, 7] 

// Add at a specific index
numbers.splice(3, 0, 15);
console.log([...numbers]);  // [3, 4, 16, 15, 6, 7]

// Remove elements
numbers.splice(2, 1);  // Remove at specific index
console.log([...numbers]);  // [3, 4, 15, 6, 7]

numbers.pop()   // Remove last element
console.log([...numbers]); // [3, 4, 15, 6]
```

:::

### Time Complexities for Dynamic Arrays

- **Access**: O(1)
- **Insert at end**: O(1) average, O(n) when resizing needed
- **Insert in middle**: O(n)
- **Delete**: O(n) for middle, O(1) for end

## Stacks

- **Stacks**: Last-In, First-Out (LIFO) data structure. Elements added and removed from the top only.

- **Push Operation**: Adding an element to the top of the stack. Time complexity: O(1).

- **Pop Operation**: Removing an element from the top of the stack. Time complexity: O(1).

:::interactive_editor

```js
// Using JavaScript array as a stack

let stack = [];

// Push operations
stack.push(1);
stack.push(2);
stack.push(3);
console.log([...stack]);  // [1, 2, 3]

// Pop operations
let topElement = stack.pop();
console.log(topElement);  // 3
console.log([...stack]);  // [1, 2]
```

:::

## Queues

- **Queues**: First-In, First-Out (FIFO) data structure. Elements added to the back and removed from the front.

- **Enqueue Operation**: Adding an element to the back of the queue. Time complexity: O(1).

- **Dequeue Operation**: Removing an element from the front of the queue. Time complexity: O(1).

:::interactive_editor

```js
// Using JavaScript array as a queue
let queue = [];

// Enqueue operations
queue.push(1);
queue.push(2);
queue.push(3);
console.log([...queue]);  // [1, 2, 3]

// Dequeue operations
let firstElement = queue.shift();
console.log(firstElement);  // 1
console.log([...queue]);  // [2, 3]
```

:::

## Linked Lists

- **Linked Lists**: Linear data structure where each node contains data and a reference to the next node. Nodes are connected like a chain.

### Singly Linked Lists

- **Structure**: Each node has data and one reference to the next node.
- **Traversal**: Can only move forward from head to tail.
- **Head Node**: First node in the list, usually the only directly accessible node.
- **Tail Node**: Last node in the list, points to `null`.

### Operations and Time Complexities

- **Insert at beginning**: O(1)
- **Insert at end**: O(n) - must traverse to end
- **Insert in middle**: O(n) - must traverse to position
- **Delete from beginning**: O(1)
- **Delete from end**: O(n) - must traverse to find previous node
- **Delete from middle**: O(n) - must traverse to find node

### Doubly Linked Lists

- **Structure**: Each node has data and two references: next node and previous node.
- **Traversal**: Can move in both directions.
- **Memory**: Requires more memory than singly linked lists due to extra reference.

## When to Use Each Data Structure

- **Arrays (dynamic arrays)**: When you need ordered, indexed access and don't know size in advance
- **Stacks**: For LIFO operations (undo functionality, expression evaluation, backtracking)
- **Queues**: For FIFO operations (task scheduling, breadth-first search)
- **Linked Lists**: When frequent insertion/deletion at beginning, unknown size, no random access needed

# --assignment--

Review the Data Structures topics and concepts.
