"Why do background apps close on their own?"
If you use a smartphone, you've hit this before: you return to an app you opened a while ago, and it restarts from the first screen. Memory was tight, so the OS quietly terminated the app you hadn't used in the longest time.
Suppose you're building that behavior yourself. The rules are simple:
- •Keep only the N most recently used apps in memory.
- •If you launch a new app and there's no room → terminate the least recently used app.
- •When you switch to an app → it becomes the 'just-used app' again.
Example: with N=3, launching
MAP → CAM → MSGgives memory[MSG, CAM, MAP]. Switching to MAP brings it to the front:[MAP, MSG, CAM]. Now launching a new app WEB terminates CAM, which was at the back.
Notice it? This "keep only the N most recent" rule is exactly an LRU (Least Recently Used) cache.
The first solution that comes to mind (and its limit)
The simplest urge is to use a single array (list), lined up in order of use.
each time an app is used: find it in the array, move it to the front
when there's no room: cut off the back of the arrayOrder stays clean. But that one line — "find it in the array" — is the problem. With N apps you may scan up to N slots each time, then shift the trailing elements to move it to the front. Each operation is O(n). With 100,000 calls, it gets slow fast.
So what about a hash map instead? Finding by name is O(1), instant. But it's missing the crucial piece: a hash map doesn't remember order. It can't answer "which alive app is the oldest?" — so it can't pick which app to terminate.
| Approach | Find by name | Know the oldest app |
|---|---|---|
| Array only | O(n) ❌ | O(1) ✓ |
| Hash map only | O(1) ✓ | impossible ❌ |
One has slow search; the other doesn't know order. And we need both.
Why "hash map + doubly linked list"?
Here's the shift in thinking: what if we combine only the strengths of the two structures?
- •A doubly linked list represents usage order. The front (HEAD) is the just-used app, the back (TAIL) is the oldest. Because it's doubly (both-direction) linked, you can detach and reattach any single node in O(1).
- •A hash map stores "app name → that node's location," so you can jump straight to the node in O(1) without scanning the list from the start.
When the two meet, something magical happens:
- •Switch/relaunch an app → find the node via the hash map (O(1)), move it right after HEAD (O(1)).
- •Over memory → remove the node right before TAIL (O(1)) and delete it from the hash map too.
Every operation is O(1). The array's "knows order but slow" weakness and the hash map's "fast but order-blind" weakness cover each other exactly. Space is one slot per app — O(N).
This pattern shows up wherever you need to "keep only the recent ones in limited space": OS page replacement, database/CDN caches, a browser's back history. It's also a coding-test staple.
See it with your own eyes
We built the entire process as a step-by-step visualization: finding an app in the hash map, that node being pulled up to the front of the list, and the moment memory fills up triggering the back app to be terminated and slide out. You'll see the hash map and linked list change together, and the exact moment switchTo hits or misses.
👉 Smartphone App Manager — watch the step-by-step visualization