Singly Linked List

Practice this coding question on Coding Gurukul.

Problem statement

Implement a singly linked list using nodes and next pointers. Start with an empty list. - FRONT x: insert x at the beginning. - BACK x: insert x at the end. - DELETE x: remove the first node containing x. Do nothing if x is absent. - PRINT: print all values from head to tail, or EMPTY if the list is empty. Repeated and negative values are allowed. Only PRINT produces output. Worked example BACK 4, FRONT 1 and BACK 4 create [1, 4, 4]. DELETE 4 removes only the first 4, so PRINT gives 1 4. DELETE 1 leaves 4.

Input format

First line: q. Next q lines: FRONT x, BACK x, DELETE x, or PRINT.

Output format

For every PRINT, output the node values separated by spaces, or EMPTY.

Constraints

1 <= q <= 2000; -10^9 <= x <= 10^9. At least one PRINT.

Sample input

7
BACK 4
FRONT 1
BACK 4
DELETE 4
PRINT
DELETE 1
PRINT

Sample output

1 4
4

Sign in to run or submit a solution in C++, Java or Python.