figure an ordered linked list the ordered list abstract data type we will now consider type of list known as an ordered list for exampleif the list of integers shown above were an ordered list (ascending order)then it could be written as and since is the smallest itemit occupies the first position in the list likewisesince is the largestit occupies the last position the structure of an ordered list is collection of items where each item holds relative position that is based upon some underlying characteristic of the item the ordering is typically either ascending or descending and we assume that list items have meaningful comparison operation that is already defined many of the ordered list operations are the same as those of the unordered list orderedlist(creates new ordered list that is empty it needs no parameters and returns an empty list add(itemadds new item to the list making sure that the order is preserved it needs the item and returns nothing assume the item is not already in the list remove(itemremoves the item from the list it needs the item and modifies the list assume the item is present in the list search(itemsearches for the item in the list it needs the item and returns boolean value is_empty(tests to see whether the list is empty it needs no parameters and returns boolean value size(returns the number of items in the list it needs no parameters and returns an integer index(itemreturns the position of item in the list it needs the item and returns the index assume the item is in the list pop(removes and returns the last item in the list it needs nothing and returns an item assume the list has at least one item pop(posremoves and returns the item at position pos it needs the position and returns the item assume the item is in the list implementing an ordered list in order to implement the ordered listwe must remember that the relative positions of the items are based on some underlying characteristic the ordered list of integers given above ( and can be represented by linked structure as shown in figure againthe node and link structure is ideal for representing the relative positioning of the items basic data structures