Ця стаття присвячена старту курсу ["Алгоритми для розробників"] (https://otus.ru/lessons/algorithm/?utm_source=partners&utm_medium=cpm&utm_campaign=algo&utm_term=evileg&utm_content=dod#event Висловлюю подяку за підтримку ресурсу даною компанією.
Давайте вивчимо, які операції можна виконувати зі зв'язаним списком.
Два важливі моменти, які потрібно пам'ятати:
- head вказує на перший вузол пов'язаного списку
- next покажчик останнього вузла дорівнює nullptr , тому, якщо наступний з поточного вузла дорівнює nullptr , ми досягли кінця зв'язаного списку.
У всіх прикладах ми припускатимемо, що пов'язаний список має три вузли 1 ---> 2 ---> 3 зі структурою вузла, як показано нижче:
struct node
{
int data;
struct node* next {nullptr};
};
Як пройти по зв'язаному списку
Відображення вмісту пов'язаного списку дуже просто. Ми продовжуємо переміщати тимчасовий вузол до наступного та відображаємо його вміст.
Коли temp дорівнює NULL , ми знаємо, що досягли кінця зв'язаного списку, тому ми виходимо із циклу while .
struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
std::cout << temp->data << " ---> ";
temp = temp->next;
}
Виведення цієї програми буде:
List elements are - 1 ---> 2 ---> 3 --->
Як додати елементи до пов'язаного списку
Ви можете додавати елементи на початок, середину або кінець пов'язаного списку.
Додати до початку
- Виділіть пам'ять для нового вузла
- Збережіть дані
- Змініть новий next вузол, щоб він вказував на head
- Змініть head , щоб вказати на нещодавно створений вузол
struct node* newNode = new node(); newNode->data = value; newNode->next = head; head = newNode;
Додати в кінець
- Виділіть пам'ять для нового вузла
- Збережіть дані
- Зробіть перехід до останнього вузла
- Змініть next з останнього вузла на нещодавно створений вузол
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;
struct node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
Додати в середину
- Виділіть пам'ять та збережіть дані для нового вузла
- Перехід до вузла безпосередньо перед необхідною позицією нового вузла
- Змініть next покажчики, щоб додати новий вузол між ними
struct node *newNode = new node();
newNode->data = value;
struct node *temp = head;
for (int i=2; i < position; i++)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
Як видалити вузол зі зв'язаного списку
Ви можете видалити або з початку, з кінця або з певної позиції.
Видалити з початку
- Налаштуйте вказівник head на другий вузол
head = head->next;
Видалити з кінця
- Перейти до другого останнього елементу
- Змінити next покажчик на nullptr
struct node* temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
temp->next = nullptr;
Видалити з середини
- Перехід до елемента до елемента, що видаляється
- Змінити next покажчики, щоб виключити вузол з ланцюжка
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
temp->next = temp->next->next;
Повна програма для операцій зі зв'язаним списком
Ось повна програма для всіх операцій із пов'язаним списком, який ми вивчили. Багато крайніх випадків були опущені, щоб зробити програму короткою.
Ми пропонуємо вам просто поглянути на програму та спробувати її реалізувати самостійно.
Також зверніть увагу на те, як ми передаємо адресу head як struct node headRef у функції insertAtFront та deleteFromFront. Ці дві функції змінюють положення вказівника head , тому нам потрібно передати адресу вказівника head** та змінити його значення всередині функції.
#include <iostream>
struct node
{
int data;
struct node* next {nullptr};
};
void display(struct node* head)
{
struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
std::cout << temp->data << " ---> ";
temp = temp->next;
}
}
void insertAtMiddle(struct node *head, int position, int value)
{
struct node *newNode = new node();
newNode->data = value;
struct node *temp = head;
for (int i=2; i < position; i++)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;
}
void insertAtFront(struct node** headRef, int value)
{
struct node* head = *headRef;
struct node* newNode = new node();
newNode->data = value;
newNode->next = head;
head = newNode;
*headRef = head;
}
void insertAtEnd(struct node* head, int value)
{
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;
struct node *temp = head;
while (temp->next != nullptr)
{
temp = temp->next;
}
temp->next = newNode;
}
void deleteFromFront(struct node** headRef)
{
struct node* head = *headRef;
head = head->next;
*headRef = head;
}
void deleteFromEnd(struct node* head)
{
struct node* temp = head;
while (temp->next->next != nullptr)
{
temp = temp->next;
}
temp->next = nullptr;
}
void deleteFromMiddle(struct node* head, int position)
{
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
if (temp->next != nullptr)
{
temp = temp->next;
}
}
temp->next = temp->next->next;
}
int main()
{
/* Initialize nodes */
struct node *head;
struct node *one = new node();
struct node *two = new node();
struct node *three = new node();
/* Assign data values */
one->data = 1;
two->data = 2;
three->data = 3;
/* Connect nodes */
one->next = two;
two->next = three;
three->next = nullptr;
/* Save address of first node in head */
head = one;
display(head); // 1 ---> 2 ---> 3 --->
insertAtFront(&head, 4);
display(head); // 4 ---> 1 ---> 2 ---> 3 --->
deleteFromFront(&head);
display(head); // 1 ---> 2 ---> 3 --->
insertAtEnd(head, 5);
display(head); // 1 ---> 2 ---> 3 ---> 5 --->
deleteFromEnd(head);
display(head); // 1 ---> 2 ---> 3 --->
int position = 3;
insertAtMiddle(head, position, 10);
display(head); // 1 ---> 2 ---> 10 ---> 3 --->
deleteFromMiddle(head, position);
display(head); // 1 ---> 2 ---> 3 --->
}
Виведення програми буде наступним
List elements are - 1 ---> 2 ---> 3 ---> List elements are - 4 ---> 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 ---> 5 ---> List elements are - 1 ---> 2 ---> 3 ---> List elements are - 1 ---> 2 ---> 10 ---> 3 ---> List elements are - 1 ---> 2 ---> 3 --->
Висновок
Також ви можете вивчити більш поглиблено алгоритми на курсі ["Алгоритми для розробників"]. зможете більш поглиблено вивчити як базові алгоритми, і складніші.
Курс пропонує наступне:
- Розуміння принципів роботи різноманітних алгоритмів, структур даних
- Вміння використовувати готові алгоритми та структури даних та створювати свої під поставлене завдання
- Володіння технікою обчислення складності алгоритмів
- Освоєння просунутих структур даних: хеш-таблиць, графів, дерев пошуку та багатьох інших
- Вміння вирішувати алгебраїчні задачі та завдання динамічного програмування
При цьому на даному курсі пропонується вивчення алгоритмів та структур даних з використанням мов програмування як Java, C++, Python.
Ви можете перевірити свої сили в тестуванні , щоб зрозуміти, чи готові до проходження даного курсу Вам додатково.
