A doubly linked list gives every node two pointers: next and prev. This makes backward traversal and deleting a node given its reference both O(1). The price is one extra pointer per node and more pointer updates on insertion and deletion — every operation must maintain both directions.
Doubly linked list with prev and next pointersEach node → [prev] [value] [next]
insertHead(v):
new.next := head; new.prev := null
if head ≠ null → head.prev := new
head := new
Deleting node x: x.prev.next := x.next; x.next.prev := x.prev
Forward & backward traversal both O(n).