Привет! Вы новичок в мире программирования и интересуетесь структурами данных? Если да, то вы попали по адресу! В этой статье блога мы собираемся углубиться в одну из фундаментальных структур данных в C++: связанный список. Не волнуйтесь, если вы еще не знакомы с этим жаргоном — мы разобьем его на простые термины и попутно предоставим множество примеров кода. Итак, начнём!
Что такое связанный список?
Представьте себе цепочку взаимосвязанных узлов, где каждый узел содержит фрагмент данных и ссылку на следующий узел в цепочке. По сути, это связанный список. В отличие от массивов, связанные списки имеют динамическую структуру и могут увеличиваться или уменьшаться по мере необходимости. В C++ связанный список реализуется с помощью указателей, которые представляют собой переменные, хранящие адреса памяти.
Создание связанного списка.
Чтобы создать связанный список, нам сначала нужно определить структуру узлов, которая представляет каждый элемент списка. Вот пример:
struct Node {
int data;
Node* next;
};
В этой структуре у нас есть целочисленная переменная с именем data
для хранения значения и указатель с именем next
, указывающий на следующий узел в списке.
Обход связанного списка.
Чтобы получить доступ к элементам связанного списка или манипулировать ими, нам необходимо пройти по нему. Обход просто означает перемещение от одного узла к другому, пока мы не достигнем нужного узла или конца списка. Вот пример того, как перемещаться по связанному списку:
void traverseLinkedList(Node* head) {
Node* currentNode = head;
while (currentNode != nullptr) {
// Access the data in the current node
cout << currentNode->data << " ";
// Move to the next node
currentNode = currentNode->next;
}
}
Вставка элементов в связанный список.
Добавление новых элементов в связанный список включает в себя создание нового узла и обновление необходимых указателей. Давайте рассмотрим пример вставки узла в начало списка:
void insertAtBeginning(Node*& head, int newData) {
Node* newNode = new Node;
newNode->data = newData;
newNode->next = head;
head = newNode;
}
Удаление элементов из связанного списка.
Как и вставка, удаление узла из связанного списка требует обновления указателей, чтобы обойти удаляемый узел. Вот пример удаления первого появления определенного значения в списке:
void deleteNode(Node*& head, int key) {
Node* currentNode = head;
Node* previousNode = nullptr;
while (currentNode != nullptr && currentNode->data != key) {
previousNode = currentNode;
currentNode = currentNode->next;
}
if (currentNode == nullptr) {
// Key not found
return;
}
if (previousNode == nullptr) {
// Node to delete is the head
head = currentNode->next;
} else {
previousNode->next = currentNode->next;
}
delete currentNode;
}
Поздравляем! Теперь вы изучили основы связанных списков в C++. Мы рассмотрели создание связанного списка, его обход, вставку элементов и удаление узлов. Связанные списки — это мощная структура данных, которую можно использовать в различных сценариях программирования. Мы рекомендуем вам продолжить изучение и поэкспериментировать с различными операциями над связанными списками. Приятного кодирования!