With a bit of trickery, inserting a new element before a given element can be done in constant time: insert the new element after the given element and swap the data in the two elements:
new.next = here.next here.next = new swap(here.data, new.data)
The trick’s no help with deleting an element before a given element.
This page last modified on 24 January 2006.