1. Write an algorithm to insert a new node in (ascending) lexicographic order in a doubly linked list. Be sure you explicitly cover all four cases. Clearly indicate where you cover each of the 4 cases in your algorithm with an appropriate comment. A head node is utilized as described in class for the empty list containing the name of a flight. The nodes in the list provide information on passengers.

1) Choice (do only one of the following): A) Write an algorithm to insert a new node in (ascending) lexicographic order in a doubly linked list. Be sure you explicitly cover all four cases. Clearly indicate where you cover each of the 4 cases in your algorithm with an appropriate comment. A head node is utilized as described in class for the empty list containing the name of a flight. The nodes in the list provide information on passengers. Empty List at address A: Pt Fit105 Texas | A | A A Sample list prior to the insertion of Sara. Pt C Fit105 Texas B A Bob C B Tom A 7 After insertion of Sara: Pt C Flt105 Texas B Pt2 Tom Bob A _ B | Sara