Linked list with checkpoints for fast indexed insert and get

Build a sequence of strings that supports insert(index, value) (before the element now at index, or at the end) and get(index). Store it as a linked list, and keep a checkpoint pointer to every k-th node so that a lookup starts from the nearest checkpoint and walks fewer than k links.

The hard part is insertion: after inserting, every checkpoint at or after that position must still point at the node at its multiple of k. Show how a doubly linked list lets you shift those checkpoints by one node each instead of rescanning, and give the cost of both operations.