Павел Разбойников
дата публикации 27-12-2009 12:12

---

Версия для печати

Доброго времени суток, жители Королевства!

Когда нам в университете читали лекции по спискам, очередям и деревьям, всё было как-то сложно и непонятно. И в памяти отложилось, что нечто такое существует, а как и зачем этим пользоваться, было ещё не ясно.

Недавно я принялся писать то, что, наверно, каждый программист однажды писал, — это телефонно-адресный справочник. Тут я осознал мощь и плюсы двусвязных списков относительно простых массивов! Но, увы, лекции оказались не достаточно информативными для программирования, а поисковики отказывались мне показывать то, что нужно. Но, благодаря книге Рода Стивенса "Delphi, готовые алгоритмы" я понял, как это можно красиво и понятно реализовать.

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

Ниже достоинства и недостатки списков из Википедии

Достоинства:

1. лёгкость добавления и удаления элементов
2. размер ограничен только объёмом памяти компьютера и разрядностью указателей
3. динамическое добавление и удаление элементов

Недостатки:

1. сложность определения адреса элемента по его индексу (номеру) в списке
2. на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
3. работа со списком медленнее, чем с массивами, так как к любому элементу списка можно обратиться, только пройдя все предшествующие ему элементы
4. элементы списка могут быть расположены в памяти разреженно, что окажет негативный эффект на кэширование процессора
5. над связными списками гораздо труднее (хотя и в принципе возможно) производить параллельные векторные операции, такие как вычисление суммы

К достоинствам необходимо добавить ещё несколько важных вещей.

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

Итак, что у нас имеется.

type PRDListEl = ^TRDListEl; //Элемент (ячейка) списка TRDListEl = record Value: PByte; //Некоторые данные Prev: PRDListEl; //Предыдущий элемент Next: PRDListEl; //Следующий элемент end; //Событие для условия поиска TFilterEvent = function: Boolean; TRazDList = class private FFirst, FLast: PRDListEl; //Первый и последний элементы списка FCount: Cardinal; //Количество элементов FFilter: PRDListEl; //Фильтр для поиска данных FOn_Term: TFilterEvent; //Событие фильтра поиска (* Направление поиска: 0 - не было поиска, 1 - с начала, 2 - с конца. Обнуляется при любых действиях со списком, связанных с изменением количества элементов, т.е. при Inert, Add, Delete, Replace, Change и т.п. *) FSearch: Byte; //Направление поиска FLastFound: PRDListEl; //Последний найденный элемент FElem1, FElem2: PRDListEl; //Элементы, полученные в GetTwoItems FInd1, FInd2: Cardinal; //Индексы, полученные в GetTwoNumbers //Функции для свойств function GetItem(Index: Cardinal): PRDListEl; function GetNumber(Element: PRDListEl): Int64; //Дополнительные процедуры procedure GetTwoItems(Index1, Index2: Cardinal); procedure GetTwoNumbers(Element1, Element2: PRDListEl); public //Количество элементов property Count: Cardinal read FCount default 0; //Первый элемент property First: PRDListEl read FFirst default nil; //Последний элемент property Last: PRDListEl read FLast default nil; //Элемент по номеру property Item[Index: Cardinal]: PRDListEl read GetItem; //Номер элемента property Number[Element: PRDListEl]: Int64 read GetNumber; //Фильтр поиска property Filter: PRDListEl read FFilter default nil; //Событие фильтра поиска property OnTerm: TFilterEvent read FOn_Term write FOn_Term; constructor Create; destructor Destroy; override; //Вставить в позицию (аналогично добавления слева) function Insert(Index: Cardinal): PRDListEl; overload; function Insert(Index: Cardinal; Value: Pointer): PRDListEl; overload; //Добавить в конец function Add: PRDListEl; overload; function Add(Value: Pointer): PRDListEl; overload; //Добавить слева (аналогично Insert) function AddLeft(Index: Cardinal): PRDListEl; overload; function AddLeft(Index: Cardinal; Value: Pointer): PRDListEl; overload; //Добавить справа function AddRight(Index: Cardinal): PRDListEl; overload; function AddRight(Index: Cardinal; Value: Pointer): PRDListEl; overload; //Удалить function Delete(Element: PRDListEl): Boolean; overload; function Delete(Index: Cardinal): Boolean; overload; //Удалить слева function DeleteLeft(Index: Cardinal): Boolean; //Удалить справа function DeleteRight(Index: Cardinal): Boolean; //Заменить один элемент списка другим function Replace(SourEl, DestEl: PRDListEl): PRDListEl; overload; function Replace(SourIndex, DestIndex: Cardinal): Cardinal; overload; //Скопировать данные из одного элемента в другой function Copy(SourEl, DestEl: PRDListEl): Boolean; overload; function Copy(SourIndex, DestIndex: Cardinal): Boolean; overload; //Поменять местами два элемента function Change(El1, El2: PRDListEl): Boolean; overload; function Change(Index1, Index2: Cardinal): Boolean; overload; //Поиск элемента function FindFirst: PRDListEl; //Поиск первого совпадения с начала function FindLast: PRDListEl; //Поиск первого совпадения с конца function FindNext: PRDListEl; //Поиск следующего совпадения //Удалить все procedure Clear; //Пересчитать количество элементов function ReCalc: Cardinal; end;

Поиск реализован следующим образом:

1. Создайте функцию по схеме:
   function <имя вашей функции>: Boolean;
2. Запишите туда условия выполнения поиска, например:
   Result:=(DList.Filter^.Next=nil); //будет найден последний элемент списка,
   где DList — экземпляр класса TRazDList.
3. До вызова поиска назначьте условие поиска на свою функцию, например:
   DList.OnTerm:=<имя вашей функции>;,
   где DList — экземпляр класса TRazDList.

В классе я реализовал самые необходимые, на мой взгляд, поля и методы, которые могут пригодиться. Думаю, объяснять здесь нечего. Всё предельно просто. Без проблем сможет разобраться даже начинающий. К тому же в исходниках много комментариев.

Из приведённого мною кода легко сделать односвязный список, циклические списки или даже дерево. Если у вас будет желание увидеть реализацию дерева, то с удовольствием поделюсь с вами.

Исходный код модуля здесь.