Baseline Linked List · Single Linked List O(N) · O(1)
A print spooler processes a stream of jobs, and every job arrives with a priority flag: flag 1 joins the back of the queue, flag 0 cuts straight to the front. The spool is a linked list, so front insertion rewires one pointer while back insertion must walk to the tail first. After the whole stream is processed, the spool order is reported.
Input: A sequence of pairs (value, indicator) where indicator 1 appends value to the end of the list and indicator 0 prepends it to the front; the list starts empty.
Output: The contents of the linked list after every operation, read front to back.
1 <= number of pairs <= 10^5-10^9 <= value <= 10^9indicator is 0 or 1Input: {"pairs":[[9,0],[5,1],[6,1],[2,0],[5,0]]}
Output: [5,2,9,5,6]
Each flag-0 job jumps the queue, so the two front insertions end up in reverse arrival order ahead of the appended jobs.
Input: {"pairs":[[5,1],[6,1],[9,1]]}
Output: [5,6,9]
All flags are 1, so arrival order and final order coincide.