C++ STL里的 list模版(简化版)算法和实现

这是前些天做的，现在拿出来总结总结，这应该是考研数据结构考试中，一维线形表最复杂的方式了。

采用双向(STL也是双向)循环(没看出来STL是不是循环)链表，

template < typename _Ty >

class list_node {

public:

    _Ty _data;           //保存数据元素

    list_node* _prior;       //指向前一个数据元素

    list_node* _next;    //指向后一个数据元素

};

 

template < typename _Ty >

class list_t {

private:

    int           _size; // 表的长度，为计算方便线性存储

    list_node<_Ty>* _begin;  // 头节点指针

    list_node<_Ty>* _end;   // 尾节点指针

    list_node<_Ty>* _pointer( const int _Pos );      // 由节点的位置获得其指针

    bool          _overbound( const int _Pos );   // 检测参数_Pos是否越界

public:

    list_t( );

    ~list_t( );

    void          clear( );

    const bool    empty( ) const;

    const int     size( ) const;

    void          reverse( );

    void          no_duplicate( );

    void          unique( );

   

    int           insert(int _Where, const _Ty& _Val);

    void          insert(int _Where, int _Count, const _Ty& _Val);

 

    _Ty           erase(const int _Where);

    void          erase(const int _First, const int _Last);

    int           remove(const _Ty& _Val);

 

    void          push_back(const _Ty& _Val);

    void          push_front(const _Ty& _Val);

    _Ty           pop_back( );

    _Ty           pop_front( );

 

    _Ty           front( );

    _Ty           back( );

    _Ty           at(const int _Pos);

    _Ty           operator[](const int _Pos);

 

    void          traverse( void (*func)(_Ty&) );

};