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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
м Unit LinkedList» переименована в «Unit Collections: LinkedList»)
Строка 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>
  
== Полный текст модуля LinkedListUnit ==
+
== Реализация ==
 +
=== LinkedListNode  ===
 
<source lang="Delphi">
 
<source lang="Delphi">
/// Модуль содержит шаблоны классов
 
///  LinkedListNode — узла с двумя полями связи
 
///  LinkedList — двусвязного линейного списка
 
unit LinkedListUnit;
 
 
 
interface
 
interface
  
uses System;  // для генерации исключений
 
 
// ========================================= LinkedListNode =======================================
 
 
type
 
type
 
   /// Узел с двумя полями связи
 
   /// Узел с двумя полями связи
Строка 108: Строка 99:
 
    
 
    
 
    
 
    
// =========================================== LinkedList =========================================
+
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
 
// ========================================= LinkedListNode =======================================
 
{Создает новый узел}
 
constructor LinkedListNode<DataType>.Create(Data: DataType; Prev, Next: LinkedListNode<DataType>);
 
begin
 
  fData := Data;
 
  fPrev := Prev;
 
  fNext := Next;
 
end;
 
 
 
// =========================================== LinkedList =========================================
 
  
 
// ---------------------------- Стандартные методы ---------------------------
 
// ---------------------------- Стандартные методы ---------------------------
Строка 312: Строка 305:
 
   writeln();
 
   writeln();
 
end;
 
end;
 
end.
 
 
</source>
 
</source>
  
 
== Примеры использования ==
 
== Примеры использования ==
 
<source lang="Delphi">
 
<source lang="Delphi">
uses LinkedListUnit;
+
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 (полный текст модуля):