В этом посте представлен обзор некоторых доступных методов реализации связанного списка на языке программирования C++.
Мы знаем, что каждый узел связанного списка содержит одно поле данных и указатель на следующий узел в списке.
|
1 2 3 4 5 6 7 |
// Узел связанного списка class Node { public: int key; // поле данных Node* next; // указатель на следующий узел }; |
Узлы связанного списка размещаются в куче памяти. Мы можем использовать новый оператор в C++ для динамического выделения памяти и delete оператор для освобождения выделенной памяти.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Вспомогательная функция для возврата нового узла связанного списка из кучи Node* newNode(int key) { // выделяем новый узел в куче с помощью оператора new и устанавливаем его данные Node* node = new Node; node->key = key; // устанавливаем указатель `.next` нового узла так, чтобы он указывал на ноль node->next = nullptr; return node; } |
Существует несколько способов построения односвязного списка. Каждый из них подробно описан ниже:
1. Наивный метод
Простым решением было бы выделить память для всех отдельных узлов связанного списка, установить их данные и переставить их указатели, чтобы построить полный список.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> using namespace std; // Узел связанного списка class Node { public: int key; // поле данных Node* next; // указатель на следующий узел }; // Вспомогательная функция для возврата нового узла связанного списка из кучи Node* newNode(int key) { // выделяем новый узел в куче и устанавливаем его данные Node* node = new Node; node->key = key; // `.next` указатель нового узла ни на что не указывает node->next = nullptr; return node; } // Функция для реализации связанного списка, содержащего три узла Node* constructList() { // строим три узла связанного списка Node* first = newNode(1); Node* second = newNode(2); Node* third = newNode(3); // переставляем указатели для построения списка Node* head = first; first->next = second; second->next = third; // возвращаем указатель на первый узел в списке return head; } // Вспомогательная функция для печати связанного списка void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // `head` указывает на первый узел (также известный как головной узел) связанного списка Node *head = constructList(); // распечатать связанный список printList(head); return 0; } |
2. Одна линия
Мы можем записать приведенный выше код в одну строку, передав следующий узел в качестве аргумента функции newNode() функция:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> using namespace std; // Узел связанного списка class Node { public: int key; // поле данных Node* next; // указатель на следующий узел }; // Вспомогательная функция для возврата нового узла связанного списка из кучи Node* newNode(int key, Node* next) { // выделяем новый узел в куче и устанавливаем его данные Node* node = new Node; node->key = key; // устанавливаем указатель `.next` нового узла так, чтобы он указывал на текущий // первый узел списка. node->next = next; return node; } // Функция для реализации связанного списка, содержащего три узла Node* constructList() { Node* head = newNode(1, newNode(2, newNode(3, nullptr))); return head; } // Вспомогательная функция для печати связанного списка void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // `head` указывает на первый узел (также известный как головной узел) связанного списка Node *head = constructList(); // распечатать связанный список printList(head); return 0; } |
3. Общий метод
Оба вышеупомянутых метода непрактичны, когда общее количество узлов в связанном списке увеличивается. Если ключи заданы в каком-либо контейнере, таком как массив, vector или набор, мы можем легко построить связанный список, обходя контейнер, как показано ниже:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <vector> using namespace std; // Узел связанного списка class Node { public: int key; // поле данных Node* next; // указатель на следующий узел }; // Вспомогательная функция для возврата нового узла связанного списка из кучи Node* newNode(int key, Node* next) { // выделяем новый узел в куче и устанавливаем его данные Node* node = new Node; node->key = key; // устанавливаем указатель `.next` нового узла так, чтобы он указывал на текущий // первый узел списка. node->next = next; return node; } // Функция реализации связанного списка из заданного набора ключей Node* constructList(vector<int> const &keys) { Node* head, *node = nullptr; // начинаем с конца массива for (int i = keys.size() - 1; i >= 0; i--) { node = newNode(keys[i], node); head = node; } return head; } // Вспомогательная функция для печати связанного списка void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // клавиши ввода (в обратном порядке) vector<int> keys = { 4, 3, 2, 1 }; // строим связанный список Node *head = constructList(keys); // распечатать связанный список printList(head); return 0; } |
4. Стандартное решение
Стандартное решение добавляет один узел в начало любого списка. Эта функция называется push() так как мы добавляем ссылку в головной конец, делая список немного похожим на stack.
Мы знаем, что C++ имеет встроенный & аргумент функция для реализации эталонных параметров. Если мы добавим & к типу параметра, компилятор автоматически заставит параметр работать по ссылке, не нарушая тип аргумента.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> #include <vector> using namespace std; // Узел связанного списка class Node { public: int key; // поле данных Node* next; // указатель на следующий узел }; /* push() в C++ — мы просто добавляем `&` в правую часть заголовка тип параметра, и компилятор заставляет этот параметр работать по ссылке. Таким образом, этот код изменяет память вызывающей программы, но никакое дополнительное использование `*` недопустимо. необходимо — мы обращаемся к "head" напрямую, и компилятор делает это изменить ссылку обратно на вызывающую сторону. */ void push(Node* &headRef, int key) { // выделяем новый узел в куче и устанавливаем его данные Node* node = new Node; node->key = key; // устанавливаем указатель `.next` нового узла так, чтобы он указывал на текущий // первый узел списка. // нет необходимости в дополнительном использовании `*` в голове — компилятор // позаботится об этом за кулисами node->next = headRef; // изменяем указатель головы, чтобы он указывал на новый узел, так что // теперь первый узел в списке. headRef = node; } // Функция реализации связанного списка из заданного набора ключей Node* constructList(vector<int> const &keys) { Node* head = nullptr; // начинаем с конца массива for (int i = keys.size() - 1; i >= 0; i--) { // Обратите внимание, что дополнительное использование `&` не требуется — компилятор берет // позаботимся об этом и здесь. Эти звонки меняют голову. push(head, keys[i]); } return head; } // Вспомогательная функция для печати связанного списка void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // клавиши ввода (в обратном порядке) vector<int> keys = { 4, 3, 2, 1 }; // строим связанный список Node *head = constructList(keys); // распечатать связанный список printList(head); return 0; } |
5. Сделайте указатель головы глобальным
Мы можем создать связанный список, сделав указатель заголовка глобальным, но этот подход не рекомендуется, поскольку глобальные переменные обычно считаются плохой практикой.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <iostream> #include <vector> using namespace std; // Узел связанного списка class Node { public: int key; Node* next; }; // Глобальный указатель головы Node* head = nullptr; // Берет список и значение данных, создает новую ссылку с заданным // данные и помещает их в начало списка. void push(int key) { // выделяем новый узел в куче и устанавливаем его данные Node* node = new Node; node->key = key; // устанавливаем указатель `.next` нового узла так, чтобы он указывал на текущий // головной узел списка. node->next = head; // изменяем указатель головы, чтобы он указывал на новый узел, так что // теперь первый узел в списке. head = node; } // Функция реализации связанного списка из заданного набора ключей void constructList(vector<int> const &keys) { // начинаем с конца массива for (int i = keys.size() - 1; i >= 0; i--) { push(keys[i]); } } // Вспомогательная функция для печати глобального связанного списка `head` void printList() { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // клавиши ввода (в обратном порядке) vector<int> keys = { 4, 3, 2, 1 }; // строим связанный список constructList(keys); // распечатать связанный список printList(); return 0; } |
6. Возврат головы из push() функция
Другой распространенный подход, которому следуют многие программисты, заключается в возврате головного узла из push() функцию и обновить голову в вызывающей программе. Это показано ниже:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <vector> using namespace std; // Узел связанного списка class Node { public: int key; // поле данных Node* next; // указатель на следующий узел }; /* Принимает список и значение данных, создает новую ссылку с заданными данными и помещает его в начало списка. */ Node* push(Node* head, int key) { // выделяем новый узел в куче и устанавливаем его данные Node* node = new Node; node->key = key; // устанавливаем указатель `.next` нового узла так, чтобы он указывал на текущий // первый узел списка. node->next = head; // вернуть новый узел, чтобы он стал первым узлом в списке return node; } // Функция реализации связанного списка из заданного набора ключей Node* constructList(vector<int> const &keys) { Node* head = nullptr; // начинаем с конца массива for (int i = keys.size() - 1; i >= 0; i--) { head = push(head, keys[i]); // обновить заголовок здесь } return head; } // Вспомогательная функция для печати связанного списка void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->key << " -> "; ptr = ptr->next; } cout << "nullptr"; } int main() { // клавиши ввода (в обратном порядке) vector<int> keys = { 4, 3, 2, 1 }; // строим связанный список Node *head = constructList(keys); // распечатать связанный список printList(head); return 0; } |
Продолжить чтение:
Связанный список – вставка в конце | Реализация C, Java и Python
Также см:
Использованная литература: http://cslibrary.stanford.edu/103/LinkedListBasics.pdf