2 Виды списков

• Однонаправленный связный список – ключевой особенностью данного вида списков является то, что ссылка в каждом узле указывает только на следующий узел в списке. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

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

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

• Кольцевой связный список – этот тип списков является разновидностью односвязных либо двусвязных списков. Последний элемент кольцевого списка содержит указатель на первый, а первый (в случае двусвязного списка) — на последний.

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

• Развёрнутый связный список - список, каждый физический элемент которого содержит несколько логических (обычно в виде массива, что позволяет ускорить доступ к отдельным элементам). Позволяет значительно уменьшить расход памяти и увеличить производительность по сравнению с обычным списком.

В практическом приложении к данной работе использовался однонаправленный связный тип списков.

3 Работа со списком

3.1 Описание практической задачи

Цель практической части заключается в создании англо-русского словаря на основе однонаправленного списка.

Программа должна иметь возможность выполнять следующие действия:

• считывать данные из файла, восстанавливая таким образом сам словарь;

• записывать данные из информационного поля списка в файл для хранения;

• добавлять новые слова;

• редактировать существующие записи;

• выводить существующие записи по запросу, как все, так и отдельную запись;

• удалять слова и полностью очищать список;

• выводить информацию о длине словаря.

Все заявленные функции реализованы в виде процедур, для удобства восприятия и использования.

В частности:

• AddNew() добавить новое слово;

• DeleteWord() удалить слово;

• RedWord() редактировать запись;

• ShowWord() вывести перевод слова;

• ShowAll() вывести все записи;

• DeleteAll() удалить все записи;

• SizeList() узнать количество слов в списке;

• OutputVocab() занести данные из списка в файл;

• ReadVocab() считать данные из файла в список.

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