### 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:

- big O notation, otherwise known as time complexity. This is a useful method to measure how fast things are, rather than looking at the number of "steps" in the worse case. https://onecore.tech/informatics/5
- skip lists, a similar variation with a randomised aspect. It is faster than mine in the average case, but slower in the worse case. https://en.wikipedia.org/wiki/Skip_list
- B-trees, which although are not linked lists, are faster than mine in all cases. Not to be confused with binary trees. https://en.wikipedia.org/wiki/B-tree

// 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; }