Связные списки - новый стиль

Динамические структуры данных, к которым относятся односвяные и двусвязные списки, традиционно излагаются в теме "Указатели". С другой стороны, в языке PascalABC.NET переменные класса являются ссылками на объекты, выделяемыми в динамической памяти, и являются по-существу скрытыми указателями. Поэтому заманчиво рассказать основные операции со списками, используя ссылки вместо указателей. Остроты ощущений добавляет тот факт, что в PascalABC.NET для объектов производится автоматическая сборка мусора, поэтому освобождаемую память не надо возвращать явно.

Рассмотрим основные операции с линейными односвязными списками и приведем реализацию для указателей (слева) и ссылок (справа). Всюду считается, что переменная p имеет тип PNode для указателей и Node для ссылок.

1. Предварительные описания.

type
  PNode = ^Node;
  Node = record
    data: integer;
    next: PNode;
end;
 
function NewNode(data: integer; next: PNode): PNode;
begin
  New(Result);
  Result^.data := data;
  Result^.next := next;
end;

type
  Node = class
  data: integer;
  next: Node;
  constructor (d: integer; n: Node);
  begin
    data := d;
    next := n;
  end;
end;

Реализация с указателями - явно более "многословная". К тому же функция NewNode является внешней, и связь ее с типом PNode определяется только близостью к нему в тексте программы.

2. Вставка элемента со значением x в начало списка, на который указывает p.

p := NewNode(x,p);

p := new Node(x,p);

Почти одинаково. Во втором случае вызывается конструктор класса Node, возвращающий ссылку на созданный объект.

3. Удаление элемента из начала непустого списка, на который указывает p.

var t := p;
p := t^.next;
Dispose(t);

p := p.next;

Здесь на компактности записи решения со ссылками сказывается сборка мусора - на первый элемент больше никто не указывает, поэтому память, им занимаемая, будет освобождена при следующей сборке мусора.

4. Вставка элемента со значением x после текущего, на который указывает p.

p^.next := NewNode(x,p^.next);

p.next := new Node(x,p.next);

Одно и то же. Только ^ не надо ставить - красота! Ссылка - это разыменованный указатель. Шапочки вовсе не нужны!

5. Удаление элемента, следующего за текущим, на который указывает p.

var t := p^.next;
if t<>nil then
begin
  p^.next := t^.next;
  Dispose(t);
end;

if p.next<>nil then
p.next := p.next.next;

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

6. Вставка элемента со значением x перед текущим, на который указывает p.

p^.next := NewNode(p^.data,p^.next);
p^.data := x;
p := p^.next;

p.next := new Node(p.data,p.next);
p.data := x;
p := p.next;

Трюк. Вставляем после текущего элемента его копию, после чего меняем в текущем элементе значение на x. Решения равноценны.

7. Удаление текущего элемента, на который указывает p.

var t := p^.next;
p^:= t^;
Dispose(t);

p.data := p.next.data;
p.next := p.next.next;

Элемент, следующий за текущим, должен существовать. В случае указателей мы можем скопировать оба поля за одно присваивание:  p^:= t^. Но и это не помогает - код со ссылками все равно короче!

8. Вывод списка, на первый элемент которого указывает p.

while p<>nil do
begin
  write(p^.data,' ');
  p := p^.next;
end;

while p<>nil do
begin
  write(p.data,' ');
  p := p.next;
end;

Равноценные решения.

9. Поиск элемента со значением x. На первый элемент списка указывает p.

while (p<>nil) and (p^.data<>x) do
  p := p^.next;
var found := p<>nil;

while (p<>nil) and (p.data<>x) do
  p := p.next;
var found := p<>nil;

Равноценные решения. Шапочек справа - нет 

10. Разрушение списка.

while p<>nil do
begin
  var t := p;
  p := p^.next;
  Dispose(t);
end;

p := nil;

Вот здесь - все преимущества сборки мусора. Присвоил указателю на первый узел списка нулевое значение - и все узлы стали недоступны. При следующей сборке мусора они будут собраны.