Односвязный список на C++

Односвязный список на C++

В стандартную библиотеку C++ входит немало основных структур данных. Среди которых вы найдете списки, стеки, очереди, множества и другие. Но чтобы эффективно пользоваться ими, вы должны хорошо представлять особенности их работы. Речь пойдет об одной из базовых структур: односвязном списке.

РЕКОМЕНДУЕМ:Способы повышения продуктивности для программиста

Односвязные списки в теории

Чтобы понять, как строится односвязный список, представьте себе цепь. У цепи есть начало и конец, а также звенья, которые последовательно соединяются друг с другом. Вы легко можете пройти от начала цепи до ее конца, переходя последовательно от одного звена к другому.

Именно так и работают односвязные списки. Начало списка называют головным элементом, а звенья — узлами. Конец списка определяется с помощью специального узла ( NULL). При этом на каждый узел «вешают» значение, чтобы структура была полезной.

Преимущество односвязных списков заключается в том, что вставка и удаление узлов относительно легко осуществляется в любом месте списка. Однако структура списка ограничивает доступ к его узлам по индексу. Список нельзя индексировать, как массив. Чтобы попасть на некоторый узел односвязного списка, необходимо последовательно пройти весь путь от головного элемента до нужного узла.

Интерфейс класса односвязного списка

Односвязный список предназначен для хранения упорядоченного набора однотипных элементов. Чтобы не определять для каждого типа данных свой список, определим шаблонный класс:

Наш класс односвязного списка будет поддерживать добавление узла в его начало, удаление последнего добавленного узла и получение значения головного элемента. Кроме того, мы реализуем обход списка с помощью итераторов, а также добавим функцию-член для расчета длины списка.

Узел определяется с помощью структуры Node, которая содержит два поля: m_t — значение, привязанное к узлу, и m_next — указатель на следующий узел.

Изначально список пуст, поэтому головной элемент указывает на NULL:

Добавление элемента в односвязный список

Добавление узла в односвязный список осуществляется в самое начало. Добавленный узел сам станет новым головным элементом списка:

Удаление элемента из односвязного списка

При удалении узла из односвязного списка усекается его головной элемент. Если в списке еще остаются узлы, то новым головным элементом становится узел, следующий за головным элементом, иначе остается NULL:

Список является динамической структурой. При добавлении новых узлов выделяется память из кучи, которую нужно освободить, чтобы не создавать утечек памяти. Имея функцию удаления элементов, реализовать деструктор односвязного списка совсем не сложно:

Итератор односвязного списка

Функциональность для добавления/удаления узлов в список лучше не смешивать с задачей его обхода. Для этого существуют итераторы. Создадим итератор односвязного списка в стиле C++. Вернемся к его определению, которое ранее пропустили:

В качестве итераторов для начала и конца списка вернем следующее:

Теперь список легко можно обойти от начала до конца. Но не забудем про функцию для вычисления его длины. Воспользуемся механизмом итераторов, чтобы упростить задачу:

Заключение

Учитывайте, что рассмотренный пример является лишь краткой демонстрацией принципов работы с односвязным списком в C++. В реальных программах практически всегда лучше использовать стандартную библиотечную реализацию списка и любой другой структуры данных. Тогда вам не только потребуется делать меньше работы, но вы получите в распоряжение хорошо отлаженную и оптимизированную версию, которой сможете смело пользоваться.

РЕКОМЕНДУЕМ:Как пользоваться const в C++

Понравилась статья? Поделиться с друзьями:
Добавить комментарий