linked list data structure c with illustration
Детальне вивчення зв’язаного списку на C ++.
Зв’язаний список - це лінійна динамічна структура даних для зберігання елементів даних. Ми вже бачили масиви в наших попередніх темах про базовий С ++. Ми також знаємо, що масиви - це лінійна структура даних, яка зберігає елементи даних у суміжних місцях.
На відміну від масивів, зв’язаний список не зберігає елементи даних у суміжних місцях пам'яті.
Зв'язаний список складається з елементів, що називаються 'Вузли', які містять дві частини. Перша частина зберігає фактичні дані, а друга частина має вказівник, який вказує на наступний вузол. Цю структуру зазвичай називають «єдинозв’язаним списком».
=> Ознайомтеся з найкращими навчальними посібниками з C ++ тут.
Що ви дізнаєтесь:
Зв’язаний список на C ++
Ми подивимось на окремо зв’язаний список детально в цьому посібнику.
На наступній схемі показана структура списку, що зв’язаний по одній.
Як показано вище, перший вузол зв’язаного списку називається “head”, тоді як останній вузол називається “Tail”. Як бачимо, останній вузол зв’язаного списку матиме наступний вказівник як нуль, оскільки на ньому не буде вказано жодної адреси пам’яті.
Оскільки кожен вузол має вказівник на наступний вузол, елементи даних у зв’язаному списку не потрібно зберігати у суміжних місцях. Вузли можуть бути розкидані в пам'яті. Ми можемо отримати доступ до вузлів у будь-який час, оскільки кожен вузол матиме адресу наступного вузла.
Ми можемо додавати елементи даних до пов’язаного списку, а також легко видаляти елементи зі списку. Таким чином, можна динамічно збільшувати або зменшувати зв’язаний список. У зв’язаному списку немає верхньої межі кількості елементів даних. Отже, поки доступна пам’ять, ми можемо додавати стільки елементів даних до пов’язаного списку.
Окрім простої вставки та видалення, зв’язаний список також не витрачає місця в пам'яті, оскільки нам не потрібно заздалегідь вказувати, скільки елементів нам потрібно у зв’язаному списку. Єдиний простір, який займає зв’язаний список, призначений для зберігання вказівника на наступний вузол, який додає трохи накладних витрат.
Далі ми обговоримо різні операції, які можна виконати у зв’язаному списку.
Операції
Як і інші структури даних, ми також можемо виконувати різні операції для пов'язаного списку. Але на відміну від масивів, в яких ми можемо отримати доступ до елемента, використовуючи підрядковий знак безпосередньо, навіть якщо він знаходиться десь посередині, ми не можемо зробити той самий випадковий доступ зі зв'язаним списком.
Для того, щоб отримати доступ до будь-якого вузла, нам потрібно перейти зв'язаний список з самого початку, і лише тоді ми можемо отримати доступ до потрібного вузла. Отже, випадковий доступ до даних із пов'язаного списку виявляється дорогим.
Ми можемо виконувати різні операції у зв’язаному списку, як показано нижче:
# 1) Вставка
Операція вставки пов'язаного списку додає елемент до пов'язаного списку. Хоча це може звучати просто, враховуючи структуру пов’язаного списку, ми знаємо, що кожного разу, коли елемент даних додається до пов’язаного списку, нам потрібно змінити наступні вказівники попереднього та наступного вузлів нового елемента, який ми вставили.
Друге, що нам слід врахувати, це місце, куди слід додати новий елемент даних.
У зв’язаному списку є три позиції, куди можна додати елемент даних.
# 1) На початку зв’язаного списку
Зв’язаний список наведено нижче 2-> 4-> 6-> 8-> 10. Якщо ми хочемо додати новий вузол 1 як перший вузол списку, тоді головка, що вказує на вузол 2, тепер буде вказувати на 1, а наступний вказівник вузла 1 матиме адресу пам'яті вузла 2, як показано нижче малюнок.
Таким чином, новий пов'язаний список стає 1-> 2-> 4-> 6-> 8-> 10.
# 2) Після заданого Вузла
Тут дається вузол, і ми повинні додати новий вузол після даного вузла. У наведеному нижче списку a-> b-> c-> d -> e, якщо ми хочемо додати вузол f після вузла c, тоді зв’язаний список буде виглядати наступним чином:
Таким чином, на наведеній вище схемі ми перевіряємо, чи присутній даний вузол. Якщо він присутній, ми створюємо новий вузол f. Потім ми вказуємо наступний покажчик вузла c, щоб вказати на новий вузол f. Наступний покажчик вузла f тепер вказує на вузол d.
# 3) У кінці пов'язаного списку
У третьому випадку ми додаємо новий вузол в кінці пов'язаного списку. Припустимо, у нас однаковий пов’язаний список a-> b-> c-> d-> e, і нам потрібно додати вузол f у кінець списку. Після додавання вузла зв’язаний список буде виглядати, як показано нижче.
Таким чином ми створюємо новий вузол f. Потім вказівник хвоста, що вказує на нуль, вказується на f, а наступний вказівник вузла f - на нуль. Ми застосували всі три типи вставних функцій у нижченаведеній програмі C ++.
У C ++ ми можемо оголосити пов'язаний список як структуру або як клас. Оголошення пов'язаного списку як структури є традиційним оголошенням у стилі С. Зв’язаний список як клас використовується в сучасній C ++, переважно під час використання стандартної бібліотеки шаблонів.
У наступній програмі ми використовували структуру для оголошення та створення пов'язаного списку. Його членами будуть дані та вказівник на наступний елемент.
#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout Вихід:
Остаточний пов'язаний список:
30–> 20–> 50–> 10–> 40–> нуль
Далі ми реалізуємо операцію вставки зв’язаного списку в Java. Мовою Java пов'язаний список реалізований як клас. Програма нижче за логікою подібна до програми C ++, єдина відмінність полягає в тому, що ми використовуємо клас для пов'язаного списку.
class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println('
Final linked list: '); lList. displayList (); } } Вихід:
Остаточний пов'язаний список:
зберігання об'єктів у масиві java
10–> 20–> 30–> 40–> 50–> нуль
В обох програмах вище, як C ++, так і в Java, ми маємо окремі функції для додавання вузла перед списком, кінцем списку та між списками, заданими у вузлі. Врешті-решт ми друкуємо вміст списку, створеного за допомогою всіх трьох методів.
# 2) Видалення
Як і вставка, видалення вузла зі зв’язаного списку також включає різні позиції, з яких вузол можна видалити. Ми можемо видалити перший вузол, останній вузол або випадковий k-й вузол зі зв’язаного списку. Після видалення нам потрібно правильно налаштувати наступний покажчик та інші покажчики у зв’язаному списку, щоб зберегти зв’язаний список недоторканим.
У наступній реалізації С ++ ми навели два методи видалення, тобто видалення першого вузла у списку та видалення останнього вузла у списку. Спочатку ми створюємо список, додаючи вузли до голови. Потім ми відображаємо вміст списку після вставки та кожного видалення.
#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created ' Вихід:
Створений зв’язаний список
10–> 8–> 6–> 4–> 2–
> НУЛЬ
Зв’язаний список після видалення головного вузла
8–> 6–> 4–> 2–
> НУЛЬ
Зв’язаний список після видалення останнього вузла
8–> 6–> 4–> НУЛЬ
Далі - реалізація Java для видалення вузлів зі зв’язаного списку. Логіка реалізації така ж, як і в програмі С ++. Єдина відмінність полягає в тому, що пов'язаний список оголошується як клас.
class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } } Вихід:
Створений пов’язаний список:
9–> 7–> 5–> 3–> 1–
> нуль
Зв’язаний список після видалення головного вузла:
7–> 5–> 3–> 1–
> нуль
Зв’язаний список після видалення останнього вузла:
7–> 5–> 3–> нуль
Підрахувати кількість вузлів
Операцію підрахунку кількості вузлів можна виконати під час обходу пов'язаного списку. У реалізації вище ми вже бачили, що всякий раз, коли нам потрібно вставити / видалити вузол або відобразити вміст зв’язаного списку, нам потрібно обходити зв’язаний список з самого початку.
Зберігання лічильника та збільшення його під час обходу кожного вузла дасть нам підрахунок кількості вузлів у зв’язаному списку. Ми залишимо цю програму для читачів для реалізації.
Масиви та зв’язані списки
Побачивши операції та реалізацію пов’язаного списку, давайте порівняємо, як масиви та пов’язаний список справедливі порівняно між собою.
Масиви Зв’язані списки Масиви мають фіксований розмір Розмір пов’язаного списку динамічний Вставка нового елемента коштує дорого Вставлення / видалення простіше Дозволений доступ Випадковий доступ неможливий Елементи знаходяться поруч Елементи мають суміжне розташування Для наступного вказівника не потрібно зайвого місця Для наступного вказівника потрібно додатковий простір пам'яті
Програми
Оскільки масиви та зв’язані списки використовуються як для зберігання елементів, так і є лінійними структурами даних, обидві ці структури можуть використовуватися подібними способами для більшості програм.
Деякі програми для зв’язаних списків:
- Зв’язаний список можна використовувати для реалізації стеків та черг.
- Зв’язаний список також може бути використаний для реалізації графіків, коли нам потрібно представляти графіки як списки суміжності.
- Математичний поліном може зберігатися як зв’язаний список.
- У разі техніки хешування сегменти, що використовуються для хешування, реалізуються за допомогою пов'язаних списків.
- Кожного разу, коли програма вимагає динамічного розподілу пам’яті, ми можемо використовувати зв’язаний список, оскільки зв’язані списки в цьому випадку працюють ефективніше.
Висновок
Зв’язані списки - це структури даних, які використовуються для лінійного зберігання елементів даних, але несуміжних розташувань. Зв’язаний список - це сукупність вузлів, що містять частину даних та наступний вказівник, що містить адресу пам’яті наступного елемента у списку.
Для останнього елемента списку наступний вказівник має значення NULL, вказуючи тим самим кінець списку. Перший елемент списку називається Head. Зв’язаний список підтримує різні операції, такі як вставка, видалення, обхід тощо. У разі динамічного розподілу пам’яті зв’язані списки мають перевагу над масивами.
Зв’язані списки дорогі, що стосується їх обходу, оскільки ми не можемо отримати випадковий доступ до таких елементів, як масиви. Однак операції вставки-видалення дешевші, якщо порівнювати масиви.
Ми дізналися все про лінійно пов’язані списки в цьому посібнику. Зв’язані списки також можуть бути круговими або подвійними. Ми глибоко ознайомимось із цими списками у наших майбутніх підручниках.
=> Перегляньте тут повну серію навчальних програм C ++.
Рекомендована література
- Структура даних кругового зв’язаного списку на C ++ з ілюстрацією
- Подвійно пов’язана структура даних списку на C ++ з ілюстрацією
- Структура даних черги в C ++ з ілюстрацією
- Структура даних стеку в C ++ з ілюстрацією
- Структура даних черги пріоритетів у C ++ з ілюстрацією
- 15 найкращих безкоштовних інструментів для видобутку даних: найповніший список
- 15 найкращих інструментів ETL у 2021 році (повний оновлений список)
- Вступ до структур даних на C ++