Data structures IRL — Part 2 A fun thing happened on an inter | Professor M

Data structures IRL — Part 2

A fun thing happened on an international flight I took in the middle of June. A long line to board. A long queue, if you will. A passenger in front of me turns around and asks if I’ll hold their spot in the queue as they walk away for a minute. “Absolutely,” I said.

But then I wondered. If they can walk away, it’s not a queue. As a data structure, a queue allows elements to be added to the back end and removed from the front end. Period. No other operations are permitted. A one-lane road for automobiles in a tunnel or a drive-through with a high curb is a queue. Once in, cars cannot drive away.

The line of passengers at the gate arranged themselves into a linked list (See Wiki page). The physical location per se doesn’t determine the order. Instead, everyone focuses on the person standing in front of them.

When the passenger walked away, I moved my pointer from them onto the person ahead of them. Plus, to undo this operation when they return, the passenger and I stored each other in mutual memories.

But of course, another condition has to be satisfied. The passenger would be able to return to the initial position in the line if and only if I hadn’t boarded yet. If I board fast, they’ll have to go to the back end. That’s precisely what happened.

I ran into this passenger on the plane. “I didn’t see you when I came back to the queue,” they said. I responded: “It wasn’t a queue; it was a linked list.”

P.S. The last paragraph exists only in my imagination, of course, but who cares.