Abstract Data Types

Abstract Data Types (ADTs) form the foundation of data structure design. An ADT consists of three main components: data objects, basic operations, and data relationships. The implementation details are hidden from the user, allowing for modular and maintainable code design.

Linear Data Structures

Sequential Lists

Sequential lists, implemented using arrays, store elements in contiguous memory locations. The key characteristics include:

• Logical adjacency corresponds to physical adjacency in memory
• Direct access to elements via indices (O(1) time complexity)
• Insertion and deletion operations may require shifting elements (O(n) time complexity)

Linked Lists

Linked lists use nodes connected through pointers rather than contiguous memory. Common variants include:

• Singly linked lists: Each node contains data and a pointer to the next node
• Doubly linked lists: Each node contains data and pointers to both next and previous nodes
• Circular linked lists: The last node points back to the first node, forming a circle

Stacks and Queues

Stacks follow the Last-In-First-Out (LIFO) principle, while queues follow the First-In-First-Out (FIFO) principle. These structures are fundamental in algorithm design and have numerous applications in computer science.

Tree Structures

Binary Trees

Binary trees are hierarchical data structures where each node has at most two children. They can be implemented using either sequential or linked structures. Key properties include:

• The maximum number of nodes at level i is 2^i
• The maximum number of nodes in a binary tree of height h is 2^h - 1
• The minimum height of a binary tree with n nodes is ⌊log₂n⌋ + 1

Binary Search Trees

Binary search trees (BSTs) maintain the property that for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node. This enables efficient search, insertion, and deletion operations with average time complexity of O(log n).

Tree Traversal Methods

Common tree traversal techniques include:

• In-order traversal: Left subtree, root, right subtree
• Pre-order traversal: Root, left subtree, right subtree
• Post-order traversal: Left subtree, right subtree, root
• Level-order traversal: Level by level using a queue

Graph Structures

Graph Representations

Graphs can be represented using:

• Adjacency matrix: A 2D array where matrix[i][j] indicates the presence of an edge between vertices i and j
• Adjacency list: An array of linked lists where each list contains all adjacent vertices for a given vertex

Graph Traversal

Graph traversal algorithms include:

• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking
• Breadth-First Search (BFS): Explores all neighbors at the present depth before moving to nodes at the next depth level

Graph Algorithms

Key graph algorithms include:

• Topological sorting: Ordering vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering
• Minimum spanning tree: A subset of edges that connects all vertices with the minimum total edge weight
• Shortest path algorithms: Finding the shortest path between two vertices (e.g., Dijkstra's algorithm, Floyd-Warshall algorithm)

Hashing

Hash Functions

Hash functions map keys to array indices. Common construction methods include:

• Division method: h(key) = key % table_size
• Multiplication method: h(key) = ⌊m(key * A) mod 1⌋ where 0 < A < 1
• Folding method: Splitting the key into parts and combining them
• Mid-square method: Squaring the key and extracting middle digits

Collision Resolution

When collisions occur (different keys map to the same index), resolution techniques include:

• Separate chaining: Each bucket contains a linked list of entries
• Open addressing: Probing for alternative slots (linear probing, quadratic probing, double hashing)

Performance Analysis

The performance of hash tables depends on:

• Load factor: α = n/m where n is the number of entries and m is the table size
• The efficiency of the hash function
• The effectiveness of the collision resolution method

Advanced Data Structures

Heaps

Heaps are specialized tree-based data structures that satisfy the heap property. Common types include:

• Max-heap: Each parent node is greater than or equal to its children
• Min-heap: Each parent node is less than or equal to its children

Priority Queues

Priority queues are abstract data types that generalize queues, where each element has a priority. Heaps are commonly used to implement priority queues efficiently.

Tries

Tries (prefix trees) are tree-like structures used for storing strings. Each node represents a character of a string, and paths from the root to nodes represent stored strings.

Algorithm Design Techniques

Dynamic Programming

Dynamic programming solves complex problems by breaking them down into simpler subproblems. Key characteristics include:

• Overlapping subproblems
• Optimal substructure
• Memoization or tabulation for storing intermediate results

Greedy Algorithms

Greedy algorithms make locally optimal choices at each step with the hope of finding a global optimum. They work well for problems with the greedy-choice property, such as:

• Minimum spanning tree algorithms
• Huffman coding for data compression
• Fractional knapsack problem

Divide and Conquer

Divide and conquer algorithms solve problems by dividing them into smaller subproblems, solving them recursively, and combining their solutions. Examples include:

• Merge sort
• Quick sort
• Binary search

Implementation Examples

Merging Sorted Linked Lists

Node* mergeSortedLists(Node* list1, Node* list2) {
    Node dummy;  // Dummy node to simplify code
    Node* tail = &dummy;
    
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->data <= list2->data) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    
    // Attach remaining elements
    tail->next = (list1 != nullptr) ? list1 : list2;
    
    return dummy.next;
}

Counting Nodes with Degree 2 in a Binary Tree

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

int countNodesWithDegree2(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }
    
    int count = 0;
    if (root->left != nullptr && root->right != nullptr) {
        count = 1;
    }
    
    return count + countNodesWithDegree2(root->left) + countNodesWithDegree2(root->right);
}

Set Intersection Using Linked Lists

typedef struct SetNode {
    int value;
    struct SetNode* next;
} SetNode;

SetNode* createNode(int value) {
    SetNode* newNode = (SetNode*)malloc(sizeof(SetNode));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

void setIntersection(SetNode* setA, SetNode* setB, SetNode** result) {
    *result = NULL;
    SetNode* tail = NULL;
    
    while (setA != NULL) {
        SetNode* currentB = setB;
        while (currentB != NULL) {
            if (setA->value == currentB->value) {
                // Element found in both sets, add to result
                SetNode* newNode = createNode(setA->value);
                if (*result == NULL) {
                    *result = newNode;
                    tail = newNode;
                } else {
                    tail->next = newNode;
                    tail = newNode;
                }
                break; // Move to next element in setA
            }
            currentB = currentB->next;
        }
        setA = setA->next;
    }
}

Sorting Algorithms

Merge Sort

Merge sort is a divide-and-conquer algorithm that divides the input into smaller halves, sorts them, and then merges the sorted halves. It has a time complexity of O(n log n) in all cases and is stable.

Quick Sort

Quick sort is another divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot. Its average time complexity is O(n log n), but it has O(n²) in the worst case when the smallest or largest element is always chosen as the pivot.

Heap Sort

Heap sort uses a binary heap to sort elements. It first builds a max-heap from the input data, then repeatedly extracts the maximum element and rebuilds the heap. It has a time complexity of O(n log n) and is in-place.

Searching Algorithms

Binary Search

Binary search efficiently locates a target value within a sorted array by repeatedly dividing the search interval in half. It has a time complexity of O(log n).

Tree Search

Searching in a binary search tree follows the tree structure, comparing the target value with each node and moving left or right accordingly. The average time complexity is O(log n) for balanced trees and O(n) for degenerate trees.

Hash Table Search

Hash tables provide average-case O(1) time complexity for search operations, assuming a good hash function and appropriate load factor.