Список - кінцева послідовність, що складається з нуля або більше атомівабо Списків.
Розглянемо Список L = (a: N, b, c: (d: N), e: L), N = (f: (), g: (h: L,j: N)) а відповідною діаграмою для нього буде

Існує багато способів для подання облікових структур в пам'ятімашини. Зазвичай всі вони є варіаціями на одну й ту ж основну тему,згідно з якою для представлення спільних лісів дерев використовуютьсябінарні дерева: одне поле, скажімо RLINK, використовується для вказівки нанаступний елемент Списку, а інше поле DLINK можна використовувати длявказівки на перший елемент під-Списку.
Тоді Список можна представити у вигляді:

Але ця проста ідея не цілком придатна для найбільш часто зустрічаютьсядодатків, що включають обробку Списків.
З цієї причини верхня схема звичайно замінюється на іншу, але теперкожен Список починається з голови Списку. Кожен список міститьдодатковий вузол, званий головою Списку.

На практиці введення цих головних вузлів не призводить до реальної втратипам'яті, оскільки виявляється чимало застосувань для них. Наприклад, можназнадобитися для лічильника посилань, або покажчика на правий кінець Списку,або для літерного імені, або для робочого поля, яке виявляєтьсякорисним в алгоритмах проходження дерева, і т. д.
По суті, Список - не що інше, як лінійний список, елементи якогоможуть містити покажчики на інші Списки. Найбільш поширенимиопераціями, які ми захочемо виконувати над списками, є звичайніоперації, необхідні і для лінійних списків (створення, руйнування,включення, виключення, розщеплення, конкатенація), і ще деякідодаткові операції, які цікаві, перш за все для деревовиднихструктур (копіювання, проходження, введення та виведення вкладеної інформації).
Але оскільки загальні Списки можуть рости і вмирати під час роботи програмиабсолютно непередбачуваним чином, часто дуже важко сказати точно,коли той чи інший вузол стає непотрібним. Отже, проблемаобслуговування списку вільного простору представляється значнобільш важкою при роботі зі списками.

Уявімо собі, що ми розробляємо універсальну систему для обробки
Списків, яка буде використовуватись сотнями інших програмістів. Дляобслуговування списку вільного простору пропонується два основнихметоду: лічильники посилань і збір сміття. У методі лічильників використовуєтьсяспеціальне поле в кожному вузлі, в якому враховується, скільки стрілоквказує на цей вузол. За таким лічильником досить легко стежити під часроботи програми, і кожного разу, коли лічильник скидається в нуль, данийвузол стає вільним. Метод збору сміття використовує в кожному вузліспеціальне поле розміром в один біт, яке називають "бітом маркування"або просто "маркером". У цьому випадку ідея полягає в тому, що майже всіалгоритми не повертають вузли в список вільної пам'яті і програмабезтурботно працює до тих пір, поки не вичерпається весь цей список, і станутьалгоритм "збирання сміття", використовуючи біти маркування, повертає у вільнупам'ять всі вузли, які в даний момент програмі недоступні, після чогопрограма продовжує працювати.
Ні один з цих методів не можна вважати цілком задовільним.
Принциповий недолік методу лічильників полягає в тому, що він не завждиповертає в список вільної пам'яті ті вузли, які фактично євільними. Він добре працює з частково перекриваються списками. Крімтого метод лічильників посилань забирає цілком відчутне простір в пам'яті
(щоправда, іноді це простір, так чи інакше, залишається вільним черезрозміру машинного слова).
Крім неприємної втрати одного біта в кожному вузлі, труднощі методу зборусміття полягає в тому, що він вкрай повільно працює, коли завантаженняпам'яті майже досягає межі; в таких випадках кількість вільних комірок,отриманих за допомогою процесу збору, не окупає витрачених на це зусиль.
Ті програми, яким не вистачає пам'яті (а це відбувається з багатьма неналагодженими програмами!), часто марно витрачають багато часу,Багато разів і майже безплідно викликаючи збирач сміття безпосередньо передтим, як остаточно вичерпати пам'ять. Цю проблему можна частково вирішити,дозволивши програмісту вказувати число k, і якщо на етапі збору сміттязнайдено не більше k вільних вузлів, то робота програми припиняється. Щеодна проблема пов'язана з труднощами, які виникають іноді привизначенні, які Списки на даному етапі не є сміттям; якщопрограміст користується якимись нестандартними прийомами або зберігає якусьабо вказівний інформацію в незвичайномумісці, то велика ймовірність неправильної роботи збирача сміття. Деякінайбільш містичні випадки в історії налагодження пов'язані з тим, що під часвиконання програм, до цього неодноразово працювали, раптом у несподіванийможе включався збір сміття. Збір сміття вимагає також, щоб програмістивесь час зберігали правильну інформацію у всіх полях вказівних, хочаіноді зручно у полях, до яких програма ніколи не звертається залишитибезглузду інформацію. Можна також відзначити, що збір сміття незручнийдля роботи в "реальному режимі", оскільки, навіть якщо збирач сміттявключається нечасто, він вимагає в цих випадках багато машинного часу.
Хоча збір сміття вимагає одного біта маркування для кожного вузла, можназберігати окрему таблицю всіх бітів маркування, скомпонованих разом, віншої області пам'яті, встановивши відповідність між адресою вузла та йогобітом маркування. Алгоритми збору сміття цікаві з кількох причин.
У першу чергу такі алгоритми корисні в інших ситуаціях, коли ми хочемо відзначити всі вузли, на які прямо чи опосередковано посилається даний вузол.
(Можна, наприклад, знайти всі підпрограми, до яких прямо або побічнозвертається деяка підпрограма.)

Збір сміття зазвичай розпадається на дві фази. Ми припускаємо, щоспочатку біти маркування у всіх вузлах дорівнюють нулю (або ми всі їхвстановлюємо в нуль). Тепер під час першої фази відзначаються всі вузли, нещо є сміттям, відправляючись від вузлів, які безпосередньо доступніз головної програми. У другій фазі здійснюється послідовний прохідпо всій області пулу і всі невідмічені вузли заносяться до спискувільного простору.
Найбільш цікава особливість збору сміття полягає в тому, що під часроботи цього алгоритму в нашому розпорядженні залишається дуже обмеженийобсяг вільної пам'яті, яку можна використовувати для управлінняалгоритмом маркування.
Наступний алгоритм маркування відноситься, напевно, до найбільш очевидним.

Алгоритм А. (Маркіровка.) Нехай вся пам'ять, що використовується для зберігання
Списків, складається з вузлів NODE (1), NODE (2 ),... ..., NODE (М), іприпустимо, що ці слова є або "атомами", або містять два полязв'язку ALINK і BLINK. Припустимо, що спочатку всі вузлинемарковані. Призначення цього алгоритму полягає в тому, щоб відзначитивсі вузли, які можна досягти по ланцюжку покажчиків ALINK і (або) BLINK внеатомарних вузлах, відправляючись від безлічі "безпосередньо доступних"вузлів.

A1 [Початкова установка.] Позначити всі "безпосередньо доступні" вузли, тобто вузли, покажчики на які знаходяться у фіксованих осередках у головній програмі і які служать відправним пунктом для доступу до всієї пам'яті. Встановити К (1.
А2. [Чи слід за NODE (К) інший вузол?] Встановити К (До 1. Якщо NODE (K) - атом або немаркований вузол, то перейти до кроку А3. В іншому випадку, якщо вузол NODE (ALINK (K)) не вибрано, то відзначити його і, якщо він не атом, встановити К1 (min (K1, ALINK (K)). Так само, якщо вузол NODE (BLINK (K)) не вибрано, то відзначити його і, якщо він не атом, встановити

K1 (min (K1, BLINK (K)).
A3. [Кінець?] Встановити K (K1. Якщо K (M, то повернутися до кроку А2, в іншому випадку алгоритм завершено.

Можливий кілька кращий варіант, що передбачає використання стекафіксованого розміру.

Алгоритм B. (Маркіровка.) У цьому алгоритмі використовується таблиця,містить Н осередків STACK [0], STACK [1I, ... ..., STACK [H-1], івиходить той же результат, що і в алгоритмі А.

У цьому алгоритмі дію "занести Х в стек" означає наступне:
"Встановити T ((T + l) mod H і STACK [T] (X. Якщо Т = В, то встановити У ((У +1)mod Н і К1 (min (Kl, STACK [В]) ". (Зауважимо, що Т вказує на поточну
"вершину" стека, а В вказує на одну позицію нижче поточного "низу"; STACKпрацює, по суті, як грудня, з обмеженим входом.)

B1. [Початкова установка.] Встановити Т (Н-1, В (Н-1, Kl (М 1. Позначити всі безпосередньо доступні вузли і послідовно занести їх адреси в стек (за допомогою тільки що описаного дії). < p> B2. [Стек порожній?] Якщо Т = У, перейти до B5.

BЗ. [Взяти з стека верхній елемент.] Встановити К (STACK [Т],

T ((Tl) mod H.
B4. [Досліджувати зв'язку.] Якщо вузол NODE (K) - атом, то веріуться

До B2. В іншому випадку, якщо NODЕ (АL1NK (К)) не відзначений, то відзначити його і занести ALINK (К) в стек. Аналогічно, якщо NODE (BLINK (К)) не відзначений, то відзначити його і занести REF (К) в стек. Назад до B2.
B5. [Прочесати.] Якщо K1> М, то алгоритм завершено. (Змінна К1 представляє найменший адресу, звідки є можливість знову вийти на вузол, який варто відзначити.) В іншому випадку, якщо NODE (KI) нe відзначено, збільшити К1 на 1 і повторити цей крок. Якщо NODE (К1) вибрано, то встановити К (К1, збільшити К1 на 1 і перейти до B4.
Цей алгоритм можна поліпшити, якщо не заносити в стек X, коли NODE (X)
- Атом.
Алгоритм B фактично стає алгоритмом А, коли Н = 1, і очевидно,ефективність його плавно зростає із збільшенням Н. На жаль, алгоритм
B не піддається точному аналізу з тих же причин, що і алгоритм А, і мине в змозі вказати, за будь-Н цей метод буде досить швидким. Уяк правдоподібного, але не дуже надійного можна назвати значення Н =
50, при якому алгоритм B застосуємо для збору сміття в більшості випадків.
В алгоритмі В використовується стек, розташований в послідовних клітинкахпам'яті, які розташовані в пам'яті непослідовно. Цей факт наводитьна думку, що в алгоритмі ми могли б організувати стек, якимось чиномрозкидавши його з тієї ж самої області пам'яті »в якій збирається сміття.
Це неважко зробити, якщо надати програмі збору сміття трохибільше місця, щоб вона могла "зітхнути вільніше".

Будемо вважати, наприклад, що всі Списки представлені, за тим лишевинятком, що поле RЕF в кожному головному вузлі використовується для зборусміття, а не для лічильника посилань. Тоді ми можемо переробити алгоритморганізувавши стек в полях REF головних вузлів.

Алгоритм D (Маркування). Нехай дано множину вузлів, які мають наступні поля

MARK (однорозрядних поле, спочатку нульове в кожному вузлі),

ATOM (ще одне однорозрядних поле),

ALINK (вказівний поле),

BLINK (вказівний поле),

Коли ATOM = 0, поля ALINK і BLINK можуть містити (або покажчик наінший вузол того ж формату; коли ATOM = 1, вміст полів ALINK і BLINKнесуттєво для даного алгоритму.
Якщо задано вказівник Р0, то цей алгоритм встановлює 1 в полі MARK ввузлі NODE (Р0) і у всіх інших вузлах, до яких можна добратися поланцюжку покажчиків ALINK і BLINK і в яких ATOM = MARK = 0. В алгоритмівикористовуються три вказівні змінні, Т, Q і Р, і зв'язки при виконанніалгоритму можуть бути тимчасово змінені, але так, що після завершенняалгоритму у всіх полях ATOM, ALINK і BLINK поновлюються їх колишнізначення.

D1. [Початкова установка.] Встановити Т ((, Р (Р0. (Далі в цьому алгоритмі мінлива Т буде використовуватися у двох значеннях: якщо Т ((, то вона вказує на вершину того, що, по суті, є стеком, а вузол, на який вказує Т, колись містив зв'язок, що дорівнює Р, замість

"штучної" стекові зв'язку, що знаходиться тепер у NODE (Т).)
D2. [Відзначити.] Встановити MARK (Р) (1.
Dз, [Атом?] Якщо ATOM (Р) = 1, то перейти до Е6.
D4. [Вниз по ALINK.] Встановити Q (ALINK (Р). Якщо Q ((і MARK (Q) = 0, товстановити ATOM (Р) (1, ALINK (Р) (Т, Т (Р, P (Q і перейти до D2. (Тепер поля
ATOM і ALINK на час змінені і, отже, досить радикальнозмінилася облікова структура в деяких зазначених вузлах. Але за крок D6все буде відновлено.)
D5. [Вниз по BLINK.) Встановити Q (BLINK (Р). Якщо Q ((і MARK (Q) = 0, товстановити BLINK (Р) (Т, Т (Р, Р (Q і перейти до D2.
D6. [На початок.] (В цьому кроці усуваються зміни зв'язків, зроблені в кроках

D4 або D5; значення АТОМ (Т) говорить про те, яку з зв'язків ALINK (Т) або BLINK (Т) слід відновити. ) Якщо Т = (, алгоритм завершено. В іншому випадку встановити Q (Т. Якщо АТОМ (Q) = 1, то встановити ATOM

(Q) (0, Т (ALINK (Q), ALINK ( Q) (P, P (Q і повернутися до D5. Якщо ATOM (Q) = 0, то встановити Т (BLINK (Q), BLINК (Q) (Р, Р (Q і повернутися до D6.
Блок - схема алгоритму D показана на малюнку,

Після
Після

ALINK
BLINK

D1.Нач. D2. D3. D4.
Вниз по D5. Вниз по D6. На початок установка Відзначити Атом? ALINK
Вже BLINK Вже

Так відзначено відзначений

Звернемо увагу на те, що в кроках D4 і D5 штучно змінюєтьсяоблікова структура. Коли відбувається повернення до попереднього стану, поле
ATOM говорить про те, які з зв'язків ALINK і BLINK містять штучніадреси. "Вкладення", показані в нижній частині малюнка служать ілюстрацієютого, що в алгоритмі кожен неатомарний вузол відвідується три рази
Доказ правильності алгоритму D можна побудувати, базуючись наіндукції по кількості вузлів, які підлягають маркуванню. Одночаснодоводиться, що в кінці алгоритму Р = Р0. Алгоритм D буде працюватишвидше, якщо виключити крок Dз, а замість нього виконати перевірки "ATOM (Q)
= 1 "та відповідні дії в кроках D4 і D5, а також перевірку" ATOM
(Р0) = 1 "за крок D1.

Ідею, на якій побудований алгоритм D, можна застосувати не тільки длязбору сміття, але і в інших завданнях.
Час виконання найкращих з відомих програм збору сміття виражається,по суті, формулою c1N + c2M, де c1 і c2 - константи, N-кількістьмаркується вузлів, а М - загальна кількість вузлів в пам'яті. Таким чином, М
- N - кількість знайдених вільних вузлів, і час, який витрачається наповернення одного такого вузла в вільну пам'ять, становить (c1N + c2М)/(М-
N). Нехай N = (М; тоді формула перетворюється до вигляду (c1 (+ c2)/(l - ().
Отже, якщо (= 3/4, тобтопам'ять заповнена на три чверті, то буде потрібно 3c1 + 4c2 одиниць часу,щоб повернути у вільну пам'ять один вузол; якщо (= 1/4

, то відповідна величина складає лише
1/3c1 + 1/4c2.
Якщо збір сміття не використовується, то витрата часу на один повертаєтьсявузол дорівнює константі c3 і, поза всякими сумнівами, ставлення c3/c1 буде дужевелике. Звідси ми можемо бачити, до якої міри неефективний збір сміття,коли пам'ять стає повною, і відповідно, наскільки він ефективний,коли вимоги до пам'яті невеликі.

Можна поєднати збір сміття з деякими іншими методами повернення осередківу вільну пам'ять; ці принципи не виключають один одного, і в деякихсистемах використовуються як лічильник посилань, так і схеми збору сміття, а крімтого, програміст може явно звільняти вузли.