У цьому уроці ви дізнаєтеся про пов'язаний список та його додатки. Ви також дізнаєтесь, як створювати та виконувати різні операції зі зв'язаним списком.
У грі "Полювання за скарбами" ви починаєте з пошуку першої підказки. Коли ви знайдете його, замість того, щоб знайти скарб, ви знайдете розташування наступної підказки, а потім наступної і так далі. Ви продовжуєте слідувати за підказками, доки не дістанетеся до скарбу.
Пов'язаний список схожий на приклад із грою. Це серія пов'язаних «вузлів», що містить «адресу» наступного вузла. Кожен вузол може зберігати точку даних, яка може бути числом, рядком чи будь-яким іншим типом даних.
Представлення зв'язаного списку
Потрібно почати з чогось, тому ми даємо адресою першого вузла спеціальне ім'я, яке називається HEAD. Крім того, останній вузол у зв'язаному списку може бути ідентифікований, тому що його наступна частина вказує на NULL.
Як посилаються на інший вузол?
Давайте подумаємо про те, що містить кожен вузол:
- Елемент даних;
- Адреса іншого вузла.
Ми об'єднуємо елемент даних та посилання на наступний вузол у структуру як:
struct node
{
int data;
struct node *next;
};
Розуміння структури пов'язаного вузла списку є ключем до розуміння.
Кожен структурний вузол має елемент даних та покажчик на інший структурний вузол. Давайте створимо простий пов'язаний список із трьома елементами, щоб зрозуміти, як це працює.
/* Инициализируем узлы */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Выделяем память */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Назначаем значения данных */ one->data = 1; two->data = 2; three->data=3; /* Соединяем узлы */ one->next = two; two->next = three; three->next = NULL; /* Сохраняем адрес первого узла в голове */ head = one;
Якщо ви не зрозуміли жодного з перелічених вище рядків, все, що вам потрібно, це оновити покажчики і структури.
За кілька кроків ми створили простий зв'язаний список з трьома вузлами.
Перевага зв'язкового списку походить від здатності розірвати ланцюг і приєднати до нього. Наприклад, якщо ви хочете помістити елемент 4 між 1 і 2, виконайте такі кроки:
- Створіть новий вузол структури та виділіть для нього пам'ять.
- Додайте його значення даних як 4
- Направте наступний покажчик на вузол структури, що містить 2 як значення даних
- Змініть наступний покажчик «1» на вузол, який ми щойно створили.
Щоб зробити щось схоже в масиві, потрібно було б змістити позиції всіх наступних елементів.
Утиліта пов'язаного списку
Списки є однією з найпопулярніших та найефективніших структур даних, які реалізуються на всіх мовах програмування, таких як C, C++, Python, Java та C#.
Крім того, пов'язані списки – чудовий спосіб дізнатися, як працюють покажчики. Практикуючи роботу зі зв'язаними списками, ви можете підготуватися до вивчення складніших структур даних, таких як графіки та дерева.
