Интернет-журнал "Домашняя лаборатория", 2007 №9

Являясь клиентом универсального класса Node, наш класс сохраняет родовые параметры клиента и ограничения, накладываемые на них. Два поля класса — first и cursor — задают указатели на первый и текущий элементы списка. Операции над списком связываются с курсором, позволяя перемещать курсор по списку. Рассмотрим вначале набор операций, перемещающих курсор:

public void start ()

{ cursor = first; } public void finish ()

{

    while (cursor.next!= null)

        cursor = cursor.next;

}

public void forth()

{ if (cursor.next!= null) cursor = cursor.next; }

Операция start передвигает курсор к началу списка, finish — к концу, a forth — к следующему элементу справа от курсора. Операции finish и forth определены только для непустых списков. Конец списка является барьером, и курсор не переходит через барьер. Нарушая принципы ради краткости текста, я не привожу формальных спецификаций методов, записанных в тегах

.

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

public void add(К key, Т item)

{

    Node newnode = new Node();

    if (first == null)

    {

       first = newnode; cursor = newnode;

       newnode.key = key; newnode.item = item;

    }

    else

    {

       newnode.next = cursor.next; cursor.next = newnode;

       newnode.key = key; newnode.item = item;

    }

}

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

Рассмотрим теперь операцию поиска элемента по ключу, реализация которой потребовала ограничения универсальности типа ключа к;

public bool findstart(К key)

{

    Node temp = first;

    while (temp!= null)

    {

        if (temp.key.CompareTo(key) == 0) {cursor=temp;

           return(true);}

        temp= temp.next;

    }

    return (false);

}

Искомые элементы разыскиваются во всем списке. Если элемент найден, то курсор устанавливается на найденном элементе и метод возвращает значение true. Если элемента с заданным ключом нет в списке, то позиция курсора не меняется, а метод возвращает значение false, в процессе поиска для каждого очередного элемента списка вызывается допускаемый ограничением метод CompareTo интерфейса IComparable. При отсутствии ограничений универсальности вызов этого метода или операции эквивалентности приводил бы к ошибке, обнаруживаемой на этапе компиляции.

Два метода класса являются запросами, позволяющими извлечь ключ и элемент списка, который отмечен курсором:

public К Key ()

{

    return (cursor.key);

}

public T Item()

{

    return(cursor.item);

}

Давайте рассмотрим теперь тестирующую процедуру — клиента нашего списка, демонстрирующую работу со списками, в которых элементы и ключи имеют разные типы: