Description

In this linked list: 

• The datatype for the value being stored is called value_t 

• The datatype for the key being stored is called key_t 

• As in lab 4, next links to the node in the order it was added to the list (either at the head or the tail) 

o This will be referred to as insertion order 

• Similar to lab 4, sort links to the node where the key is greater or equal to its key 

o i.e. the list is kept in ascending order by key 

o This will be referred to as key sort order 

o Note: unlike lab 4, there is only one key

Create a Sorted List abstract data type 

• Has two heads (head for insertion order, head_sort for key sort order) 

• Has two tails (tail for insertion order, tail_sort for key sort order) 

• Has an int field called size that stored the node count (the number of elements in the list) 

• The datatype should be called Sorted_List 

Note: technically you will be implementing only be a subset of the Sorted List ADT as you will not be asked to implement all functions of the full ADT