There’s a particularly lovely version due to Chris Okasaki:
type 'a de_list = 'a list * 'a list
where the “list” is the concatenation of the first list and the reverse of the second. The idea being that you can push or pop onto the front or back very cheaply, until you’re popping off an empty list, at which point you must reverse the other list before continuing. [hope that was clear]
IIRC Okasaki has a book of “purely functional datastructures” in which this is all laid-out, though I just heard it from a friend a few decades ago.