Practice: Identify Data Structures in Real Systems

Theoretical knowledge becomes valuable only when you can recognize how production software architectures employ data structures to solve performance bottlenecks.

In this practical exercise, we analyze five ubiquitous real-world software components and dissect the underlying data structures powering them.

Scenario 1: Web Browser Navigation (Back / Forward Buttons)

The Problem

When browsing web pages, clicking the Back button returns you to the most recently visited page. Clicking Forward moves you forward through previously undone pages. Navigating to a brand-new URL clears the forward history.

The Underlying Data Structure: Two Stacks

Browser navigation is implemented using two independent Stacks:

• Back Stack: Holds previously visited URLs.
• Forward Stack: Holds URLs undone via the Back button.

Copy codeUser actions: Visit A -> Visit B -> Visit C
Back Stack:    [A, B, C] (Top = C)
Forward Stack: []

Action: Click "Back"
Pop C from Back Stack, push C to Forward Stack
Current page: B
Back Stack:    [A, B] (Top = B)
Forward Stack: [C]

Action: Visit D
Push D to Back Stack, clear Forward Stack!
Back Stack:    [A, B, D] (Top = D)
Forward Stack: []

Scenario 2: Android Main Thread / MessageQueue

The Problem

Android applications run on a single main UI thread. User taps, animations, network responses, and lifecycle callbacks arrive asynchronously from various background threads. The main thread must process them sequentially without race conditions.

The Underlying Data Structure: Priority Blocking Queue / Linked List

Android's MessageQueue is physically implemented as a singly-linked list of Message objects sorted by execution timestamp (when):

Copy code// Simplified illustration of Android Message
class Message(
    val what: Int,
    val targetHandler: Any,
    var `when`: Long, // Execution timestamp
    var next: Message? = null
)

When you call handler.postDelayed(runnable, 5000), the message is inserted into the sorted queue in O(n) time based on its target timestamp. The Looper dequeues messages from the head in O(1) time when their dispatch time arrives.

Scenario 3: LRU (Least Recently Used) Image Cache

The Problem

An image loading library (like Coil or Glide) stores downloaded bitmaps in limited phone RAM (e.g., 64MB). When the cache is full, the image that hasn't been accessed for the longest time must be evicted. Lookups, additions, and evictions must all happen in O(1) time.

The Underlying Data Structure: Hash Table + Doubly Linked List

Neither a Hash Table nor a Linked List can solve this alone:

• Hash Table: O(1) lookup, but no ordering.
• Linked List: O(1) removal and reordering, but O(n) lookup.

The Solution: Combine them into a LinkedHashMap!

Copy code   Hash Table (keys to node pointers)
  +----------+---------+
  | "url_1"  | Node A  |
  | "url_2"  | Node B  |
  +----------+---------+
         |         |
         v         v
Head <-> [Node A] <-> [Node B] <-> Tail
(Least Recent)               (Most Recent)

Whenever an image is requested, its node is moved to the tail in O(1). When capacity is exceeded, the node at the head is evicted in O(1).

Scenario 4: Auto-Complete & Search Suggestions

The Problem

As a user types characters into an e-commerce search bar (e.g., "kotl"), the app must suggest matching words ("kotlin", "kotlin coroutines", "kotlin flow") within milliseconds.

The Underlying Data Structure: Trie (Prefix Tree)

A Trie is a specialized tree where each node represents an alphabet character. Looking up prefix matches takes O(k) time, where k is the length of the query string — completely independent of the total number of words in the dictionary (N).

Scenario 5: Social Network Friend Recommendations

The Problem

Finding mutual friends between two users or calculating the "degrees of separation" between members on LinkedIn.

The Underlying Data Structure: Undirected Graph

• Vertices (Nodes): Individual user accounts.
• Edges: Friendships / connections.
• Algorithm: Breadth-First Search (BFS) to identify shortest paths and 2nd-degree connections.

Hands-On Exercise

Identify the most appropriate data structure for each of the following scenarios:

1. Undo / Redo feature in a text editor:
   • Answer: Two Stacks (Undo stack and Redo stack).
2. Music playlist with 'repeat current track' and 'shuffle':
   • Answer: Circular Doubly Linked List for sequential traversal and repeat, or Array with Fisher-Yates shuffle.
3. GPS Routing system finding the fastest route between two cities:
   • Answer: Weighted Directed Graph solved via Dijkstra's / A* algorithm with a Min-Heap (Priority Queue).