Data Structures and Algorithms Review

Searching a List

• Searching involves looking through a data structure to find an item.
• Techniques include using loops and specialized methods.

Search Methods

• Linear Search: Iterates through each item in the list.
  • Time Complexity: O(n), where n is the number of items.
• Binary Search: Requires a sorted list and involves repeatedly dividing the list in half to find the target.
  • Steps:
  1. Set the first index to 0 and last index to the length of the list minus one.
  2. Find the middle index: ext{middle} = rac{ ext{first} + ext{last}}{2}.
  3. Compare the target value with the middle value:
     • If the target is equal to the middle value, return the middle index.
     • If the target is less, adjust the last index to middle - 1.
     • If more, adjust the first index to middle + 1.
  4. Repeat until the first index is greater than last index or the item is found.
  • Time Complexity: O( ext{log } n).

Hashtables

• A hashtable uses a key-value mapping and allows for fast data retrieval.
• Properties:
  • Keys must be unique.
  • Common operations:
  • Insertion: O(1) average time complexity.
  • Search: O(1) average time complexity.
• Collisions:
  • When two keys hash to the same index. Methods to resolve include:
  • Open Addressing: Searches for the next available spot.
  • Chaining: Allows multiple items at the same index using a linked list.

Sorting Algorithms

1. Bubble Sort: Compares adjacent pairs and swaps them to form a sorted list.

   • Time Complexity: O(n^2).

2. Insertion Sort: Builds a sorted sublist by inserting elements from unsorted to sorted.

   • Time Complexity: O(n^2).

3. Shell Sort: Generalization of insertion sort that allows the exchange of items far apart.

   • Time Complexity: Varies based on gap sequence.

4. Merge Sort: A divide-and-conquer algorithm that splits the input into smaller pieces, sorts them, then merges them back.

   • Time Complexity: O(n ext{ log } n).

5. Quick Sort: Another divide-and-conquer algorithm that selects a pivot element and partitions the other elements.

   • Time Complexity: average O(n ext{ log } n), worst-case O(n^2).

Trees

• Binary Tree Structure:
  • Each node can have at most two children.
  • Nodes can be classified as:
    • Internal Nodes: Nodes with at least one child.
    • Leaf Nodes: Nodes without children.
• Binary Search Tree (BST):
  • Left child < Parent < Right child.
  • Used for efficient searching, insertion, and deletion.

Traversal Types:

1. In-order: Left, Root, Right.
2. Pre-order: Root, Left, Right.
3. Post-order: Left, Right, Root.

Priority Queues

• A data structure where each element has a priority level.
• Items are served in order of priority, not just in order of insertion.
• Variants include:
  • List-based: Always keeps the list sorted.
  • Heap-based: Uses a binary heap to maintain order and allows faster delete operations.

Each of these techniques and structures is fundamental to understanding data management and algorithm performance in programming.