Устаревшие материалы АТД список

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

АТД и класс Список (Linked List)

Структура данных двусвязный список обладает следующими важными преимуществами по сравнению с другими:

  • список занимает в памяти ровно столько места, каково количество его элементов;
  • операции вставки и удаления в начало(конец) и середину списка выполняются за время, не зависящее от длины списка;

Недостатки:

  • невозможность обращаться к элементу по индексу (отсутствие произвольного доступа, только последовательный);

В задачах, где требуется перебрать элементы от первого до последнего, списки являются хорошим выбором.
В задачах, где есть вставка и удаление из середины, списки — незаменимый выбор.

<xh4> Проблемы при доступе к структуре данных «двусвязный список» </xh4> Поля Next и Prev легко изменить, «испортив» при этом список.

Способ решения:
Сделать поля связи доступными только на чтение и разрешить их изменение только строго определенному набору подпрограмм (вставка, удаление).
Технически это осуществимо с помощью

  • классов
  • защиты доступа
  • свойств

Замечание. В Object Pascal ключевое слово private не распространяется на доступ внутри данного модуля.
Это значит, что внутри одного модуля каждый может обращаться к любым приватным полям.

Вывод. Связанные классы следует помещать в один модуль.

Именно так мы и поступим с классами LinkedListNode и LinkedList: 

unit LinkedListUnit;
 
interface
 
uses System;  // для генерации исключений
 
// ========================================= 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
 
// ========================================= 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.


Пример 1. Проход по списку. 

var l: LinkedList<integer> := new LinkedList<integer>;
l.AddLast(1100);
l.AddLast(1300);
  
var node := l.First;
while node <> nil do
begin
  node.Value := node.Value * 2;
  node := node.Next;
end;

Пример 2.
Наполнить список целых случайными элементами.
Удалить все элементы с четными номерами (нумерация с единицы). 

uses LinkedListUnit;

const
  MAX_RAN = 200;
  
/// Возвращает список из n случайных целых чисел
/// в диапазоне [-MAX_RAN, MAX_RAN]
function CreateRandomLinkedList(n: integer): LinkedList<integer>;
begin
  result := new LinkedList<integer>;
  for var i := 1 to n do
    result.AddLast(Random(-MAX_RAN, MAX_RAN));
end;

/// Удаляет из списка list все элементы с четными номерами
/// (элементы нумеруются с 1цы)
procedure RemoveEvenNumbers(list: LinkedList<integer>);
begin
  var cur := list.First;
  var i := 1;
  while cur <> nil do
  begin
    if (i mod 2 = 0) then
      list.Remove(cur);
    cur := cur.Next;
    i += 1;
  end;
end;

begin
  var l := CreateRandomLinkedList(15);
  l.Println;
  
  RemoveEvenNumbers(l);
  writeln('Список после удаления элементов с четными номерами:');
  l.Println;
end.
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Устаревшие_материалы_АТД_список&oldid=4970»