Skip to content

Latest commit

 

History

History
126 lines (97 loc) · 10.9 KB

chapter12.adoc

File metadata and controls

126 lines (97 loc) · 10.9 KB

12. Разработка классов-контейнеров

В этом разделе мы поговорим о проектировании классов другого вида, а именно классов-контейнеров. Так мы называем классы, содержащие внутри себя наборы однотипных данных. Список, множество, таблица, телефонная или адресная книга, матрица — всё это примеры классов-контейнеров.

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

Для упрощения задачи будем считать, что наш список SinglyLinkedList умеет хранить исключительно целые числа; в качестве одного из упражнений вы можете попробовать изменить данный класс так, чтобы он мог хранить данные настраиваемого типа (подробнее про настраиваемые типы см. раздел 9). Опишем для начала один узел цепи в виде вложенного класса.

class SinglyLinkedList {
    // ...
    private class Node(
        val value: Int,
        var next: Node? // next == null означает, что данный узел -- последний в списке
    )
    // ...
}

Узел хранит в себе значение value и ссылку на следующий узел next.

Напомним, что создание класса не приводит само по себе к созданию каких-либо данных или переменных. Выше мы уже говорили, что ссылку на первый узел в списке необходимо сохранить отдельно; используем для этого свойство start.

class SinglyLinkedList {
    private var start: Node? = null
    private class Node(...) //
    // ...
}

Данные нашего класса исчерпываются свойством start, узлом, ссылка на который хранится в данном свойстве, а также всеми последующими узлами, ссылки на которые хранятся в предыдущих узлах.

Начиная с раздела 4 мы уже знакомы с понятием "список" и типичными методами для работы с ним. Давайте посмотрим на реализацию некоторых из этих методов для связного списка.

Добавление элемента

Элемент проще добавить в начало однонаправленного связного списка, чем в его конец. Для этого необходимо:

  • создать новый узел, вызвав его конструктор;

  • указать, что следующим для созданного узла будет БЫВШИЙ первый узел списка, или же null, если список был пустым;

  • указать, что созданный узел теперь будет первым в списке, записав ссылку на него в свойство start.

Как ни странно, все эти действия можно сделать в одну строчку:

class SinglyLinkedList {
    // ...
    // newValue = значение, сохраняемое в новом узле
    fun add(newValue: Int) {
        start = Node(newValue, start)
    }
    // ...
}

Удаление элемента

Удаление первого элемента, опять-таки, делается очень легко: start = start?.next. Действительно, мы должны пойти в первый узел списка, вытащить из него ссылку на следующий (второй) узел и записать эту ссылку в свойство start. После этого образуется ситуация, когда ссылка на бывший первый узел не хранится нигде, и вскоре этот первый узел будет удалён сборщиком мусора.

Ниже приведён пример функции, удаляющей последний элемент в связном списке.

class SinglyLinkedList {
    // ...
    // Удаление последнего узла, возвращает false, если список пуст
    fun removeLast(): Boolean {
        val start = start ?: return false
        if (start.next == null) {
            this.start = null
        } else {
            var current = start
            while (current.next?.next != null) {
                current = current.next!!
            }
            current.next = null
        }
        return true
    }
    // ...
}

Функция работает по следующей схеме:

  • если список пуст start == null, мы возвращаем false и ничего более не делаем (нет последнего узла);

  • если список содержит единственный элемент, start.next == null, мы обнуляем start и ничего более не делаем (список становится пустым);

  • в противном случе мы с помощью цикла while ищем предпоследний узел списка и обнуляем его ссылку на следующий (последний) узел.

Сравнение на равенство

Если вы реализуете подобную функцию для контейнера, задумайтесь вначале, когда контейнеры данного типа могут считаться равными. Для списков традиционнно считается, что они равны, если содержат одинаковое число элементов (равны размеры) И соответствующие элементы списков равны друг другу (первый равен первому, второй второму и так далее). Поэтому нам необходимо в цикле параллельно пройти по элементам двух списков и сравнить их на равенство.

class SinglyLinkedList {
    // ...
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other !is SinglyLinkedList) return false
        var ourCurrent = start
        var otherCurrent = other.start
        while (ourCurrent != null) {
            if (otherCurrent == null || ourCurrent.value != otherCurrent.value) return false
            ourCurrent = ourCurrent.next
            otherCurrent = otherCurrent.next
        }
        return otherCurrent == null
    }    // ...
}

Функция equals, как обычно, начинается с проверки на равенство ссылок this и other и с проверки типа other. Далее мы объявляем ссылки ourCurrent и otherCurrent для нашего путешествия по узлам двух списков — this и other соответственно. В цикле мы проверяем, что при существовании ourCurrent существует и соответствующий ему otherCurrent, и что их значения равны. Попробуйте разобраться сами, для чего нужна проверка в конце функции return otherCurrent == null, и что будет, если заменить эту проверку на более простой return true.

Упражнения

Откройте каталог src/lesson12/task1 в проекте. Внутри находится файл с рассмотренным выше примером SinglyLinkedList.kt, а также четыре других файла с различными заданиями на проектирование классов-контейнеров. Задания имеют близкую сложность; самым сложным из них является OpenHashSet.kt, и это единственное из заданий, предполагающее создание настраиваемого (generic) класса. Суть каждого задания описана в заголовочном комментарии класса, плюс дан короткий комментарий к каждой функции класса.

Выберите одно из заданий, которое кажется вам посильным. Замените на реализацию все TODO(), которые есть в классе. После этого откройте тесты для данного класса из каталога test/lesson12/task1. Подумайте над тем, какие из важных случаев рассмотрены тестами, а какие — нет. Дополните тесты нерассмотренными случаями. После этого запустите тесты для вашего класса и добейтесь их полного прохождения.

Поздравляем вас с прохождением всех разделов нашего курса!