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
Sun | Mon | Tue | Wed | Thu | Fri | Sat |
---|---|---|---|---|---|---|
27 | 28 | 29 | 30 | 1 | 2 | 3 |
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |