Collections: LinkedList — различия между версиями
Материал из Вики ИТ мехмата ЮФУ
Juliet (обсуждение | вклад) м («Unit LinkedList» переименована в «Unit Collections: LinkedList») |
Juliet (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
[[Категория:Коды]] | [[Категория:Коды]] | ||
− | == | + | == Интерфейс == |
=== LinkedListNode === | === LinkedListNode === | ||
<source lang="Delphi"> | <source lang="Delphi"> | ||
/// Узел с двумя полями связи | /// Узел с двумя полями связи | ||
type LinkedListNode<DataType> = class | type LinkedListNode<DataType> = class | ||
− | |||
/// Значение узла | /// Значение узла | ||
property Value: DataType; | property Value: DataType; | ||
Строка 16: | Строка 15: | ||
property Next: LinkedListNode<DataType>; | property Next: LinkedListNode<DataType>; | ||
− | + | ||
/// Создает новый узел | /// Создает новый узел | ||
constructor Create(Data: DataType; Prev, Next: LinkedListNode<DataType>); | constructor Create(Data: DataType; Prev, Next: LinkedListNode<DataType>); | ||
Строка 26: | Строка 25: | ||
/// Двусвязный линейный список | /// Двусвязный линейный список | ||
type LinkedList<DataType> = class | type LinkedList<DataType> = class | ||
− | |||
/// Первый элемент (голова) — только на чтение | /// Первый элемент (голова) — только на чтение | ||
property First: LinkedListNode<DataType>; | property First: LinkedListNode<DataType>; | ||
Строка 33: | Строка 31: | ||
property Last: LinkedListNode<DataType>; | property Last: LinkedListNode<DataType>; | ||
− | + | ||
/// Добавляет элемент x в начало списка | /// Добавляет элемент x в начало списка | ||
procedure AddFirst(x: DataType); | procedure AddFirst(x: DataType); | ||
Строка 55: | Строка 53: | ||
procedure Remove(node: LinkedListNode<DataType>); | procedure Remove(node: LinkedListNode<DataType>); | ||
− | + | ||
/// Выводит содержимое списка на консоль | /// Выводит содержимое списка на консоль | ||
procedure Println(); | procedure Println(); | ||
Строка 64: | Строка 62: | ||
</source> | </source> | ||
− | == | + | == Реализация == |
+ | === LinkedListNode === | ||
<source lang="Delphi"> | <source lang="Delphi"> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
interface | interface | ||
− | |||
− | |||
− | |||
type | type | ||
/// Узел с двумя полями связи | /// Узел с двумя полями связи | ||
Строка 108: | Строка 99: | ||
− | + | implementation | |
+ | |||
+ | {Создает новый узел} | ||
+ | constructor LinkedListNode<DataType>.Create(Data: DataType; Prev, Next: LinkedListNode<DataType>); | ||
+ | begin | ||
+ | fData := Data; | ||
+ | fPrev := Prev; | ||
+ | fNext := Next; | ||
+ | end; | ||
+ | </source> | ||
+ | |||
+ | === LinkedList === | ||
+ | <source lang="Delphi"> | ||
+ | interface | ||
+ | |||
type | type | ||
/// Двусвязный линейный список | /// Двусвязный линейный список | ||
Строка 170: | Строка 175: | ||
implementation | implementation | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
// ---------------------------- Стандартные методы --------------------------- | // ---------------------------- Стандартные методы --------------------------- | ||
Строка 312: | Строка 305: | ||
writeln(); | writeln(); | ||
end; | end; | ||
− | |||
− | |||
</source> | </source> | ||
== Примеры использования == | == Примеры использования == | ||
<source lang="Delphi"> | <source lang="Delphi"> | ||
− | uses | + | uses Collections; |
begin | begin | ||
Строка 391: | Строка 382: | ||
== См. также == | == См. также == | ||
− | [[Unit Collections | Collections]] | + | [[Unit Collections | Collections]] (полный текст модуля): |
+ | |||
+ | * [[Unit Collections: Stack | Stack]] | ||
+ | * [[Unit Collections: Queue | Queue]] | ||
+ | * [[Unit Collections: DynArray | DynArray]] | ||
+ | * [[Unit Collections: SimpleSet | SimpleSet]] | ||
+ | *[[Unit Collections: AssocArray | AssocArray]] |
Версия 19:17, 1 мая 2009
Содержание
Интерфейс
LinkedListNode
/// Узел с двумя полями связи
type LinkedListNode<DataType> = class
/// Значение узла
property Value: DataType;
/// Ссылка на предыдущий элемент — только на чтение
property Prev: LinkedListNode<DataType>;
/// Ссылка на следующий элемент — только на чтение
property Next: LinkedListNode<DataType>;
/// Создает новый узел
constructor Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
end;
LinkedList
/// Двусвязный линейный список
type LinkedList<DataType> = class
/// Первый элемент (голова) — только на чтение
property First: LinkedListNode<DataType>;
/// Последний элемент (хвост) — только на чтение
property Last: LinkedListNode<DataType>;
/// Добавляет элемент x в начало списка
procedure AddFirst(x: DataType);
/// Добавляет элемент x в конец списка
procedure AddLast(x: DataType);
/// Удаляет первый элемент списка
procedure RemoveFirst();
/// Удаляет последний элемент списка
procedure RemoveLast();
/// Добавляет элемент x перед node
procedure AddBefore(node: LinkedListNode<DataType>; x: DataType);
/// Добавляет элемент x после node
procedure AddAfter(node: LinkedListNode<DataType>; x: DataType);
/// Удаляет элемент node
procedure Remove(node: LinkedListNode<DataType>);
/// Выводит содержимое списка на консоль
procedure Println();
/// Выводит содержимое списка на консоль в обратном порядке
procedure ReversePrintln();
end;
Реализация
LinkedListNode
interface
type
/// Узел с двумя полями связи
LinkedListNode<DataType> = class
private
// ----------------------------------- Поля ----------------------------------
/// Значение узла
fData: DataType;
/// Ссылка на предыдущий элемент
fPrev: LinkedListNode<DataType>;
/// Ссылка на следующий элемент
fNext: LinkedListNode<DataType>;
public
// --------------------------------- Свойства --------------------------------
/// Значение узла
property Value: DataType read fData write fData;
/// Ссылка на предыдущий элемент — только на чтение
property Prev: LinkedListNode<DataType> read fPrev;
/// Ссылка на следующий элемент — только на чтение
property Next: LinkedListNode<DataType> read fNext;
// ---------------------------- Стандартные методы ---------------------------
/// <summary>
/// Создает новый узел
/// </summary>
/// <param name="DataType">Значение узла</param>
/// <param name="Prev">Ссылка на предыдущий элемент</param>
/// <param name="Next">Ссылка на следующий элемент</param>
constructor Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
end;
implementation
{Создает новый узел}
constructor LinkedListNode<DataType>.Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
begin
fData := Data;
fPrev := Prev;
fNext := Next;
end;
LinkedList
interface
type
/// Двусвязный линейный список
LinkedList<DataType> = class
private
/// Первый элемент (голова)
fFirst: LinkedListNode<DataType> := nil;
/// Последний элемент (хвост)
fLast: LinkedListNode<DataType> := nil;
public
// --------------------------------- Свойства --------------------------------
/// Первый элемент (голова) — только на чтение
property First: LinkedListNode<DataType> read fFirst;
/// Последний элемент (хвост) — только на чтение
property Last: LinkedListNode<DataType> read fLast;
// ---------------------------- Стандартные методы ---------------------------
/// <summary>
/// Добавляет элемент x в начало списка
/// </summary>
/// <param name="x">Добавляемый элемент</param>
procedure AddFirst(x: DataType);
/// <summary>
/// Добавляет элемент x в конец списка
/// </summary>
/// <param name="x">Добавляемый элемент</param>
procedure AddLast(x: DataType);
/// Удаляет первый элемент списка
procedure RemoveFirst();
/// Удаляет последний элемент списка
procedure RemoveLast();
/// <summary>
/// Добавляет элемент x перед node
/// </summary>
/// <param name="node">Ссылка на элемент, перед которым нужно добавить новый</param>
/// <param name="x">Добавляемый элемент</param>
procedure AddBefore(node: LinkedListNode<DataType>; x: DataType);
/// <summary>
/// Добавляет элемент x после node
/// </summary>
/// <param name="node">Ссылка на элемент, после которого нужно добавить новый</param>
/// <param name="x">Добавляемый элемент</param>
procedure AddAfter(node: LinkedListNode<DataType>; x: DataType);
/// <summary>
/// Удаляет элемент node
/// </summary>
/// <param name="node">Ссылка на элемент, который нужно удалить</param>
procedure Remove(node: LinkedListNode<DataType>);
// ---------------------------------- Вывод ----------------------------------
/// Выводит содержимое списка на консоль
procedure Println();
/// Выводит содержимое списка на консоль в обратном порядке
procedure ReversePrintln();
end;
implementation
// ---------------------------- Стандартные методы ---------------------------
{Добавляет элемент x в начало списка}
procedure LinkedList<DataType>.AddFirst(x: DataType);
begin
var val := new LinkedListNode<DataType>(x, nil, fFirst);
if fFirst <> nil then
fFirst.fPrev := val;
fFirst := val;
if fLast = nil then
fLast := fFirst;
end;
{Добавляет элемент x в конец списка}
procedure LinkedList<DataType>.AddLast(x: DataType);
begin
var val := new LinkedListNode<DataType>(x, fLast, nil);
if fLast <> nil then
fLast.fNext := val;
fLast := val;
if fFirst = nil then
fFirst := fLast;
end;
{Удаляет первый элемент списка}
procedure LinkedList<DataType>.RemoveFirst();
begin
if fFirst = nil then
raise new Exception(
'Попытка удаления из пустого списка!');
fFirst := fFirst.fNext;
if fFirst = nil then
fLast := nil
else
fFirst.fPrev := nil;
end;
{Удаляет последний элемент списка}
procedure LinkedList<DataType>.RemoveLast();
begin
if fLast = nil then
raise new Exception(
'Попытка удаления из пустого списка!');
fLast := fLast.fPrev;
if fLast = nil then
fFirst := nil
else
fLast.fNext := nil;
end;
{Добавляет элемент x перед node}
procedure LinkedList<DataType>.AddBefore(node: LinkedListNode<DataType>; x: DataType);
begin
if node = nil then
raise new Exception(
'Аргумент node метода является нулевой ссылкой!');
if node = fFirst then
AddFirst(x)
else
begin
var val := new LinkedListNode<DataType>(x, node.fPrev, node);
node.fPrev.fNext := val;
node.fPrev := val;
end;
end;
{Добавляет элемент x после node}
procedure LinkedList<DataType>.AddAfter(node: LinkedListNode<DataType>; x: DataType);
begin
if node = nil then
raise new Exception(
'Аргумент node метода является нулевой ссылкой!');
if node = fLast then
AddLast(x)
else
begin
var val := new LinkedListNode<DataType>(x, node, node.fNext);
node.fNext.fPrev := val;
node.fNext := val;
end;
end;
{Удаляет элемент node}
procedure LinkedList<DataType>.Remove(node: LinkedListNode<DataType>);
begin
if node = nil then
raise new Exception(
'Аргумент node метода является нулевой ссылкой!');
if node = fFirst then
RemoveFirst
else if node = fLast then
RemoveLast
else
begin
node.fPrev.fNext := node.fNext;
node.fNext.fPrev := node.fPrev;
end;
end;
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое списка на консоль}
procedure LinkedList<DataType>.Println();
begin
var cur := fFirst;
while cur <> nil do
begin
write(cur.Value, ' ');
cur := cur.Next;
end;
writeln();
end;
{Выводит содержимое списка на консоль в обратном порядке}
procedure LinkedList<DataType>.ReversePrintln();
begin
var cur := fLast;
while cur <> nil do
begin
write(cur.Value, ' ');
cur :=cur.Prev;
end;
writeln();
end;
Примеры использования
uses Collections;
begin
// Создание объекта двусвязного линейного списка
var list := new LinkedList<integer>;
// Добавление нового элемента в начало
list.AddFirst(5);
// Добавление нового элемента в конец
list.AddLast(-9);
list.AddLast(11);
// Вывод содержимого в прямом порядке
list.Println;
writeln();
// Вывод содержимого в обратном порядке
list.ReversePrintln;
writeln();
var cur := list.First;
// Добавление элемента в позицию после cur
list.AddAfter(cur, 36);
list.Println;
writeln();
cur := cur.Next;
// Добавление элемента в позицию перед cur
list.AddBefore(cur, -36);
list.Println;
writeln();
// Удаление текущего элемента
list.Remove(cur);
list.Println;
writeln();
// Удаление первого элемента
list.RemoveFirst;
list.Println;
writeln();
// Удаление последнего элемента
list.RemoveLast;
list.Println;
writeln();
// Обработка исключений
cur := nil;
try
list.Remove(cur);
except
on e: exception do
writeln(e);
end;
list.RemoveFirst;
list.RemoveLast; // теперь список пуст
try
list.RemoveFirst;
except
on e1: exception do
writeln(e1);
end;
end.
См. также
Collections (полный текст модуля):