Data Structures Exam Notes

1. Difference between Double Linked List and Array

2. Single, Double, Circular Linked List

Basic Operations: Insertion, Deletion, Traversal

3. Double Linked List Node Structure

struct Node {
    int data;
    struct Node* previous;
    struct Node* next;
};

Three fields: data, previous pointer, next pointer

4. Strictly Binary Tree (Full Binary Tree)

Every node has either 0 children (leaf) or exactly 2 children. No node has 1 child.

5. Properties of Red-Black Tree

1. Every node is Red or Black
2. Root is always Black
3. All leaves (NULL) are Black
4. If node is Red, both children must be Black
5. Every path has same count of Black nodes
6. New nodes inserted as Red

6. AVL Tree Definition

Height-Balanced Binary Search Tree where Balance Factor of every node is -1, 0, or +1.

7. AVL Tree Rotations

1. Double Linked List: Insertion at End

void insertAtEnd(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;

    if(head == NULL) {
        newNode->previous = NULL;
        head = newNode;
    } else {
        struct Node* temp = head;
        while(temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->previous = temp;
    }
}

2. Stack Using Linked List

Implements LIFO (Last In First Out). Top pointer points to most recent node.

struct Node {
    int data;
    struct Node* next;
}*top = NULL;

void push(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL) {
        printf("Stack Overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

void pop() {
    if(top == NULL) {
        printf("Stack Underflow\n");
        return;
    }
    struct Node* temp = top;
    top = temp->next;
    free(temp);
}

3. AVL Tree Insertion with Example

Steps: 1) BST Insertion 2) Update heights 3) Check Balance Factor 4) Rotate if needed

4. Binary Tree Traversal

void inorder(struct Node* root) {
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

5. Single Linked List: Insertion Operations

// Insert at Beginning - O(1)
void insertAtBeginning(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL) return;
    newNode->data = value;
    newNode->next = head;
    head = newNode;
}

// Insert at End - O(n)
void insertAtEnd(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL) return;
    newNode->data = value;
    newNode->next = NULL;
    if(head == NULL) {
        head = newNode;
        return;
    }
    struct Node* temp = head;
    while(temp->next != NULL) temp = temp->next;
    temp->next = newNode;
}

// Insert After Location - O(n)
void insertAfter(int value, int location) {
    if(head == NULL) return;
    struct Node* temp = head;
    while(temp != NULL && temp->data != location) {
        temp = temp->next;
    }
    if(temp == NULL) return; // Location not found
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL) return;
    newNode->data = value;
    newNode->next = temp->next;
    temp->next = newNode;
}

6. Construct Binary Search Tree

Rule: First value = Root. If value < Root → Left. If value > Root → Right.

Problem: Construct BST for: 50, 30, 70, 20, 40, 60, 80

7. Tree Insertion Algorithm

struct Node* insert(struct Node* node, int key) {
    if(node == NULL) {
        struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
        if(temp == NULL) return NULL;
        temp->data = key;
        temp->left = temp->right = NULL;
        return temp;
    }
    if(key < node->data)
        node->left = insert(node->left, key);
    else if(key > node->data)
        node->right = insert(node->right, key);
    return node;
}

8. BST Deletion (3 Cases)

struct Node* deleteNode(struct Node* root, int key) {
    if(root == NULL) return NULL;
    
    if(key < root->data)
        root->left = deleteNode(root->left, key);
    else if(key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // Node found
        if(root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        }
        else if(root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
        // Two children: Get inorder successor
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

9. Queue Using Linked List

Implements FIFO (First In First Out). Uses front and rear pointers.

struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node *front, *rear;
};

void enqueue(struct Queue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if(newNode == NULL) {
        printf("Queue Overflow\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if(q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

void dequeue(struct Queue* q) {
    if(q->front == NULL) {
        printf("Queue Underflow\n");
        return;
    }
    struct Node* temp = q->front;
    q->front = q->front->next;
    if(q->front == NULL) q->rear = NULL;
    free(temp);
}