Trace with capacity = 2.
put(1, 1): Cache empty. Insert node 1:1 at head. List: [1]. Map: {1: node1}.
put(2, 2): Insert node 2:2 at head. List: [2, 1]. Map: {1: node1, 2: node2}.
get(1): Found in map. Move node 1 to head. List: [1, 2]. Return .
put(3, 3): At capacity. Evict tail (node 2). Remove key from map. Insert 3:3 at head. List: [3, 1]. Map: {1: node1, 3: node3}.
get(2): Not in map. Return .
Every operation is time. space where is the capacity.