Linked lists are O(N) random insertion as you need to traverse the tree to locate the correct node. The only way that they are always O(1) are a degenerate case better suited for another data structure. Aka if you want a queue then use a ring buffer not a linked list.