> That O(1) splice must also be accompanied with an iteration. I don't think it necessarily must, but it tends to be. People tend to keep pointers to elements

> That O(1) splice must also be accompanied with an iteration. I don't think it necessarily must, but it tends to be. People tend to keep pointers to elements of the list all over the place, so if you have the right 3 pointers (being and end of list you want to insert, and position in another list), then you can do it in O(1). If not, and you need to traverse the lists... as you mentioned there are other data-structures that might be much better.