Google Interview Question

They asked me to implement a restaurant queue using a doubly linked list, making sure all the operations—like adding or removing customers—work in constant O(1) time.