Списки в C++. Односвязный список
Стандартная библиотека C++ включает достаточно много структур данных. Среди них есть списки, очереди, стеки, множества и т. д. Но если вы хотите эффективно их использовать, необходимо понимать особенности их работы. В этой статье поговорим о базовой структуре в С++ — односвязном списке.
Односвязный список: теория
Если хотите понять, как построен односвязный список, представьте цепь. У неё есть и начало, и конец, плюс звенья последовательно соединены друг с другом. Можно легко пройти от начала до конца цепи, перебирая звенья.
Схожим образом работают односвязные списки. В них начало списка — это головной элемент, звенья — это узлы, а конец списка определяется посредством NULL — специального узла. Причём, чтобы структура списка была полезной, на каждый узел «вешают» определённое значение.
У односвязного списка есть преимущество — вставка и удаление узлов осуществляется довольно легко в любом месте списка. Однако список нельзя индексировать в качестве массива, а структура списка ограничивает доступ к узлам по индексу. Если нужно попасть на какой-нибудь узел односвязного списка, нужно пройти весь путь последовательно, начиная от головного элемента, заканчивая нужным узлом.
Интерфейс класса односвязного списка
Однонаправленный список используют при хранении упорядоченного набора однотипных элементов. Дабы не определять для каждого типа данных свой список, лучше определить шаблонный класс:
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; };
Класс односвязного списка поддерживает добавление узла в начало, получение значения головного элемента и удаление последнего добавленного узла. Также реализован обход списка посредством итераторов, плюс добавлена функция для расчета длины списка.
Определение узла осуществляется посредством структуры
Изначально список является пустым, а значит, головной элемент указывает на NULL:
template< typename T > List< T >::List() : m_head( NULL ) { }
Добавляем элемент в односвязный список
Добавление узла в список производится в самое начало. То есть узел, который добавлен, сам превратится в новый головной элемент нашего списка:
template< typename T > void List< T >::append( const T &t ) { // Создаём новый узел для значения // Если произойдёт исключение, контейнер не пострадает Node* node = new Node( t ); // Новый узел привязывается к старому головному элементу node->m_next = m_head; // Новый узел сам становится головным элементом m_head = node; }
Удаляем элемент из односвязного списка
В процессе удаления узла из списка усекается головной элемент. Таким образом, если в списке остаются узлы, новым головным элементом становится тот узел, который следует за головным элементом, в обратном случае — NULL:
template< typename T > void List< T >::remove() { if( m_head ) { // Если список не пуст: // Сохраняем указатель на второй узел, который станет новым головным элементом Node* newHead = m_head->m_next; // Освобождаем память, выделенную для удаляемого головного элемента delete m_head; // Назначаем новый головной элемент m_head = newHead; } // Иначе мы могли бы возбудить исключение }
Идём дальше. Список — динамическая структура. Когда добавляются новые узлы, из кучи выделяется память — её нужно освободить, дабы не создавались утечки памяти. А имея в наличии функцию удаления элементов, мы без проблем реализуем деструктор односвязного списка:
template< typename T > List< T >::~List() { while( m_head ) { remove(); } }
Односвязный список: итератор
Функциональность для удаления и добавления узлов в список не стоит смешивать с задачей его обхода. Для этих целей есть итераторы. Давайте создадим итератор списка в стиле C++. Для начала вернёмся к его определению, которое раньше пропустили:
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; };
В качестве итераторов для конца и начала нашего списка вернём следующее:
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 ); }
Что же, теперь мы можем легко обойти список с начала до конца. Но не стоит забывать про функцию вычисления длины. Для упрощения задачи будем использовать механизм итераторов: ```cplus template< typename T > size_t List< T >::size() const { size_t s = 0; for( Iterator it = begin(); it != end(); ++it ) { ++s; }
/* Но можно и без итераторов for( Node* n = m_head; n != NULL; n = n->m_next ) { ++s; } */ return s;
}
Вместо заключения
Рассмотренный выше пример — лишь краткая демонстрация, из которой можно понять принципы работы с односвязным списком в C++. Однако практика показывает, что в реальных приложениях почти всегда лучше будет использовать стандартную библиотечную реализацию как списка, так и любой другой структуры данных. В этом случае работы от вас потребуется меньше. Кроме того, вы сразу получите в своё распоряжение оптимизированную и хорошо отлаженную версию, которой можно будет смело пользоваться.
