Очереди и стеки обладают двумя общими свойствами. Во-первых, доступ к находящимся в них данных подчиняется строгим правилам. Во-вторых, операции поиска имеют разрушительный характер. Если выбранный из стека или очереди элемент не будет где-нибудь сохра- нен, то он будет потерян. Кроме того, стеки и очереди для своей работы требуют наличия непрерывной области памяти /непрерывность должна обеспечиваться по крайней мере логически/.
В отличии от стека и очереди связанный список позволяет осу- ществлять доступ к любым элементам, поскольку каждая единица ин- формации имеет указатель на следующий элемент данных в цепочке. Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди могут работать и с простыми и со слож- ными структурами данных. Операция поиска в связанном списке не приводит к удалению и уничтожению элемента. В данном случае сле- дует предусмотреть дополнительно операцию удаления элемента из списка.
Связанные списки используются в двух основных случаях. Во -первых, при создании массивов, которые располагаются в оператив- ной памяти и размер которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей зада- чи, то вы можете использовать простой массив. Однако, если дейс- твительный размер списка вам неизвестен, то вы должны применить связанный список. Во-вторых, связанные списки используются в ба- зах данных на дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего диско- вого файла. По этим причинам связанные списки широко используются в программах по управлению базами данных.
Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависи- мости от решаемой задачи.
Связанные списки с одиночной связью ----------------------------------------------------------------- В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис. 8. Рис.8. Расположение списка с одиночной связью в памяти: 1 - информация; 2 - указатель связи; 3 - нуль. Имеется два способа построения списка с одиночной связью. В первом случае каждый новый элемент добавляется в начало или в ко- нец списка. Во втором случае каждый элемент добавляется в свое место в списке /например, так, чтобы обеспечить упорядочность по возрастанию/. Способ построения списка определяется процедурой постановки нового элемента в список. Ниже дается такая процедура для просто- го случая, когда элементы добавляются в конец списка. Необходимо определить запись, которая будет содержать информацию и указатели связи. В этом примере запись содержит адрес почтовой корреспон- денции. Тип записи для каждого элемента в списке адресов опреде- ляется ниже: AddrPointer = ^address; address = record name: string[30]; street: string[40]; city: string[20]; state: string[2]; zip: string[9]; next: AddrPointer; { указатель на следующую запись } end; DataItem = address; var start.last: AddrPointer; Ниже представлена функция добавления в список с одной связью, когда каждый новый элемент помещается в конец списка. Указатель записи типа "address" должен передаваться в качестве аргумента функции: { добавление в список с одной связью } procedure SL_Store(i: AddrPointer); Legin if last=nil then { первый элемент списка } 2 begin last := i; start := i; i^.next := nil; end else begin last^.next := i; i^.next := nil; last := i; Энциклопедия по Турбо-Паскалю ч.1 = 49 = end; end; { конец процедуры добавления элементов в список с одной связью } Следует помнить, что до первого обращения к этой функции пе- ременные "start" и "last" должны быть установлены на значение "nil". Можно предусмотреть отдельную операцию по сортировке списка, созданного с помощью указанной функции добавления элементов в список с одной связью. Однако упорядочения легче добиться во вре- мя вставки путем установки каждого нового элемента в соответству- ющее место списка. Кроме того, если список уже является отсорти- рованным, то имеет смысл сохранить его упорядоченность, вставляя каждый новый элемент в соответствующее место списка. Для этого делается последовательный просмотр списка до тех пор, пока не бу- дет найдено нужное место. В это место вставляется новый адрес и делается соответствующее изменение связей. При вставке элемента в список с одной связью может воникнуть одна из трех ситуаций. Во-первых, новый элемент может оказаться первым в списке. Во-вторых, он может встать между другими двумя элементами и в-третьих, он может оказаться последним элементом в списке. На рис.9 показано, как для каждого из этих случаев изме- няются связи. Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избе- жать этого, в качестве первого элемента нужно использовать фик- тивный элемент. Этот фиктивный элемент должен иметь такое значе- ние, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостат- ком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется. Энциклопедия по Турбо-Паскалю ч.1 = 50 = 1 Новый первый элемент +-----+ +-----+ ¦2 new¦ ¦2 new¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ +-----+ +-----+ 4becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 6 New Middle Item +-----+ +-----+ ¦2 new¦ ¦2 new¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ +-----+ +-----+ 4becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 7 New Last Item +-----+ +-----+ ¦2 new¦ ¦2 new¦ +-----¦ +-----¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ 4becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦ ¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ Рис.9. Вставка элемента в список с одной связью: 1 - новый первый элемент; 2 - новый элемент; 3 - информационные поля; 4 - справа дается преобразованный список; 5 - нулевой указатель связи; 6 - новый средний элемент; Энциклопедия по Турбо-Паскалю ч.1 = 51 = 7 - новый последний элемент. Приводимая ниже функция используется для вставки адресов почтовых корреспонденций в порядке возрастания фамилий /поле "name"/. В качестве результата функции выдается первый элемент списка. Входными аргументами этой функции являются указатели на начало и конец списка. { добавление элементов в список с одной связью с сохранением упорядоченности } function SLS_Store(info, start: AddrPointer; var last: AddrPointer): AddrPointer; var old, top: AddrPointer; done: boolean; begin top := start; old := nil; done := FALSE; if start=nil then begin { первый элемент списка } info^.next:=nil; last:=info; SLS_Store:=info; end else begin while (start<>nil) and (not done) do begin if start^.name < info^.name then begin old:=start; start:=start^.next; end else begin { вставка в середину } if old<>nil then begin old^.next:=info; info^.next:=start; SLS_Store:=top; { сохранить начало } done:=TRUE; end else begin info^.next:=start; { новый первый элемент } SLS_Store:=info; done:=TRUE; end; Энциклопедия по Турбо-Паскалю ч.1 = 52 = end; end; {while} if not done then begin last^.next:=info; { вставка в конец } info^.next:=nil; last:=info; SLS_Store:=top; end; end; end; { конец процедуры упорядоченной вставки в список с одной связью} Для связанного списка обычно не предусматривается отдельная функция, связанная с процессом поиска, при котором элементы выда- ются в порядке их расположения в списке. Эта функция обычно прог- раммируется очень просто и оформляется вместе с другими функция- ми, например, поиском отдельного элемента, его удалением или выводом на экран. В качестве примера ниже приводится процедура вывода всех фамилий в списке адресов почтовых корреспонденций: procedure Display(start: AddrPointer); begin while start<>nil do begin WriteLn(start^.name); start:=start^.next; end; end; { конец процедуры вывода} Здесь переменная "start" является указателем на первую за- пись в списке. Поиск элемента в списке представляет собой простую процедуру прохода по цепочке. Процедуру поиска адресов по фамилиям можно составить следующим образом: function Search(start:AddrPointer;name:str80):AddrPointer; var done:boolean; begin done := FALSE; while (start<>nil) and (not done) do begin if name=start^.name then begin Search:=start; done:=TRUE; end else start:=start^.next; Энциклопедия по Турбо-Паскалю ч.1 = 53 = end; if start=nil then Search := nil; { нет в списке } end; { конец процедуры поиска элемента } Поскольку эта процедура поиска в результате выдает указатель на тот элемент списка, который соответствует искомой фамилии, пе- ременная "Search" должна объявляться как указатель записи типа "address". Если требуемый элемент отсутствует в списке, то в ре- зультате выдается нулевой указатель. Процедура удаления элемента из списка с одной связью прог- раммируется просто. Как при вставке элемента здесь может встре- титься один из трех случаев: удаляется первый элемент, удаляется средний элемент и удаляется последний элемент. На рис.10 иллюст- рируется каждая ситуация. 1 Deleting the First Item 2becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 6 Deleting a Middle Item 2becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦ ¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5nil ¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 7 Deleting the Last Item 2becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦ ¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦5 nil¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ Рис.10. Удаление элемента из списка с одной связью: 1 - удаление первого элемента; 2 - левый список преобразуется в правый; 3 - информационные поля; 4 - удаленный элемент; 5 - связь с нулевым значением; 6 - удаление среднего элемента; 7 - удаление последнего элемента. Приводимая ниже функция выполняет удаление заданного элемен- та из списка записей адресов: Энциклопедия по Турбо-Паскалю ч.1 = 54 = function SL_Delete(start, item, prior_item: AddrPointer) :AddrPointer; begin if prior_item<>nil then prior_item^.next:=item^.next else start:= item^.next; SL_Delete:=start; end; { конец функции удаления элемента из списка с одной связью } СВЯЗАННЫЕ СПИСКИ ----------------------------------------------------------------- Очереди и стеки обладают двумя общими свойствами. Во-первых, доступ к находящимся в них данных подчиняется строгим правилам. Во-вторых, операции поиска имеют разрушительный характер. Если выбранный из стека или очереди элемент не будет где-нибудь сохра- нен, то он будет потерян. Кроме того, стеки и очереди для своей работы требуют наличия непрерывной области памяти /непрерывность должна обеспечиваться по крайней мере логически/. В отличии от стека и очереди связанный список позволяет осу- ществлять доступ к любым элементам, поскольку каждая единица ин- формации имеет указатель на следующий элемент данных в цепочке. Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди могут работать и с простыми и со слож- ными структурами данных. Операция поиска в связанном списке не приводит к удалению и уничтожению элемента. В данном случае сле- дует предусмотреть дополнительно операцию удаления элемента из списка. Связанные списки используются в двух основных случаях. Во -первых, при создании массивов, которые располагаются в оператив- ной памяти и размер которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей зада- чи, то вы можете использовать простой массив. Однако, если дейс- твительный размер списка вам неизвестен, то вы должны применить связанный список. Во-вторых, связанные списки используются в ба- зах данных на дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего диско- вого файла. По этим причинам связанные списки широко используются в программах по управлению базами данных. Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависи- мости от решаемой задачи. Связанные списки с одиночной связью ----------------------------------------------------------------- В списке с одиночной связью каждый элемент данных имеет связь с последующим элементом в списке. Каждый элемент данных обычно представляет собой запись, которая содержит информационные поля и указатель связи. Список с одиночной связью показан на рис. 8. Энциклопедия по Турбо-Паскалю ч.1 = 48 = +-----+ +-----+ +-----+ ¦1info¦ ¦1info¦ ¦1info¦ +-----¦ +-----¦ +-----¦ ¦2link¦ ¦2link¦ ¦3 nil¦ +-----+ +-----+ +-----+ Рис.8. Расположение списка с одиночной связью в памяти: 1 - информация; 2 - указатель связи; 3 - нуль. Имеется два способа построения списка с одиночной связью. В первом случае каждый новый элемент добавляется в начало или в ко- нец списка. Во втором случае каждый элемент добавляется в свое место в списке /например, так, чтобы обеспечить упорядочность по возрастанию/. Способ построения списка определяется процедурой постановки нового элемента в список. Ниже дается такая процедура для просто- го случая, когда элементы добавляются в конец списка. Необходимо определить запись, которая будет содержать информацию и указатели связи. В этом примере запись содержит адрес почтовой корреспон- денции. Тип записи для каждого элемента в списке адресов опреде- ляется ниже: AddrPointer = ^address; address = record name: string[30]; street: string[40]; city: string[20]; state: string[2]; zip: string[9]; next: AddrPointer; { указатель на следующую запись } end; DataItem = address; var start.last: AddrPointer; Ниже представлена функция добавления в список с одной связью, когда каждый новый элемент помещается в конец списка. Указатель записи типа "address" должен передаваться в качестве аргумента функции: { добавление в список с одной связью } procedure SL_Store(i: AddrPointer); Legin if last=nil then { первый элемент списка } 2 begin last := i; start := i; i^.next := nil; end else begin last^.next := i; i^.next := nil; last := i; Энциклопедия по Турбо-Паскалю ч.1 = 49 = end; end; { конец процедуры добавления элементов в список с одной связью } Следует помнить, что до первого обращения к этой функции пе- ременные "start" и "last" должны быть установлены на значение "nil". Можно предусмотреть отдельную операцию по сортировке списка, созданного с помощью указанной функции добавления элементов в список с одной связью. Однако упорядочения легче добиться во вре- мя вставки путем установки каждого нового элемента в соответству- ющее место списка. Кроме того, если список уже является отсорти- рованным, то имеет смысл сохранить его упорядоченность, вставляя каждый новый элемент в соответствующее место списка. Для этого делается последовательный просмотр списка до тех пор, пока не бу- дет найдено нужное место. В это место вставляется новый адрес и делается соответствующее изменение связей. При вставке элемента в список с одной связью может воникнуть одна из трех ситуаций. Во-первых, новый элемент может оказаться первым в списке. Во-вторых, он может встать между другими двумя элементами и в-третьих, он может оказаться последним элементом в списке. На рис.9 показано, как для каждого из этих случаев изме- няются связи. Если изменяется первый элемент списка, то везде в программе должна быть изменена точка входа в список. Для того, чтобы избе- жать этого, в качестве первого элемента нужно использовать фик- тивный элемент. Этот фиктивный элемент должен иметь такое значе- ние, которое обеспечивает ему первое место в списке. В этом случае точка входа в список не будет меняться. Однако, недостат- ком такого метода является необходимость расхода дополнительной памяти для фиктивного элемента и поэтому в показанном примере этот метод не используется. Энциклопедия по Турбо-Паскалю ч.1 = 50 = 1 Новый первый элемент +-----+ +-----+ ¦2 new¦ ¦2 new¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ +-----+ +-----+ 4becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 6 New Middle Item +-----+ +-----+ ¦2 new¦ ¦2 new¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ +-----+ +-----+ 4becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ 7 New Last Item +-----+ +-----+ ¦2 new¦ ¦2 new¦ +-----¦ +-----¦ ¦ ¦ ¦5 nil¦ +-----+ +-----+ 4becomes +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ ¦3info¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ +-----¦ ¦ ¦ ¦ ¦ ¦5 nil¦ ¦ ¦ ¦ ¦ ¦ ¦ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ Рис.9. Вставка элемента в список с одной связью: 1 - новый первый элемент; 2 - новый элемент; 3 - информационные поля; 4 - справа дается преобразованный список; 5 - нулевой указатель связи; 6 - новый средний элемент; Энциклопедия по Турбо-Паскалю ч.1 = 51 = 7 - новый последний элемент. Приводимая ниже функция используется для вставки адресов почтовых корреспонденций в порядке возрастания фамилий /поле "name"/. В качестве результата функции выдается первый элемент списка. Входными аргументами этой функции являются указатели на начало и конец списка. { добавление элементов в список с одной связью с сохранением упорядоченности } function SLS_Store(info, start: AddrPointer; var last: AddrPointer): AddrPointer; var old, top: AddrPointer; done: boolean; begin top := start; old := nil; done := FALSE; if start=nil then begin { первый элемент списка } info^.next:=nil; last:=info; SLS_Store:=info; end else begin while (start<>nil) and (not done) do begin if start^.name < info^.name then begin old:=start; start:=start^.next; end else begin { вставка в середину } if old<>nil then begin old^.next:=info; info^.next:=start; SLS_Store:=top; { сохранить начало } done:=TRUE; end else begin info^.next:=start; { новый первый элемент } SLS_Store:=info; done:=TRUE; end; Энциклопедия по Турбо-Паскалю ч.1 = 52 = end;end; {while}
if not done then
begin
last^.next:=info; { вставка в конец }
info^.next:=nil;
last:=info;
SLS_Store:=top;
end;
end;
end;
{ конец процедуры упорядоченной вставки в список с одной связью}
Для связанного списка обычно не предусматривается отдельная функция, связанная с процессом поиска, при котором элементы выда- ются в порядке их расположения в списке. Эта функция обычно прог- раммируется очень просто и оформляется вместе с другими функция- ми, например, поиском отдельного элемента, его удалением или выводом на экран. В качестве примера ниже приводится процедура вывода всех фамилий в списке адресов почтовых корреспонденций:
procedure Display(start: AddrPointer);begin
while start<>nil do begin
WriteLn(start^.name);
start:=start^.next;
end;
end; { конец процедуры вывода}
Здесь переменная "start" является указателем на первую за-
пись в списке.
Поиск элемента в списке представляет собой простую процедуру прохода по цепочке. Процедуру поиска адресов по фамилиям можно составить следующим образом:
function Search(start:AddrPointer;name:str80):AddrPointer;
var
done:boolean;
begin
done := FALSE; while (start<>nil) and (not done) do
begin
if name=start^.name then
begin
Search:=start;
done:=TRUE;
end else
start:=start^.next;
end;
if start=nil then Search := nil; { нет в списке }
end; { конец процедуры поиска элемента }
Поскольку эта процедура поиска в результате выдает указатель на тот элемент списка, который соответствует искомой фамилии, пе- ременная "Search" должна объявляться как указатель записи типа "address". Если требуемый элемент отсутствует в списке, то в ре- зультате выдается нулевой указатель.
Процедура удаления элемента из списка с одной связью прог- раммируется просто. Как при вставке элемента здесь может встре- титься один из трех случаев: удаляется первый элемент, удаляется средний элемент и удаляется последний элемент. На рис.10 иллюст- рируется каждая ситуация.
Рис.10. Удаление элемента из списка с одной связью:1 - удаление первого элемента;
2 - левый список преобразуется в правый;
3 - информационные поля;
4 - удаленный элемент;
5 - связь с нулевым значением;
6 - удаление среднего элемента;
7 - удаление последнего элемента.
Приводимая ниже функция выполняет удаление заданного элемен- та из списка записей адресов:
Энциклопедия по Турбо-Паскалю ч.1 = 54 = function SL_Delete(start, item, prior_item: AddrPointer)
:AddrPointer;
begin
if prior_item<>nil then
prior_item^.next:=item^.next
else start:= item^.next;
SL_Delete:=start;
end; { конец функции удаления элемента из списка с одной
связью } СВЯЗАННЫЕ СПИСКИ
-----------------------------------------------------------------
Очереди и стеки обладают двумя общими свойствами. Во-первых, доступ к находящимся в них данных подчиняется строгим правилам. Во-вторых, операции поиска имеют разрушительный характер. Если выбранный из стека или очереди элемент не будет где-нибудь сохра- нен, то он будет потерян. Кроме того, стеки и очереди для своей работы требуют наличия непрерывной области памяти /непрерывность должна обеспечиваться по крайней мере логически/.
В отличии от стека и очереди связанный список позволяет осу- ществлять доступ к любым элементам, поскольку каждая единица ин- формации имеет указатель на следующий элемент данных в цепочке. Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди могут работать и с простыми и со слож- ными структурами данных. Операция поиска в связанном списке не приводит к удалению и уничтожению элемента. В данном случае сле- дует предусмотреть дополнительно операцию удаления элемента из списка.
Связанные списки используются в двух основных случаях. Во -первых, при создании массивов, которые располагаются в оператив- ной памяти и размер которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей зада- чи, то вы можете использовать простой массив. Однако, если дейс- твительный размер списка вам неизвестен, то вы должны применить связанный список. Во-вторых, связанные списки используются в ба- зах данных на дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации всего диско- вого файла. По этим причинам связанные списки широко используются в программах по управлению базами данных.
Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый из которых имеет связь со следующим элементом данных. В списке с двойной связью каждый элемент имеет связь как со следующим элементом, так и с предыдущим элементом. Тип связанного списка выбирается в зависи- мости от решаемой задачи.
