Join Community
Home Events Academy Speakers Organizers Stories Gallery Blog FAQs Join Community
← All courses

Lists, Stacks & Queues

🗓 May 31, 2026 • ⏱ 3 min read

Linked lists

A linked list stores each item in a node that points to the next one. Unlike an array, items aren’t contiguous in memory. The trade-off: inserting/removing is O(1) if you have the node (no shifting), but access by position is O(n) (you must walk the chain).

A B C null

In app development you rarely write a linked list by hand, but the concept matters — the LRU cache (a later lesson) combines a hash map with a linked list, and understanding nodes/pointers helps you reason about memory and the structures libraries use.

Stack: Last-In, First-Out (LIFO)

A stack is like a pile of plates — you add (push) and remove (pop) from the top. Both are O(1).

val stack = ArrayDeque<String>()
stack.addLast("Home")      // push
stack.addLast("Profile")
val top = stack.removeLast()   // pop -> "Profile"

Mobile uses:

  • Navigation back stack — pushing a screen and pressing Back is literally push/pop on a stack.
  • Undo/redo — each action pushed; undo pops the last.
  • Depth-first traversal of trees (like the view hierarchy).

Queue: First-In, First-Out (FIFO)

A queue is like a line at a counter — first in, first served. You enqueue at the back and dequeue from the front, both O(1).

val queue = ArrayDeque<Task>()
queue.addLast(task)             // enqueue
val next = queue.removeFirst()  // dequeue

Mobile uses:

  • Network/work queues — process requests or uploads in order.
  • Event/message handling — the main thread itself processes a message queue.
  • Breadth-first traversal of trees/graphs (e.g. level-by-level).

Deque & priority queue

  • Deque (double-ended queue) — add/remove at both ends; ArrayDeque serves as both stack and queue.
  • Priority queue — always removes the highest-priority item first (e.g. process the most important download next).

Choosing the right one

  • Need LIFO (most recent first, undo, back) → stack.
  • Need FIFO (fair, in-order processing) → queue.
  • Need fast inserts/removes by node, not index → linked list.

Common mistakes

  • Using a plain list and removing from the front repeatedly (O(n) each time) instead of a deque.
  • Confusing stack (LIFO) with queue (FIFO) for the task at hand.
  • Hand-rolling these when the standard library (ArrayDeque) already provides them.
Summary: Linked lists give O(1) node inserts but O(n) access. Stacks (LIFO) power navigation back stacks and undo; queues (FIFO) power work/event processing. Use ArrayDeque for both, and pick LIFO vs FIFO based on the order you need.