data structures, doubly linked lists and sorting please!

1. Introduction In this assignment, you will implement sorting methods that you have learned in class on a doubly linked list. 2. Input files This file will contain two lines. The first one gives you the numbers that you have to store in your doubly linked list and the second one will have the sorting method. For instance, this is a valid input: 1582493 Selection This is an invalid input: Insertion 2461 Other examples of invalid input include: empty input, no numbers, no sorting specified 3. Output files - The output file should display the whole linked list after each iteration in the format below. - Each iteration ends when a number sits in its right place and the program starts checking the next number (insertion) or position (selection). [1,5,8,2,4,9,3] [1,2,8,5,4,9,3] [1,2,3,5,4,9,8] [1,2,3,4,5,9,8] [1,2,3,4,5,9,8] [1,2,3,4,5,8,9] If the input is invalid, print: "Input is invalid." (no or endl) 4. Operation Please note that you will have to move the whole node by changing the next and prev; changing just the values will result in a \% 100 penalty