Collections: LinkedList

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск


Интерфейс

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 (полный текст модуля):

Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Collections:_LinkedList&oldid=2070»