Rivalry2

HTML Diff

1 added 1 removed

Original 2026-01-01

Modified 2026-03-10

1 <p>Стандартная библиотека C++ включает достаточно много структур данных. Среди них есть списки, очереди, стеки, множества и т. д. Но если вы хотите эффективно их использовать, необходимо понимать особенности их работы. В этой статье поговорим о базовой структуре в С++ -<strong>односвязном списке</strong>.</p>

2 <h2>Односвязный список: теория</h2>

3 <p>Если хотите понять, как построен односвязный список, представьте цепь. У неё есть и начало, и конец, плюс звенья последовательно соединены друг с другом. Можно легко пройти от начала до конца цепи, перебирая звенья.</p>

4 <p>Схожим образом работают<strong>односвязные списки</strong>. В них начало списка - это головной элемент, звенья - это узлы, а конец списка определяется посредством NULL - специального узла. Причём, чтобы структура списка была полезной, на каждый узел "вешают" определённое значение.</p>

5 <p>У односвязного списка есть преимущество - вставка и удаление узлов осуществляется довольно легко<strong>в любом месте списка</strong>. Однако список нельзя индексировать в качестве массива, а структура списка ограничивает доступ к узлам по индексу. Если нужно попасть на какой-нибудь узел односвязного списка, нужно пройти весь путь последовательно, начиная от головного элемента, заканчивая нужным узлом.</p>

6 <h2>Интерфейс класса односвязного списка</h2>

7 <p>Однонаправленный список используют при хранении упорядоченного набора однотипных элементов. Дабы не определять для каждого типа данных свой список, лучше определить шаблонный класс:</p>

8 template< typename T > class List { private: // Объявляем структуру узла для использования в классе Iterator struct Node; public: // Класс итератора односвязного списка class Iterator { // Пока что опускаем ... }; public: List(); ~List(); // Добавляем узел в список void append( const T& t ); // Удаляем последний добавленный узел из списка void remove(); // Получаем головной элемент списка T head() const; // Получаем итератор на начало списка Iterator begin() const; // Получаем итератор на конец списка Iterator end() const; // Получаем размер списка size_t size() const; private: // Структура узла односвязного списка struct Node { Node() : m_next( NULL ) { } Node( const T& t ) : m_t( t ), m_next( NULL ) { } // Значение узла T m_t; // Указатель на следующий узел Node* m_next; }; // Голова односвязного списка Node* m_head; };<p>Класс односвязного списка поддерживает добавление узла в начало, получение значения головного элемента и удаление последнего добавленного узла. Также реализован обход списка посредством итераторов, плюс добавлена функция для расчета длины списка.</p>

9 <p>Определение узла осуществляется посредством структуры Node, содержащей два поля: - значение, привязанное к узлу, - m_t; - указатель на следующий узел - m_next.</p>

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

11 template< typename T > List< T >::List() : m_head( NULL ) { }<h2>Добавляем элемент в односвязный список</h2>

12 <p>Добавление узла в список производится в самое начало. То есть узел, который добавлен, сам превратится в новый головной элемент нашего списка:</p>

13 template< typename T > void List< T >::append( const T &t ) { // Создаём новый узел для значения // Если произойдёт исключение, контейнер не пострадает Node* node = new Node( t ); // Новый узел привязывается к старому головному элементу node->m_next = m_head; // Новый узел сам становится головным элементом m_head = node; }<h2>Удаляем элемент из односвязного списка</h2>

14 <p>В процессе удаления узла из списка усекается головной элемент. Таким образом, если в списке остаются узлы, новым головным элементом становится тот узел, который следует за головным элементом, в обратном случае - NULL:</p>

15 template< typename T > void List< T >::remove() { if( m_head ) { // Если список не пуст: // Сохраняем указатель на второй узел, который станет новым головным элементом Node* newHead = m_head->m_next; // Освобождаем память, выделенную для удаляемого головного элемента delete m_head; // Назначаем новый головной элемент m_head = newHead; } // Иначе мы могли бы возбудить исключение }<p>Идём дальше.<strong>Список - динамическая структура</strong>. Когда добавляются новые узлы, из кучи выделяется память - её нужно освободить, дабы не создавались утечки памяти. А имея в наличии функцию удаления элементов, мы без проблем реализуем деструктор односвязного списка:</p>

16 template< typename T > List< T >::~List() { while( m_head ) { remove(); } }<h2>Односвязный список: итератор</h2>

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

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

18 class Iterator { public: Iterator( Node* node ) : m_node( node ) { } // Проверка на равенство bool operator==( const Iterator& other ) const { if( this == &other ) { return true; } return m_node == other.m_node; } // Проверка на неравенство bool operator!=( const Iterator& other ) const { return !operator==( other ); } // Получение значения текущего узла T operator*() const { if( m_node ) { return m_node->m_t; } // Иначе достигнут конец списка. Здесь уместно возбудить исключение return T(); } // Переход к следующему узлу void operator++() { if( m_node ) { m_node = m_node->m_next; } // Иначе достигнут конец списка. Здесь уместно возбудить исключение } private: Node* m_node; };<p>В качестве итераторов для конца и начала нашего списка вернём следующее:</p>

19 template< typename T > typename List< T >::Iterator List< T >::begin() const { // Итератор пойдет от головного элемента... return Iterator( m_head ); } template< typename T > typename List< T >::Iterator List< T >::end() const { // ... и до упора, т.е. NULL return Iterator( NULL ); }<p>Что же, теперь мы можем легко обойти список с начала до конца. Но не стоит забывать про<strong>функцию вычисления длины</strong>. Для упрощения задачи будем использовать механизм итераторов: ```cplus template< typename T > size_t List< T >::size() const { size_t s = 0; for( Iterator it = begin(); it != end(); ++it ) { ++s; }</p>

20 /* Но можно и без итераторов for( Node* n = m_head; n != NULL; n = n-&gt;m_next ) { ++s; } */ return s;<p>}</p>

21 <h2>Вместо заключения</h2>

22 <p>Рассмотренный выше пример - лишь краткая демонстрация, из которой можно понять принципы работы с односвязным списком в C++. Однако практика показывает, что в реальных приложениях почти всегда лучше будет использовать<strong>стандартную библиотечную реализацию</strong>как списка, так и любой другой структуры данных. В этом случае работы от вас потребуется меньше. Кроме того, вы сразу получите в своё распоряжение оптимизированную и хорошо отлаженную версию, которой можно будет смело пользоваться.</p>