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

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

class Item {

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

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

}

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

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

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

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

и методы:

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

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

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

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

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

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

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

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

if(isEmpty()) { return; }

Item p = top;

do{

//выполняем действия над текущем эл. списка

//…

p = p.next;

}while(p!=top);

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

· для добавления/удаления элемента, необходимо встать на предшествующий ему элемент (что будет, если список содержит 1 элемент? если список пустой?);

· добавление в начало изменит ссылки на первый элемент и ссылку next последнего элемента.

· в случае ошибки добавления/удаления элемента соответствующий метод должен возвращать false и выводить текстовое сообщение (иначе true).

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