> but that inserts in the middle necessitate looping through the linked list until you get to the correct index, which is a O(n) operation.

Not if you save the node you are working on. Inserting (when you have a node) is simply:

    NewNode = malloc(...) or new or something.
    NewNode.next = node.next
    node.next = NewNode