Design tutorial

Welcome to the Design world. First move: build a class from simple parts.

You get a blueprint: a few methods, each with a promised cost, usually constant time. The slow version keeps only a list, so get has to scan everything. The fix: snap on a helper part. Store a little extra next to the data, like a second value, a map from key to node, or a link, and get becomes one step.

The clue: the problem says design or implement the class, and each function must run in O of one, often on average.

Every call stays constant time; you pay for it with linear extra memory, one entry per item.

Now let's use it on Min Stack.