Create a C# console application for sorted linked lists. This project should have two classes: a generic SortedLinkedList class that implements the sorted linked list, and a TestSortedLinkedList class that uses integers and characters to test the SortedLinkedList class.

A sorted linked list is a linked list in which all items are always sorted in ascending order, i.e., every node in the linked list is smaller than or equal to the node right after it. For example, the following integer list is sorted: 2, 7, 15, 18, 23, 26. The following integer list is not sorted: 5, 2, 7, 1, 16, 21. Similar, the following character list is sorted: A, K, T, X, Z. The following character list is not sorted: M, B, X, R, T, A.

The SortedLinkedList class is a generic class. Since we need to compare and sort items in the list, you need to add IComparable interface as its type constraint. That means the values stored in the list must be something that can be compared to determined order, such as int, double or char, etc.

This class must have at least three methods:

(1) A parameter-less constructor that creates an empty linked list

(2) A void method PrintList that displays the nodes in the list

(3) A void method Insert (T newItem) that inserts a new node (with newItem as its value) to the list. Since this list is always sorted in ascending order, you need to write code to insert the new node at the appropriate position in the list. If a node in the list already carries the same value we are trying to insert, you can insert the new node either right before or right after the existing node.

You can design your own algorithm or use the following one to determine where in the linked list to insert newItem:

(1) If the list is empty, insert newItem at the front of the list

(2) If the list has only one node, compare newItem with the node in the list. If newItem is smaller than the value stored at that node, insert newItem right before the item. Otherwise, insert newItem right after the item.

(3) If the list has two or more items, do the following:

If newItem is greater than or equal to the last node in the list, insert newItem at the back of list. Otherwise, write a loop to compare newItem with nodes in the list one by one until a node larger than newItem is found. Then insert newItem right before that larger node.

You can use the built-in ComapreTo method of newItem (of Type T) to compare its value with the value of a node. For example:

newItem.CompareTo(node.Value)

returns a negative number if newItem is smaller than node.Value, 0 if they have the same value, or a positive number if newItem is larger than node.Value.

The TestSortedLinkedList class has been written already. You must use this class to test your SortedLinkedList class. You are not allowed to modify the code of this TestSortedLinkedList class.

class TestSortedLinkedList

{

static void Main(string[] args)

{

SortedLinkedList si = new SortedLinkedList();

si.Insert(8);

si.PrintList();

si.Insert(5);

si.PrintList();

si.Insert(20);

si.PrintList();

si.Insert(1);

si.PrintList();

si.Insert(17);

si.PrintList();

Console.WriteLine();

SortedLinkedList sc = new SortedLinkedList();

sc.Insert('K');

sc.PrintList();

sc.Insert('T');

sc.PrintList();

sc.Insert('Z');

sc.PrintList();

sc.Insert('M');

sc.PrintList();

sc.Insert('A');

sc.PrintList();

}

}

The following is the expected output in the console window.

Linked list: 8

Linked list: 5 8

Linked list: 5 8 20

Linked list: 1 5 8 20

Linked list: 1 5 8 17 20

Linked list: K

Linked list: K T

Linked list: K T Z

Linked list: K M T Z

Linked list: A K M T Z

Press any key to continue . . .

Hints: You can use a LinkedList object in your SortedLinkedList class to store the list nodes. That will save you a lot of coding time.