Optional Assignment – Sorted Linked Lists

Implementing a Sorted Linked Lists

What you will learn

• Implementing a sorted linked list

• Templates

• Running time analysis

Coding exercise

Implement a sorted linked list in a template called sortedLinkedList. Functionalities desired are as follows:

The list should always be sorted, i.e., each element should always be less than its next element and smaller than its previous element. You can use a singly or doubly linked list implementation.

What to turn in

• A zip file containing the sortedLinkedList.h file with your template declaration and implementation, and a main.cpp file with test cases to show that your program works.

• For each function, analyze the running time of your algorithm, i.e., the time complexity of your algorithms in big-O notation. Report it in a file called report.pdf. Include your sources as references in report.pdf.