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

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

class Item2 {

public Book data; // данные

public Item2 prev; // ссылка на такой же предыдущий элемент

public Item2 next; // ссылка на такой же следующий элемент

}

Добавьте в этот класс конструктор (какой он должен быть?).

Класс самого списка должен содержать переменные:

· ссылку на первый элемент,

· ссылку на последний элемент,

· количество элементов

и методы:

· конструктор(ы)

· isEmpty() – пустой список или нет

· возвращающий количество элементов

· возвращающий ссылку на элемент по номеру (возвращает null, если элемент не найден)

· добавление элемента по заданному номеру возвращает (true/false)

· удаление элемента по заданному номеру возвращает (true/false)

При написании методов добавления/удаления необходимо помнить, что

· проход по списку: аналогичен проходу по односвязному списку;

· ссылка next последнего элемента должна указывать на первый элемент, а ссылка prev первого элемента на последний, поскольку список циклический (т.е. представляет собой кольцо);

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

Напишите класс двунаправленного связного списка и протестируйте его отдельно от задания 2. После того, как класс будет работать корректно выполните задание 2.

Задание 3.

Проверьте работу классов, создав экземпляр научной библиотеки с различными произвольными значениями количества книг по залам. Добавьте книги в залы, библиотеки; измените книгу; измените зал; удалите книгу; для проверки каждого задания используйте методы распечатки списка залов и книг.

Выведите автора самой лучшей книги; выведите список названий книг по убыванию цены.