Почему связанный список лучше массива

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

С чего начнем (Постановка задачи)

Нужно обработать список сущностей. Сама по себе сущность (для простоты) представляет собой модель (объект) в которой всего одно свойство "value".

Model( value: int )

Решение через массив + stdClass

Многие разработчики сразу подумают "если мне нужно обработать список моделей мне нужен массив". Массив самая простая структура данных (На мой взгляд).

Для решения данной проблемы нам подойдет следующий код:

$count = 100;
$list = [];

for ($index = 0; $index <= $count; $index++) {
  $model = new stdClass(); // создаем обьект (модель)
  $model->value = $index;  // указываем значение
  
  $list[$index] = $model;  // вносим новую модель в массив
}

В чем же плюсы:

1. Проще (мало кода) - чем проще тем лучше скажут многие.

Минусы:

1. Ох уж этот stdClass. Мало того что нет интерфейса взаимодействия, так еще возможны утечки памяти. (В этой статье описаны его минусы).

2. Потребляет памяти больше чем ожидалось. В PHP массивы не самые экономные так еще и stdClass кушает больше чем ожидалось.

Решение через массив + Model class

Текущее решение похоже на (Решение через массив + stdClass). Единственное и важное отличие это создание интерфейса (класса модели)

$count = 100;
$list = [];

class Model {
  protected int $value;         // значение модели
  public function __construct(int $value)
  {
    $this->value = $value;
  }
}

for ($index = 0; $index <= $count; $index++) {  
  $list[$index] = new Model($index);  // вносим новую модель в массив
}

Какие плюсы:

1. Код прост.

2. Есть интерфейс взаимодействия с моделью.

3. В виду отсутствия stdClass меньше потребляет памяти.

Какие минусы:

1. Чуть усложняется работа с массивом (например фильтр возможно потребует нового метода в модель).

2. В PHP массивы не самые экономные по памяти.

Решение через связанный список

Не многие (в основном профи) могут подумать а может стоит использовать связанный список?

$count = 100;

class LinkedList {
  protected int $value;         // значение модели
  protected ?LinkedList $next = null; // следующий элемент

  public function __construct(int $value)
  {
    $this->value = $value;
  }

  // добавление следующего элемента 
  public function add(LinkedList $next): LinkedList
  {
    $this->next = $next;
    return $next;
  }
}

$root = new Node(0); // связаный список

for($index = 1; $index <= $count; $index++) {
	$node = ($node ?? $root)->add(new Node($index));
}
unset($node);

Какие плюсы:

1. Есть интерфейс взаимодействия

2. Меньшее потребление памяти

3. Многие будущие операции будут выполнятся быстрее (смотря как напишет программист)

Какие минусы:

1. Чуть усложняется работа с данными так как структура другая фильтр будет работать по другому.

Тесты

Наш тест будет происходить на платформе OnlinePHP.io (Можно стразу зайти и проверить результаты)

Вывод

Хоть мы тестили на 100 элементах, даже на них видно какой объем памяти занимал тот или иной вариант решения.

Если ваш продукт работает с большим количеством данных, то самый лучший вариант для вас это "Связанный список". Если ваш продукт еще не работает с большим количеством данных, то мой совет не используйте stdClass.

Полный скрипт (для самостоятельных тестов)

Этот код был написан только для ознакомительных целей (Не используйте его в своих проектах).

$count = 100;

class LinkedList {
	protected int $value;
	protected ?LinkedList $next = null;
	public function __construct(int $value) {
		$this->value = $value;
	}
	public function add(LinkedList $next): LinkedList {
		$this->next = $next;
		return $next;
	}
}

class Model {
	protected int $value;
	public function __construct(int $value) {
		$this->value = $value;
	}
}

// -----------------------------------
// -----------------------------------

$memory_get_usage = memory_get_usage();

echo 'list before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage ) . "\n";

$root = new LinkedList(0);

for($i = 1; $i <= $count; $i++) {
	$next = ($next ?? $root)->add(new LinkedList($i));
}
unset($next);

echo 'list set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";

unset($root);
echo 'list after -- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n\n";

// -----------------------------------
// -----------------------------------

$memory_get_usage = memory_get_usage();

echo 'array + model before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";
$list = [];
for($index = 0; $index <= $count; $index++) {
	$list[$index] = new Model($index);
}
echo 'array + model set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";
$list = [];
unset($list);
echo 'array + model after -- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n\n";

// -----------------------------------
// -----------------------------------

$memory_get_usage = memory_get_usage();

echo 'array + stdClass before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";
$list = [];
for($index = 0; $index <= $count; $index++) {
	$model = new stdClass();
	$model->value = $index;
	$list[$index] = $model;
}
echo 'array + stdClass set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";
$list = [];
unset($list);
echo 'array + stdClass after -- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n\n";