Sqrt linked lists



I present a (novel?) variation of a linked list, which allows for insertion, deletion and querying in worse case O(sqrt(n))

If these things interest you, you may like to look at:


// Written by Ryan Ong (z5419383)
// on 14/04/2022

/**
 * Sqrt Linked List!
 * I want to answer these queries in about sqrt(n) steps:
 *    - "insert this value at index i"
 *    - "remove the value at index i"
 *    - "what is the value at index i" 
 *
 * The main difficulty boils down to finding the node at index "i" quickly. For 
 * each range of length sqrtn, I would store the number of nodes in the range, 
 * and also a pointer to the first node in the range.
 * 
 * To find an index i would walk the ranges to find the best one, then walk 
 * through the nodes until index i. Every sqrtn queries, recalculate the ranges,
 * such that the number of steps never grows too large.
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TRUE 1
#define FALSE 0

#define CMD_INSERT 'I'
#define CMD_REMOVE 'R'
#define CMD_QUERY 'Q'
#define CMD_PRINT 'P'
#define CMD_UPDATE_RANGES 'U'

struct Range;

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

struct Range {
    int num_contained; // number of nodes in this range, usually around sqrt(N)
    struct Node *checkpoint;
    struct Range *next;
};

struct List {
    int num_contained; // total number of nodes, otherwise denoted as N
    struct Node *head;
    struct Range *range;
};

// initialise a sqrt linked list, given that it contains "first_val"
// [0 steps]
struct List *init(int first_val) {
    struct Node *first_node = malloc(sizeof(struct Node));
    first_node->data = first_val;
    first_node->next = NULL;
    
    struct Range *first_range = malloc(sizeof(struct Range));
    first_range->num_contained = 1;
    first_range->next = NULL;

    first_range->checkpoint = first_node;
    first_node->range = first_range;

    struct List *list = malloc(sizeof(struct List));
    list->num_contained = 1;
    list->head = first_node;
    list->range = first_range;
    
    return list;
}

// return the node at that index
// [2sqrt(N) steps]
struct Node *get_node(struct List *list, int index) {
    int total = 0;

    // step through the ranges until you find the range that covers this index
    struct Range *curr_range = list->range;
    while (total + curr_range->num_contained < index) {
        total += curr_range->num_contained;
        curr_range = curr_range->next;
    }

    // then, step through the nodes in this range until you reach the index
    struct Node *curr_node = curr_range->checkpoint;
    while (total + 1 <= index) {
        total++;
        curr_node = curr_node->next;
    }

    return curr_node;
}

// insert val after this index
// note that this function cannot deal with prepending
// [2sqrt(N) steps]
void insert(struct List *list, int index, int val) {
    struct Node *curr_node = get_node(list, index);
    
    struct Node *new_node = malloc(sizeof(struct Node));
    new_node->data = val;
    new_node->next = curr_node->next;
    new_node->range = curr_node->range;
    new_node->range->num_contained++;

    curr_node->next = new_node;
}

// remove the node at this index
// [2sqrt(N) steps]
void rem(struct List *list, int index) {
    struct Node *curr_node;
    if (index == 0) {
        curr_node = list->head;
        list->head = curr_node->next;
    } else {
        curr_node = get_node(list, index);
        get_node(list, index - 1)->next = curr_node->next;
    }

    curr_node->range->num_contained--;
    // edge case: the node to be removed is a checkpoint node, change the 
    // checkpoint to something else
    if (curr_node == curr_node->range->checkpoint) {
        curr_node->range->checkpoint = curr_node->next;
    }
    free(curr_node);
}

// return the data of the node at this index
// [2sqrt(N) steps]
int query(struct List *list, int index) {
    return get_node(list, index)->data;
}

// output the data of the entire list
// [N steps]
void print(struct List *list) {
    for (struct Node *node = list->head; node != NULL; node = node->next) {
        printf("%d ", node->data);
    }
    printf("\n");
}

// clear the linked list of ranges, and create a new one
// this should be called after every sqrt(N) updates
// [N steps]
void update_ranges(struct List *list) {
    int sqrtn = sqrt(list->num_contained);

    list->range = NULL;
    struct Range *prev_range = NULL;
    struct Node *curr_node = list->head;
    while (curr_node != NULL) {
        // initialise this_range
        struct Range *this_range = malloc(sizeof(struct Range));
        this_range->num_contained = 0;
        this_range->checkpoint = curr_node;
        while (curr_node != NULL && this_range->num_contained + 1 <= sqrtn) {
            this_range->num_contained++;
            curr_node = curr_node->next;
        }

        // add "this_range" to the linked list of ranges
        if (list->range == NULL) {
            list->range = this_range;
        } else {
            prev_range->next = this_range;
        }
        prev_range = this_range;
    }
}

// appendix of commands
void print_help() {
    printf("+-----------------+-------------------------------------------+\n");
    printf("|Command Name     | How to Use                                |\n");
    printf("+=================+===========================================+\n");
    printf("| INSERT          | Enter command: I [INDEX] [VALUE]          |\n");
    printf("+-----------------+-------------------------------------------+\n");
    printf("| REMOVE          | Enter command: R [INDEX]                  |\n");
    printf("+-----------------+-------------------------------------------+\n");
    printf("| QUERY           | Enter command: Q [INDEX]                  |\n");
    printf("+-----------------+-------------------------------------------+\n");
    printf("| PRINT           | Enter command: P                          |\n");
    printf("+-----------------+-------------------------------------------+\n");
    printf("| UPDATE RANGES   | Enter command: U                          |\n");
    printf("+-----------------+-------------------------------------------+\n");
    printf("\n");
}

int main(void) {
    //printf("What is the initial value in the sqrt linked list: ");
    int val, i;
    scanf("%d", &val);

    struct List *list = init(val);

    print_help();
    //printf("Enter command: ");

    // read in commands and perform them
    char option;
    while (scanf(" %c", &option) == 1) {
        if (option == CMD_INSERT) {
            scanf("%d %d", &i, &val);
            insert(list, i, val);
        } else if (option == CMD_REMOVE) {
            scanf("%d", &i);
            rem(list, i);
        } else if (option == CMD_QUERY) {
            scanf("%d", &i);
            printf("%d\n", query(list, i));
        } else if (option == CMD_UPDATE_RANGES) {
            update_ranges(list);
        } else if (option == CMD_PRINT) {
            print(list);
        } else {
            printf("Invalid command\n");
        }

        //printf("Enter command: ");
    }
    
    printf("\n");
    return 0;
}

Popular posts from this blog

Implementation tips for competitive programming

Introduction to Competitive Programming