awelgorithms

Empty list is empty stack

Updated

head == null iff the stack is empty. isEmpty does not look at a dummy value. After popping the last node, set head to null (delete-head already does).

What to focus on

A dummy head would mean the stack is empty when dummy.next is null, then peek is dummy.next.value. Prefer no dummy for a stack. It adds a branch you do not need.

Worked examples

null

a = []
  1. head null

Result: empty

after last pop

a = [7], pop
  1. head ← null

Result: empty

nonempty

a = [4, 1, 9]
  1. head non-null

Result: not empty

Try it

Write isEmpty(head). head is the top node, or null if the stack is empty. node.next is the next node toward the bottom. isEmpty is head==null. Do not peek a dummy value. Pop [7] and show empty. [4, 1, 9] is not empty.

Head is the top. Values are integers. Empty is in scope. That is this skill.