Явное освобождение динамически выделенной памяти применяется во многих системах программирования и потому привычно для большинства программистов, но оно имеет серьезный недостаток: если программист по какой-то причине не освобождает выделенные блоки, память будет теряться. Эта ошибка, называемая утечкой памяти (memory leak), особенно неприятна в программах, которые длительное время работают без перезапуска — подсистемах ядра ОС, постоянно запущенных сервисах или серверных приложениях. Дополнительная неприятность состоит в том, что медленные утечки могут привести к заметным потерям памяти лишь при многодневной или даже многомесячной непрерывной эксплуатации системы, поэтому их сложно обнаружить при тестировании.
Некоторые системы программирования используют специальный метод освобождения динамической памяти, называемый сборкой мусора (garbage collection). Этот метод состоит в том, что ненужные блоки памяти не освобождаются явным образом. Вместо этого используется некоторый более или менее изощренный алгоритм, следящий за тем, какие блоки еще нужны, а какие — уже нет.
Самый простой метод отличать используемые блоки от ненужных — считать, что блок, на который есть ссылка, нужен, а блок, на который ни одной ссылки не осталось, — не нужен. Для этого к каждому блоку присоединяют дескриптор, в котором подсчитывают количество ссылок на него. Каждая передача указателя на этот блок приводит к увеличению счетчика ссылок на 1, а каждое уничтожение объекта, содержавшего указатель, — к уменьшению.
Впрочем, при наивной реализации такого подхода возникает специфическая проблема. Если у нас есть циклический список, на который нет ни одной ссылки извне, то все объекты в нем будут считаться используемыми, хотя они и являются мусором. Если мы по тем или иным причинам уверены, что кольца не возникают, метод подсчета ссылок вполне приемлем; если же мы используем графы произвольного вида, необходим более умный алгоритм.
Наиболее распространенной альтернативой подсчету ссылок является периодический просмотр всех ссылок, которые мы считаем "существующими (чтобы под этим ни подразумевалось). Если некоторые из указуемых объектов сами по себе могут содержать ссылки, мы вынуждены
осуществлять просмотр рекурсивно. Проведя эту рекурсию до конца, мы можем быть уверены, что, то и только то, что мы просмотрели, является нужными данными, и с чистой совестью можем объявить все остальное мусором. Эта стратегия решает проблему кольцевых списков, но требует остановки всей остальной деятельности, которая может сопровождаться созданием или уничтожением ссылок.
Все методы сборки мусора, так или иначе, сводятся к поддержанию базы Данных о том, какие объекты на кого ссылаются. Использование такой техники возможно практически только в интерпретируемых языках, таких, как Java, Smalltalk или Lisp, где с каждой операцией можно ассоциировать неограниченно большое количество действий.