 Solution

A doubly linked list supports backward traversal and removal of a known linked list node in constant time, because that node supplies its own predecessor. In a singly linked list, removing a known node generally requires finding its predecessor by a forward scan unless the caller already supplies it. Inserting before a known node has the same advantage.

The cost is another pointer per node, more link assignments on every update, and a stronger consistency invariant to maintain. HenceThis does not make locating an arbitrary data value faster: a search still takes linear time in the worst case.