单向链表类的实现

来源：My Blog 《单向链表类的实现》

下面这段程序是关于单向链表类的实现，你可以把他作为你的头文件
提供一些比较常用的操作，如果有需要，以后会更新
如果有什么错误和不足，一定要给我留言，非常感谢！

/*********************************************************** *******/
/*                                             *
* Programme   ：   list.cpp                         *
* Description   ：   单向链表类的实现                     *
* Author   ：   Ma Jia nan                         *
*                                             *
************************************************************ **********/

/* 把list（）链表和list_item（链表项）抽象为独立的类             */
/* 链表支持的操作：插入（insert）,删除（remove），查找（find），
            查询链表长度（szie），显示链表（display），
      链表翻转（reverse），链表连接（concatenate）       */


#include “stdio.h”
#include <iostream>
using namespace std;

template<class elemType>
class list_item
{
public:
  //constructor
  //第二个参数是可选的，如果有第二个参数，则新的项插入在该指针指向的list_item的后面
  list_item( elemType value, list_item *item = 0 );

  //用inline函数封装对私有数据成员_value和_next的访问
  elemType value() const { return _value; }
  list_item<elemType>* next() const { return _next; }

  //对数据成员进行赋值
  void next( list_item<elemType> *link ) { _next = link;     }
  void value( elemType new_value )     { _value = new_value;}

private:
  elemType _value;
  list_item<elemType> *_next;

};

template<class elemType>
class myList
{
public:
  //default constructor
  myList():_at_front(0),_at_end(0),_current(0),_size(0) {}

  //copy constructor
  myList( const myList<elemType>& );

  //operator = overloading
  myList<elemType>& operator=( const myList<elemType>&);

  //destructor
  ~myList() { remove_all(); }

  //插入数据项

  //在指针ptr所指向的节点的前面插入数据，如果ptr为空，则ptr作为链表新的尾节点进行插入
  void insert_before( list_item<elemType> *ptr, const elemType value);

  //在指针ptr所指向的节点的后面插入数据，如果ptr为空，则ptr作为链表新的头节点进行插入
  void insert_after( list_item<elemType> *ptr, const elemType value );

  //在链表头插入数据
  void insert_front( const elemType value );

  //在链表尾插入数据
  void insert_end( const elemType value );

  //在拷贝构造函数和操作符=的实现过程中，抽取出函数insert_all()
  void insert_all( const myList<elemType> &rhs );

  //删除数据项
  void remove_front();
  void remove_all();
  int remove( elemType value );

  //查询数据项，并返回指向该节点的指针，若返回空指针则没有找到
  list_item<elemType>* find( const elemType value ) const;

  //显示链表
  void display( ostream &os = cout ) const;

  //两个链表的连接
  void concat( const myList &il );  

  //链表翻转
  void reverse();

  //为了使用户可以迭代链表中的元素，提供以下两个函数
  //init_iter()缺省的将iterator初始化为_at_front,否则迭代工作从指向list_item的指针开始
  list_item<elemType>* init_iter( list_item<elemType> *it = 0 );
  //返回链表中下一项，如果迭代结束，返回0
  list_item<elemType>* next_iter();

  int size() const { return _size; }

private:
  void size_increase() { ++_size; }
  void size_decrease() { –_size; }

  list_item<elemType> *_at_front;     //指向链表头
  list_item<elemType> *_at_end;     //指向链表尾
  //为了迭代的需要，添加指针_current
  list_item<elemType> *_current;     //指向当前节点
 
  int _size;                   //记录链表长度
};

//Function defination
template<class elemType>
list_item<elemType>::list_item( elemType value, list_item<elemType> *item ):_value( value )
{
  if( !item )
    _next = 0;
  else
  {
    _next = item->_next;
    item->_next = this;
  }
}

template<class elemType>
inline myList<elemType>::myList( const myList<elemType> &rhs ):_at_front( 0 ),_at_end( 0 ),_current( 0 ),_size( 0 )
{
  insert_all( rhs );
}

template<class elemType>
inline myList<elemType>& myList<elemType>::operator =( const myList<elemType> &rhs )
{
  if( this != &rhs )
  {
    remove_all();
    insert_all( rhs );
  }

  return *this;
}

template<class elemType>
inline void myList<elemType>::insert_before( list_item<elemType> *ptr, const elemType value)
{
  if( !ptr )
    insert_end( value );
  else
  {
    if( ptr == _at_front )
    {
        insert_front( value );
        size_increase();
    }    
    else
    {
        list_item<elemType> *temp = _at_front;
        while( temp->next() != ptr )
          temp = temp->next();
        new list_item<elemType>( value, temp );
        size_increase();
    }
  }
}

template<class elemType>
inline void myList<elemType>::insert_after( list_item<elemType> *ptr, const elemType value )
{
  if( !ptr )
    insert_front( value );
  else
  {
    new list_item<elemType>( value, ptr );
    size_increase();
  }
}

template<class elemType>
inline void myList<elemType>::insert_front( const elemType value )
{
  list_item<elemType> *ptr = new list_item<elemType>( value );

  if( !_at_front )   //链表为空
    _at_front = _at_end = ptr;
  else
  {
    ptr->next( _at_front );
    _at_front = ptr;
  }
  size_increase();
}

template<class elemType>
inline void myList<elemType>::insert_end( const elemType value )
{
  if( !_at_end )   //链表为空
    _at_end = _at_front = new list_item<elemType>( value );
  else
    _at_end = new list_item<elemType>( value, _at_end );
  size_increase();
}

template<class elemType>
void myList<elemType>::insert_all(const myList<elemType> &rhs)
{
  list_item<elemType> *pt = rhs._at_front;

  while( pt )
  {
    insert_end( pt->value() );
    pt = pt->next();
  }
}

template<class elemType>
void myList<elemType>::remove_front()
{
  if( _at_front )
  {
    list_item<elemType> *ptr = _at_front;
    _at_front = _at_front->next();

    //在删除头节点之前，防止_current指向被删除的项
    if( _current == ptr )
        _current = _at_front;

    size_decrease();
    delete ptr;
  }
  else   //链表为空
  {
    cout << “There is nothing in the list.” << endl;
  }
}

template<class elemType>
void myList<elemType>::remove_all()
{
  while( _at_front )
    remove_front();

  _size = 0;
  _at_front = _at_end = 0;
}

template<class elemType>
int myList<elemType>::remove( elemType value )
{
  list_item<elemType> *plist = _at_front;
  int elem_cnt = 0;   //删除的元素个数

  while( plist && plist->value() == value )   //链表不为空，并且头节点就是要删除的项
  {
    plist = plist->next();
    remove_front();
    ++elem_cnt;
  }

  if( !plist )   //链表为空，删除结束
    return elem_cnt;

  list_item<elemType> *prev = plist;
  plist = plist->next();

  while( plist )   //prev不是链表尾
  {
    if( plist->value() == value )
    {
        prev->next( plist->next() );

        //在删除节点之前，防止_current指向被删除的项
        if( _current == plist )
          _current = prev->next();

        delete plist;
        plist = NULL;
        ++elem_cnt;
        size_decrease();
        plist = prev->next();

        if( !plist )   //prev是链表尾
        {
          _at_end = prev;
          return elem_cnt;
        }
    }
    else
    {
        prev = plist;
        plist = plist->next();
    }
  }
  return elem_cnt;
}

template<class elemType>
list_item<elemType>* myList<elemType>::find( const elemType value ) const
{
  list_item<elemType> *ptr = _at_front;

  while( ptr )
  {
    if( ptr->value() == value )
        break;
    ptr = ptr->next();
  }

  return ptr;
}

template<class elemType>
void myList<elemType>::display( ostream &os ) const
{
  os << “\n(” << _size << “)(“;
  list_item<elemType> *ptr = _at_front;

  while( ptr )
  {
    os << ptr->value() << ” “;
    ptr = ptr->next();
  }

  os << “)\n” ;
}

template<class elemType>
void myList<elemType>::concat( const myList<elemType> &il )
{
  list_item<elemType> *ptr = il._at_front;

  while( ptr )
  {
    insert_end( ptr->value() );
    ptr = ptr->next();
  }
}

template<class elemType>
void myList<elemType>::reverse()
{
  list_item<elemType> *ptr = _at_front;
  list_item<elemType> *prev = 0;

  _at_front = _at_end;
  _at_end = ptr;

  while( ptr != _at_front )
  {
    list_item<elemType> *temp = ptr->next();
    ptr->next( prev );
    prev = ptr;
    ptr = temp;
  }

  _at_front->next( prev );
}

template<class elemType>
inline list_item<elemType>* myList<elemType>::init_iter( list_item<elemType> *it )
{
  return _current = it ? it : _at_front;
}

template<class elemType>
inline list_item<elemType>* myList<elemType>::next_iter()
{
  list_item<elemType> *next = _current ? _current = _current->next() : _current;

  return next;
}



//测试程序
int main()
{
  myList<int> my1;

  //测试insert_front() and insert_end()
  for( int x=0; x<10; ++x )
  {
    my1.insert_front( x );
    my1.insert_end( x );
  }
  cout <<”OK! After insert_front() and insert_end() ” << endl;
  my1.display();

  //测试find（）
  list_item<int> *pi = my1.find( 8 );
  cout << endl << “Searching for the value 8: Found it ” << (pi?”yes!\n”:”no!\n”) << endl;

  //测试insert_after()
  my1.insert_after( pi, 1024 );
  cout << endl << “Inserting element 1024 following the value 8″ << endl;
  my1.display();

  //测试insert_before()
  my1.insert_before( pi, 2048 );
  cout << endl << “Inserting element 2048 beofre the value 8″ << endl;
  my1.display();


  //测试remove_front（） and remove_all（）
  my1.remove_front();
  cout << endl << “Remove front element” << endl;
  my1.display();

  my1.remove_all();
  cout << endl << “Remove all elements” << endl;
  my1.display();


  myList<int> my2;
  cout << endl;
  cout << “———————————–” << endl;
  cout << “test #1: items at end” << endl;
  cout <<   “———————————–” << endl;
 
  my2.insert_front( 1 );
  my2.insert_front( 1 );
  my2.insert_front( 1 );
  my2.insert_front( 2 );
  my2.insert_front( 3 );
  my2.insert_front( 4 );
  my2.display();

  //测试remove（）
  int elem_cnt = my2.remove( 1 );
  cout << endl << “Remove ” << elem_cnt << ” of the value 1″ << endl;
  my2.display();
  my2.remove_all();

  cout << endl;
  cout << “———————————–” << endl;
  cout << “test #2: items at front” << endl;
  cout <<   “———————————–” << endl;

  my2.insert_front( 1 );
  my2.insert_front( 1 );
  my2.insert_front( 1 );
  my2.display();

  elem_cnt = my2.remove( 1 );
  cout << endl << “Remove ” << elem_cnt << ” of the value 1″ << endl;
  my2.display();
  my2.remove_all();

  cout << endl;
  cout << “———————————–” << endl;
  cout << “test #3: no items present” << endl;
  cout <<   “———————————–” << endl;

  my2.insert_front( 0 );
  my2.insert_front( 3 );
  my2.insert_front( 5 );
  my2.display();

  elem_cnt = my2.remove( 1 );
  cout << endl << “Remove ” << elem_cnt << ” of the value 1″ << endl;
  my2.display();
  my2.remove_all();


  myList<int> my3;
 
  for( int x=0; x<10; ++x )
  {
    my3.insert_front( x );
  }
  cout << endl << “my3 is : ” << endl;
  my3.display();
  //测试reverse()
  cout << endl << “Reverse my3:” << endl;
  my3.reverse();
  my3.display();


  myList<int> my4;
  for( int x=0; x<5; ++x )
    my4.insert_end( x );
  cout << endl << “my4 is :” << endl;
  my4.display();
  //测试concat（）
  my3.concat(my4);
  cout << endl << “my3 after concat with my4:” << endl;
  my3.display();


  //测试拷贝构造函数和=
  myList<int> my5(my3);
  cout << endl << “Copy constructor:after my5(my3), my5 is:” << endl;
  my5.display();
  my5 = my4;
  cout << endl << “After my5 = my4, my5 is :” << endl;
  my5.display();


  myList<int> my6;
  for( int x=0; x<10; ++x )
  {
    my6.insert_front( x );
    my6.insert_end( x );
  }
  cout << endl << “Use of init_iter() and next_iter()” << endl;
  list_item<int> *iter;
  for( iter = my6.init_iter(); iter; iter=my6.next_iter() )
    cout << iter->value() << ” ” ;
  cout << endl;

  return 0;
}