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

/**
*    - "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 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->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) {
} 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;
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;
}

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