Пов’язані списки
proceduredeleteNext(t : integer);beginnext[t] := next[next[t]];end;
procedureinsertAfter(v: integer; t : integer);beginx := x+1; key[x]: = v; next[x]: = netx[t]; next [t]: = xend;
Покажчикx замінює нам процедуру виділення динамічної пам'ятіnew: він вказує на наступну позицію, що не використовується в масиві.
На Error: Reference source not found показано, як список з нашого прикладу може бути представлений у вигляді паралельних масивів, і як це уявлення пов'язане з тим графічним уявленням, яке ми досі використовували. Масиви key і next показані зліва в тому вигляді, в якому вони з'явилися б, якби ми вставили в спочатку порожній список SLAIT, де S, L і A вставлені після head, I після L, і T після S. Позиція 0 є початком списку а позиція 1 його кінцем (це встановлюється при ініціалізації списку). Тому next [0] = 4 - перший вузол списку зі значенням key [4] (A); Оскільки next[4]=3, то наступним (другим) елементом буде key[3] (L), тощо. На другій ліворуч діаграмі індекси масиву замінені лініями, замість написання номера наступного елемента списку ми просто креслимо лінію, що з'єднує його з наступним елементом. На третій діаграмі ми “випрямляємо” список, а потім в останній, правій діаграмі ми просто використовуємо звичайне графічне уявлення пов'язаного списку.
Реалізація пов'язаного списку за допомогою масивів
Повертаючись до аналогії з пам'яттю комп'ютера, побудуємо аналогію для динамічного виділення та звільнення пам'яті. Операційна система поставлена таке становище, що вузли зберігаються у тому масиві (пам'ять – масив), як і посилання. Отже, ми хочемо реалізувати вбудовані процедури newіdispose, виходячи з того, щоєдине місце для зберігання вузлів та посилань – це наші масиви.
Припустимо, що потрібно видалити вузол A з прикладу на Error: Reference source not found, та був звільнити зайняту ним пам'ять. Переставити всі покажчики у списку так, щоб вузол більше не був частиною списку – це одне, але що нам робити з простором, що використовується цим вузлом? І як знайти місце під новий вузол, коли ми викликаємо процедуруnew? Для вирішення проблеми, ми можемо використовувати другий зв'язаний список для зберігання інформації про простір, що не використовується. Ми називатимемо йогосписок невикористовуваних елементів. Тепер, коли мивидаляємоелемент зі списку, ми звільняємо простір, що використовується, додаючи його до списку невикористовуваних елементів, а коли ми створюємоновийвузол, - отримуємо місце під нього за допомогою видалення його з списку списку елементів, що не використовуються. Таким чином, йдеться про кілька списків на одному масиві.
Простий приклад із двома списками (але без списку елементів, що не використовуються) зображений на Error: Reference source not found. У цьому прикладі визначено два вузли-заголовки списківhd1 = 0іhd2 = 6, але обидва списки мають один і той же кінцевий вузолz. (Для створення декількох списків, процедура ініціалізаціїlistInitializeмає бути змінена так, щоб вона могла керувати більш ніж одним заголовком списку.) Тепер,next[0] = 4, тому перший елемент нашого списку - цеkey [4] (O). Так, якnext[6]=7, то перший елемент другого списку -key[7] (T),і так далі. Наступна діаграма показує наші списки без використання паралельного масивуnext, замінюючи його лініями, що з'єднують його вузли. На третій показані ті самі два списки, але вже «розгорнуті». Зрештою на останній діаграмі зображеносписки у звичній нам графічній формі, як у Error: Reference source not found.
Два списки, що містяться в одному масиві
Все описане раніше призначене розуміння того, як система керує виділенням ресурсів. Насправді проблема, з якою має справу система, складніша. Справа в тому, що вузли не повинні бути одного розміру. Деякі системи звільняють користувача від необхідності прямого викликуdisposeдля звільнення пам'яті за допомогою алгоритмівзбору сміттядля видалення «втрачених» вузлів. Якщо управління пам'яттю надається середовищем програмування, як у Паскалі, зазвичай немає причин створювати свій власний диспетчер пам'яті.