Структура даних “Список”

Дізнайтесь, що таке структура даних "Список", і як вона працює!

Чому нам потрібен список?

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

Список — це лінійна колекція елементів даних, відома як вузли (nodes), що містять дані та вказівник (pointer) на наступний вузол. Порядок елементів не визначається їх фізичним розташуванням у пам'яті, натомість кожен елемент вказує на наступний елемент за допомогою вказівника (pointer). Головний/перший вузол — це вказівник, який вказує на перший вузол або головний (head) вузол у списку. Вказівник останнього вузла завжди має значення NULL або ZERO, що вказує на те, що цей вузол не з'єднаний з наступним вузлом (NODE). Список створюється в області пам'яті Heap, тому ми отримуємо динамічне виділення пам'яті.

Як виглядає список!

Вузол (Node)

Розглядайте вузол як коробку, ми маємо кілька таких коробок, які з'єднані між собою і формують список. Щоб визначити вузол, потрібно вказати два компоненти: дані (data) та вказівник (pointer) на наступний вузол. Дані можуть бути будь-якого типу, що необхідно для збереження інформації, а вказівник використовується для з'єднання вузлів. Вузол міститиме вказівник типу Node, ілюстрація нижче допоможе вам зрозуміти та уявити, як виглядає вузол (Node) в списку.

Вузол (Node) списку

struct Node  
{   
 int data; // частина даних вузла, може бути будь-якого типу  
 Node *next; // частина вказівника вузла, вказує на наступний вузол або NULL  
}

Як створити вузол?

Щоб створити вузол, нам потрібен вказівник (pointer), щоб він вказував на перший вузол списку в області пам'яті Heap. Як видно на малюнку нижче, ми оголосили вказівник типу Node, який вказує на перший вузол (Node). Вузол ініціалізований з даними 10, наразі частина вказівника (next) цього вузла не вказує на інший вузол, оскільки вона є NULL. Це означає, що немає наступного вузла.

int main()  
{  
 Node *p;  
 p = new Node;  
 p-> data = 10;  
 p-> next = 0;  
}

Декілька важливих концепцій!

Тут у нас є два вказівники p та q, у першому рядку коду ми присвоїли p значення q, що означає, що тепер q також вказує на той самий вузол, на який вказує вказівник p.

У другому рядку q присвоюється next вказівника p (q = p-> next), це означає, що тепер вказівник q вказує на вузол, який є наступним після вказівника p.

У третьому рядку p тепер присвоюється next самого себе (p = p-> next), вказівник p вказує на наступний вузол, використовуючи адресу цього вузла.

Логіка вказівників (pointers)

Реалізація списку за допомогою масиву

#include   
using namespace std;   

struct Node {  
 int data;  
 Node* next;  
};  

 Node *first = NULL;  

// функція для створення списку  
void create(int A[], int n) {  
 int i;  
 Node *t, *last;  

 first = new Node;  
 first->data = A[0];  
 first->next = NULL;  
 last = first;  

 for (i = 1; i < n; i++) {  
 t = new Node;  
 t->data = A[i];  
 t->next = NULL;  
 last->next = t;  
 last = t;  
 }  
}  

// функція для відображення списку  
void Display(Node* p) {  
 while (p != NULL) {  
 cout << p->data << " ";   
 p = p->next;  
 }  
}  

int main() {  
 int A[] = {3, 5, 7, 10, 15};  

 create(A, 5);  
 Display(first);  

 return 0;  
}

Існують й інші типи списків, які будуть розглянуті в наступних блогах!

Щасливого навчання!

Перекладено з: Linked List Data Structure