[penetraitor69]

My understanding is that push/pop from the front/back of linked lists are constant time, 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.

[dragontamer]

> 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

[penetraitor69]

Oh, gotcha; I just meant in the general case.