Collections — различия между версиями

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
(Collections)
(Collections)
Строка 92: Строка 92:
 
   
 
   
 
   
 
   
// ============================================= STACK ============================================
+
// ============================================= Stack ============================================
 
type
 
type
 
   /// Шаблон класса Stack [Стек]
 
   /// Шаблон класса Stack [Стек]
Строка 125: Строка 125:
 
   
 
   
 
   
 
   
// ============================================= QUEUE ============================================
+
// ============================================= Queue ============================================
 
type   
 
type   
 
   /// Шаблон класса Queue [Очередь]
 
   /// Шаблон класса Queue [Очередь]
Строка 160: Строка 160:
 
   
 
   
 
   
 
   
// =========================================== DYN_ARRAY ==========================================
+
// =========================================== DynArray ==========================================
 
const
 
const
 
   /// Минимальная емкость, устанавливаемая при создании массива
 
   /// Минимальная емкость, устанавливаемая при создании массива
Строка 244: Строка 244:
 
   
 
   
 
   
 
   
// =========================================== SIMPLE_SET =========================================
+
// =========================================== SimpleSet =========================================
 
type  
 
type  
 
   /// Шаблон класса SimpleSet [Простое множество]
 
   /// Шаблон класса SimpleSet [Простое множество]
Строка 278: Строка 278:
  
 
   
 
   
// =========================================== ASSOC_ARRAY ========================================
+
// =========================================== AssocArray ========================================
 
type
 
type
 
   /// Шаблон класса AssocArray [Ассоциативный массив]
 
   /// Шаблон класса AssocArray [Ассоциативный массив]
Строка 405: Строка 405:
 
   
 
   
 
   
 
   
// ============================================= STACK ============================================
+
// ============================================= Stack ============================================
 
   
 
   
 
// ---------------------------- Стандартные методы ---------------------------
 
// ---------------------------- Стандартные методы ---------------------------
Строка 464: Строка 464:
 
   
 
   
 
   
 
   
// ============================================= QUEUE ============================================
+
// ============================================= Queue ============================================
 
   
 
   
 
// ---------------------------- Стандартные методы ---------------------------
 
// ---------------------------- Стандартные методы ---------------------------
Строка 538: Строка 538:
 
   
 
   
 
   
 
   
// =========================================== DYN_ARRAY ==========================================  
+
// =========================================== DynArray ==========================================  
  
 
// ----------------------------- Сеттеры/Геттеры -----------------------------
 
// ----------------------------- Сеттеры/Геттеры -----------------------------
Строка 662: Строка 662:
 
   
 
   
 
   
 
   
// =========================================== SIMPLE_SET =========================================
+
// =========================================== SimpleSet =========================================
  
 
// ---------------------------- Стандартные методы ---------------------------
 
// ---------------------------- Стандартные методы ---------------------------
Строка 694: Строка 694:
 
   
 
   
 
   
 
   
// =========================================== ASSOC_ARRAY ========================================
+
// =========================================== AssocArray ========================================
  
 
// ----------------------------- Сеттеры/Геттеры -----------------------------
 
// ----------------------------- Сеттеры/Геттеры -----------------------------

Версия 19:19, 1 мая 2009

Nodes (вспомогательный модуль)

/// Модуль содержит шаблоны классов
///   SingleNode — узла с одним полем связи
///   DoubleNode — узла с двумя полями связи
unit Nodes;

interface

type

//-------------------------------------------SINGLE_NODE-------------------------------------------
  /// Узел с одним полем связи
  SingleNode<DataType> = class
    /// Значение узла
    data: DataType;
    /// Ссылка на следующий элемент
    next: SingleNode<DataType>;
    
    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="pData">Значение узла</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    constructor Create(pData: DataType; pNext: SingleNode<DataType>);
  end;

// -------------------------------------------DOUBLE_NODE------------------------------------------  
  /// Узел с двумя полями связи
  DoubleNode<DataType> = class
    /// Значение узла
    data: DataType;
    /// Ссылка на следующий элемент
    next: DoubleNode<DataType>;
    /// Ссылка на предыдущий элемент
    prev: DoubleNode<DataType>;
    
    /// <summary>
    /// Конструктор
    /// </summary>
    /// <param name="pData">Значение узла</param>
    /// <param name="pNext">Ссылка на следующий элемент</param>
    /// <param name="pPrev">Ссылка на предыдущий элемент</param>
    constructor Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
  end;

implementation

//-------------------------------------------SINGLE_NODE-------------------------------------------
{Конструктор
    pData — значение узла
    pNext — cсылка на следующий элемент}
constructor SingleNode<DataType>.Create(pData: DataType; pNext: SingleNode<DataType>);
begin
  data := pData;
  next := pNext;
end;

// -------------------------------------------DOUBLE_NODE------------------------------------------  
{Конструктор
    pData — значение узла
    pNext — cсылка на следующий элемент
    pPrev — ссылка на предыдущий элемент}
constructor DoubleNode<DataType>.Create(pData: DataType; pPrev, pNext: DoubleNode<DataType>);
begin
  data := pData;
  next := pNext;
  prev := pPrev;
end;

end.

Collections

/// Модуль содержит шаблоны классов
///   Stack — стек
///   Queue — очередь
///   DynArray — динамический массив с автоконтролем памяти
///   SimpleSet — простое множество (с минимальным набором операций)
///   AssocArray — ассоциативный массив
///   LinkedListNode — узел с двумя полями связи
///   LinkedList — двусвязный линейный список
unit Collections;
 
interface
 
uses Nodes;   // для использования типа SingleNode<DataType> — 
              // узла с одним полем связи
 
 
// ============================================= Stack ============================================
type
  /// Шаблон класса Stack [Стек]
  Stack<DataType> = class
  private 
    // ----------------------------------- Поля ----------------------------------
    /// Вершина стека
    fTop: SingleNode<DataType> := nil; 
 
  public 
    // ---------------------------- Стандартные методы ---------------------------
    /// Создает пустой стек
    constructor Create;
 
    /// <summary>
    /// Кладет элемент x на вершину стека
    /// </summary>
    /// <param name="x">Новый элемент</param>
    procedure Push(x: DataType);
    /// Возвращает значение элемента на вершине, снимая его со стека
    function Pop: DataType;
    /// Возвращает значение элемента на вершине стека, не снимая его
    function Top: DataType;
 
    /// Возвращает истину, если стек пуст
    function IsEmpty: boolean; 
    
    // ---------------------------------- Вывод ----------------------------------
    /// Выводит содержимое стека на консоль
    procedure Println();
  end;
 
 
// ============================================= Queue ============================================
type  
  /// Шаблон класса Queue [Очередь]
  Queue<DataType> = class
  private
    // ----------------------------------- Поля ----------------------------------
    /// Голова очереди
    head: SingleNode<DataType>;
    /// Хвост очереди
    tail: SingleNode<DataType>;
 
  public
    // ---------------------------- Стандартные методы ---------------------------
    /// Создает пустую очередь
    constructor Create;
 
    /// <summary>
    /// Добавляет элемент x в хвост очереди
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure Enqueue(x: DataType);
    /// Возвращает значение элемента в голове, удаляя его из очереди
    function Dequeue: DataType;
    /// Возвращает значение элемента в голове очереди, не удаляя его
    function Top: DataType;
 
    /// Возвращает истину, если очередь пуста
    function IsEmpty: boolean;
 
    // ---------------------------------- Вывод ----------------------------------
    /// Выводит содержимое очереди на консоль
    procedure Println();
  end;
 
 
// =========================================== DynArray ==========================================
const
  /// Минимальная емкость, устанавливаемая при создании массива
  MIN_CAP = 4;
  /// Коэффициент увеличения емкости массива при её нехватке
  INC_CAP_FACTOR = 2;
 
type
  /// Шаблон класса DynArray [Динамический массив с автоконтролем памяти]
  DynArray<DataType> = class
  private
    // ----------------------------------- Поля ----------------------------------
    /// Встроенный динамический массив, содержащий данные
    data: array of DataType;
    /// Размер массива
    size: integer;
    /// Емкость массива
    cap: integer;
    
    // ----------------------------- Сеттеры/Геттеры -----------------------------
    /// Устанавливает элемент с индексом ind равным x
    procedure SetElem(ind: integer; x: DataType);
    /// Возвращает элемент массива с индексом ind
    function GetElem(ind: integer): DataType;
 
  public
    // ---------------------------- Стандартные методы ---------------------------
    /// Создает массив размера pSize
    constructor Create(pSize: integer := 0);
 
    /// <summary>
    /// Выделяет новую память. Емкость увеличивается до newCap.
    /// (Если newCap меньше текущей емкости, ничего не происходит) 
    /// </summary>
    /// <param name="newCap">Новая емкость массива</param>
    procedure Reserve(newCap: integer);
    /// <summary>
    /// Устанавливает новый размер массива равным newSize
    /// </summary>
    /// <param name="newSize">Новый размер массива</param>
    procedure Resize(newSize: integer);
 
    /// <summary>
    /// Добавляет элемент x в конец массива 
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>
    procedure Add(x: DataType);
    /// <summary>
    /// Вставляет элемент x в позицию pos
    /// </summary>
    /// <param name="pos">Позиция, в которую вставляется элемент</param>
    /// <param name="x">Вставляемый элемент</param>
    procedure Insert(pos: integer; x: DataType);
    /// <summary>
    /// Удаляет элемент массива из позиции pos
    /// </summary>
    /// <param name="pos">Позиция, из которой удаляется элемент</param>
    procedure Remove(pos: integer);
 
    /// <summary>
    /// Возвращает индекс первого элемента массива равного x
    /// или -1, если такого элемента нет
    /// </summary>
    /// <param name="x">Искомый элемент</param>
    function Find(x: DataType): integer;
    
    // --------------------------------- Свойства --------------------------------
    /// Количество элементов (размер) массива
    property Count: integer read size write Resize;
    /// Емкость массива (отведенная память)
    property Capacity: integer read cap write Reserve;
 
    /// Позволяет обращаться к элементам массива по индексу 
    /// (например, apples[5])
    property Elem[index: integer]: DataType read GetElem write SetElem; default;
 
    // ---------------------------------- Вывод ----------------------------------
    /// Выводит содержимое массива на консоль
    procedure Println();
    /// Выводит содержимое массива на консоль в обратном порядке
    procedure PrintlnReverse();
  end;
 
 
// =========================================== SimpleSet =========================================
type 
  /// Шаблон класса SimpleSet [Простое множество]
  SimpleSet<DataType> = class 
  private
    // ----------------------------------- Поля ----------------------------------
    /// Элементы множества
    data := new DynArray<DataType>;
 
  public
    // ---------------------------- Стандартные методы ---------------------------
    /// <summary>
    /// Добавляет элемент x во множество, если его там еще нет
    /// </summary>
    /// <param name="x">Добавляемый элемент</param>    
    procedure Add(x: DataType);
    /// <summary>
    /// Удаляет элемент x из множества, если он там есть
    /// </summary>
    /// <param name="x">Удаляемый элемент</param>
    procedure Remove(x: DataType);
 
    /// <summary>
    /// Возвращает истину, если множество содержит элемент x
    /// </summary>
    /// <param name="x">Искомый элемент</param>          
    function Contains(x: DataType): boolean;   
 
    // ---------------------------------- Вывод ----------------------------------
    ///Выводит содержимое множества на консоль
    procedure Println();
end;

 
// =========================================== AssocArray ========================================
type
  /// Шаблон класса AssocArray [Ассоциативный массив]
  AssocArray<KeyType, ValueType> = class
  private
    // ----------------------------------- Поля ----------------------------------
    /// Ключи
    keys: DynArray<KeyType> := new DynArray<KeyType>;
    /// Значения, соответствующие ключам
    values: DynArray<ValueType> := new DynArray<ValueType>;
    
    // ----------------------------- Сеттеры/Геттеры -----------------------------
    /// Устанавливает значение элемента с ключом key равным value
    procedure SetElem(key: KeyType; value: ValueType);
    /// Возвращает значение элемента с ключом key
    function GetElem(key: KeyType): ValueType;
 
  public
    // --------------------------------- Свойства --------------------------------
    /// Позволяет обращаться к элементам массива по ключу
    /// (Например, zoo['крокодил'])
    property Elem[key: KeyType]: ValueType read GetElem write SetElem; default;
    
    // ---------------------------------- Вывод ----------------------------------
    ///Выводит содержимое ассоциативного массива на консоль
    procedure Println();
  end;
  
  
// ========================================= LinkedListNode =======================================
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;
  
  
// =========================================== LinkedList =========================================
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
 
 
// ============================================= Stack ============================================
 
// ---------------------------- Стандартные методы ---------------------------
{Создает пустой стек}
constructor Stack<DataType>.Create;
begin
  fTop := nil;
end;
 
{Кладет элемент x на вершину стека} 
procedure Stack<DataType>.Push(x: DataType);
begin
  fTop := new SingleNode<DataType>(x, fTop);
end;
 
{Возвращает значение элемента на вершине, снимая его со стека}
function Stack<DataType>.Pop: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка снятия элемента с пустого стека!');
 
  result := fTop.data;
  fTop := fTop.next;  // элемент снимается с вершины стека
                      // (т.е. вершиной становится следующий элемент)
end;
 
{Возвращает значение элемента на вершине стека, не снимая его}
function Stack<DataType>.Top: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка получения элемента с пустого стека!');
 
  result := fTop.data;
end;
 
{Возвращает истину, если стек пуст}
function Stack<DataType>.IsEmpty: boolean;
begin
  result := (fTop = nil);
end;
 
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое стека на консоль}
procedure Stack<DataType>.Println();
begin
  if not IsEmpty then
  begin
    var curElem := fTop;
 
    while curElem <> nil do
    begin
      write(curElem.data, ' ');
      curElem := curElem.next;
    end;
  end;
  writeln();
end;
 
 
// ============================================= Queue ============================================
 
// ---------------------------- Стандартные методы ---------------------------
{Создает пустую очередь}
constructor Queue<DataType>.Create;
begin
  head := nil;
  tail := nil;
end;
 
{Добавляет элемент x в хвост очереди} 
procedure Queue<DataType>.Enqueue(x: DataType);
begin
  if IsEmpty then
  begin
    head := new SingleNode<DataType>(x, nil);
    tail := head;
  end
  else
  begin
    tail.next := new SingleNode<DataType>(x, nil);
    tail := tail.next;  // элемент удаляется из хвоста очереди
                        // (т.е. хвостом становится следующий элемент)
  end;
end;
 
{Возвращает значение элемента в голове, удаляя его из очереди}
function Queue<DataType>.Dequeue: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка удаления элемента из пустой очереди!');
 
  result := head.data;
  head := head.next;  // элемент удаляется из головы очереди
                      // (т.е. головой становится следующий элемент)
  if head = nil then
    tail := nil;
end;
 
{Возвращает значение элемента в голове очереди, не удаляя его}
function Queue<DataType>.Top: DataType;
begin
  if IsEmpty then 
     raise new Exception('Попытка получения элемента из пустой очереди!');
 
  result := head.data;
end;
 
{Возвращает истину, если очередь пуста}
function Queue<DataType>.IsEmpty: boolean;
begin
  result := (head = nil);
  if result then
    Assert(tail = nil);
end;
 
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое очереди на консоль}
procedure Queue<DataType>.Println();
begin
  if not IsEmpty then
  begin
    var curElem := head;
 
    while curElem <> nil do
    begin
      write(curElem.data, ' ');
      curElem := curElem.next;
    end;
  end;
  writeln();
end;
 
 
// =========================================== DynArray ========================================== 

// ----------------------------- Сеттеры/Геттеры -----------------------------
{Устанавливает элемент с индексом ind равным x}
procedure DynArray<DataType>.SetElem(ind: integer; x: DataType);
begin
  if (ind < 0) or (ind > size-1) then 
     raise new Exception(
     'Попытка присвоить значение элементу за границей массива с индексом ' + IntToStr(ind) + '!');
 
  data[ind] := x;
end;
 
{Возвращает элемент массива с индексом ind}
function DynArray<DataType>.GetElem(ind: integer): DataType;
begin
  if (ind < 0) or (ind > size-1) then 
     raise new Exception(
     'Попытка получить значение элемента за границей массива с индексом ' + IntToStr(ind) + '!');
 
  result := data[ind];
end;

// ---------------------------- Стандартные методы ---------------------------
{Создает массив размера pSize}
constructor DynArray<DataType>.Create(pSize: integer);
begin
  if pSize < 0 then
    raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(pSize) + '!');
 
  size := pSize;
  cap := INC_CAP_FACTOR*pSize + MIN_CAP; // Устанавливаем емкость "с запасом"
  SetLength(data, cap);
end;
 
{Выделяет новую память. Емкость увеличивается до newCap.
 (Если newCap меньше текущей емкости, ничего не происходит) }
procedure DynArray<DataType>.Reserve(newCap: integer);
begin
  if newCap > cap then 
  begin
    SetLength(data, newCap);
    cap := newCap;
  end;
end;
 
{Устанавливает новый размер массива равным newSize}
procedure DynArray<DataType>.Resize(newSize: integer);
begin
  if newSize < 0 then
    raise new Exception('Попытка присвоить размеру массива отрицательное значение ' + IntToStr(newSize) + '!');
 
  if newSize > cap then
  begin
    Reserve(INC_CAP_FACTOR * newSize);
    for var i := size to newSize - 1 do // явным образом заполняем новые элементы
      data[i] := default(DataType);
  end;
  size := newSize;
end;
 
{Добавляет элемент x в конец массива }
procedure DynArray<DataType>.Add(x: DataType);
begin
  Resize(size + 1);
  data[size-1] := x;
end;
 
{Вставляет x элемент в позицию pos}
procedure DynArray<DataType>.Insert(pos: integer; x: DataType);
begin
  if (pos < 0) or (pos > size-1) then 
     raise new Exception(
     'Попытка вставки за границей массива в позицию ' + IntToStr(pos) + '!');
 
  Resize(size + 1);
  for var i := size - 2 downto pos do
    data[i+1] := data[i];
  data[pos] := x;
end;
 
{Удаляет элемент массива из позиции pos}
procedure DynArray<DataType>.Remove(pos: integer);
begin
  if (pos < 0) or (pos > size-1) then 
     raise new Exception(
     'Попытка удаления за границей массива из позиции ' + IntToStr(pos) + '!');
 
  for var i := pos to size - 2 do // сдвиг элементов влево на 1, начиная с позиции pos
    data[i] := data[i+1];
  Resize(size - 1);
end;
 
{Возвращает индекс первого элемента массива равного x
 или -1, если такого элемента нет}
function DynArray<DataType>.Find(x: DataType): integer;
begin
  result := -1;
  for var i := 0 to size - 1 do
    if data[i] = x then
    begin
      result := i;
      exit;
    end;
end;
 
// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое массива на консоль}
procedure DynArray<DataType>.Println();
begin
  for var i := 0 to size - 1 do
      write(data[i], ' '); 
  writeln();
end;
 
{Выводит содержимое массива на консоль в обратном порядке}
procedure DynArray<DataType>.PrintlnReverse();
begin
  for var i := size - 1 downto 0 do
      write(data[i], ' '); 
  writeln();
end;
 
 
// =========================================== SimpleSet =========================================

// ---------------------------- Стандартные методы ---------------------------
{Добавляет элемент x во множество, если его там еще нет}     
procedure SimpleSet<DataType>.Add(x: DataType);
begin
  if data.Find(x) = -1 then 
    data.Add(x);
end;
 
{Удаляет элемент x из множества, если он там есть}
procedure SimpleSet<DataType>.Remove(x: DataType);
begin
  var xPos := data.Find(x);
  if xPos <> -1 then
    data.Remove(xPos);
end;
 
{Возвращает истину, если множество содержит элемент x}    
function SimpleSet<DataType>.Contains(x: DataType): boolean;
begin
  result := (data.Find(x) <> -1);
end;
 
// ---------------------------------- Вывод ----------------------------------
 {Выводит содержимое множества на консоль}
procedure SimpleSet<DataType>.Println();
begin
  data.Println;
end;
 
 
// =========================================== AssocArray ========================================

// ----------------------------- Сеттеры/Геттеры -----------------------------
{Устанавливает значение элемента с ключом key равным value}
procedure AssocArray<KeyType, ValueType>.SetElem(key: KeyType; value: ValueType);
begin
  var ind := Keys.Find(key);
  if ind <> -1 then
    Values[ind] := value
  else
  begin
    Keys.Add(key);
    Values.Add(value);
  end;
end;
 
{Возвращает значение элемента с ключом key}
function AssocArray<KeyType, ValueType>.GetElem(key: KeyType): ValueType;
begin
  var ind := Keys.Find(key);
  if ind <> -1 then
    result := Values[ind]
  else
  begin
    Keys.Add(key);
    Values.Add(default(ValueType));
    result := default(ValueType);
  end;
end;

// ---------------------------------- Вывод ----------------------------------
{Выводит содержимое ассоциативного массива на консоль}
procedure AssocArray<KeyType, ValueType>.Println();
begin
  for var i := 0 to keys.Count - 1 do
    writeln(keys[i], ': ', values[i]);
end;


// ========================================= LinkedListNode =======================================
{Создает новый узел}
constructor LinkedListNode<DataType>.Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
begin
  fData := Data;
  fPrev := Prev;
  fNext := Next;
end;


// =========================================== LinkedList =========================================

// ---------------------------- Стандартные методы ---------------------------
{Добавляет элемент 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;
 
end.

См. также

LinkedList