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

Tips for Competitive Programming

The Art of Making Programming Problems

Interactive Tasks

Introduction to Competitive Programming

Introduction to Dynamic Programming

Fracturing Search

Union-find Disjoint set