Абстрактный тип данных “упорядоченный списоꔶ

А теперь рассмотрим такой подвид списков, как упорядоченный список. Например, если бы список целых, показанный выше, был упорядоченным (по возрастанию), то он записался как 17, 26, 31, 54, 77 и 93. 17 - наименьший элемент, поэтому он ставится на первую позицию, а 93 - наибольший, так что он занимает последнее место.

По структуре упорядоченный список представляет собой коллекцию элементов, каждый из которых занимает положение в зависимости от некой общей для всех характеристики. Порядок упорядочения обычно или возрастающий, или убывающий, и мы полагаем, что для элементов списка существует и определена операция сравнения. Многие из операций для упорядоченного списка аналогичны методам неупорядоченного.

• OrderedList() создаёт новый упорядоченный список. Не требует параметров, возвращает пустой список.
• add(item) добавляет в список новый элемент, предварительно убедившись, что порядок сохраняется. Требует элемент в качестве аргумента, ничего не возвращает. Предполагается, что элемент ранее в списке отсутствовал.
• remove(item) удаляет элемент из списка. Требует элемент и изменяет список. Предполагается, что элемент присутствует в списке.
• search(item) ищет элемент в списке. Требует элемент и возвращает булево значение.
• isEmpty() проверяет список на пустоту. Не требует параметров и возвращает булево значение.
• size() возвращает количество элементов в списке. Не требует параметров и возвращает целое число.
• index(item) возвращает позицию элемента в списке. Требует элемент и возвращает индекс. Предполагается, что элемент в списке присутствует.
• pop() выталкивает последний элемент списка. Не требует параметров и возвращает элемент. Предполагается, что список содержит как минимум один элемент.
• pop(pos) выталкивает элемент с позиции pos. Требует индекс в качестве аргумента, возвращает элемент. Предполагается наличие элемента в списке.