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 2006 January 24.