Реализация связанного списка в виде шаблона класса...366

Приведённый далее шаблон класса LinkedList выглядит практически идентично классу AccountLinkedList из программы BUDGET3, если заменить класс Node обобщённым классом Т.

    /* LinkedList — связанный список произвольных объектов */

    #ifndef _ACCOUNTLINKEDLIST_

    #define _ACCOUNTLINKEDLIST_

    /* Предварительное объявление класса LinkedList */

    template < class T > class LinkedList;

    /* Node — узел связанного списка; каждый */

    /*          узел указывает на объект Т */

    template < class T > class Node

    {

    public:

        Node(LinkedList< T >* pL, T* pT)

        {

            pList = pL;

            pNext = 0;

            pObject = pT;

        }

        Node< T >* next( ) { return pNext; }

        Node<T >* next(Node< T >* pN) { pNext = pN;

                                        return pNext; }

        T* current( ) { return pObject; }

_________________

366 стр. Часть 6. Великолепная десятка

    protected:

        LinkedList< T >* pList;

        Node< T >* pNext;

        T* pObject;

    };

    /* LinkedList — связанный список объектов Node */

    template < class T > class LinkedList

    {

      public :

        LinkedList< T >( ) { pFirst = 0 ; }

        Node< T >* firstNode( ) { return pFirst ; }

        Node< T >* lastNode( )

        {

            /* Если список пуст, возвращает 0 */

            if ( pFirst == 0 )

            {

                return 0 ;

            }

            /* В противном случае ищем последний элемент списка */

            Node< T >* pN = pFirst ;

            while ( true )

            {

                Node< T >* pNext = pN -> next( ) ;

                if ( pNext == 0 )

                {

                    break ;

                }

                pN = pNext ;

            }

            return pN ;

        }

        void addNode( Node< T >* pNode )

        {

            Node< T >* pN = lastNode( ) ;

            if ( pN == 0 )

            {

                pFirst = pNode ;

            }

            else

            {

                pN -> next( pNode ) ;

            }

        }

      protected :

        Node< T >* pFirst ;

    } ;

    #endif 

_________________

367 стр. Глава 31. Программа BUDGET 

«Дальнейшее рассмотрение может оказаться проще, если вы мысленно замените обобщённый класс Т действительным классом Account. При этом вы увидите, насколько программа становится похожей на свою предшественницу — программу BUDGET3.»

[Советы]

Выражение template < class Т > class LinkedList представляет собой предварительное объявление шаблона, необходимое для класса Node.

«Не забывайте о том, что шаблоны классов LinkedList и Node не являются реальными классами до тех пор, пока параметр Т не будет заменён действительным классом.» 

[Помни!]

Шаблон класса Node сконструирован для работы в качестве узла связанного списка. Каждый узел указывает на объект класса Т, который будет определён позже. Конструктор инициализирует члены-указатели: pList указывает на LinkedList, членом которого является данный объект Node, pObject указывает на объект типа Т, a pNext инициализируется значением 0 , указывающим, что пока узел не является членом списка.

"Активный метод" next ( Node< T >* ) добавляет текущий узел в список путём инициализации указателя pNext. "Пассивный метод" next( ) просто возвращает следующий объект Node< T > в списке. Это обычная практика кодирования, когда функция fn( ) возвращает текущее значение объекта, a fn( Т ) устанавливает его значение на основе аргумента.

Эта версия addNode( ) более усовершенствована по сравнению с представленной в программе BUDGET3, поскольку добавляет узел в конец списка. Преимущество такого подхода в том, что объекты считываются из списка в том же порядке, в котором были в него внесены, а недостаток в том, что метод lastNode( ) должен выполнять проход по всему списку всякий раз, когда требуется внести в список новый объект. Это может существенно замедлить работу программы при большом количестве элементов в списке.