linklist.h

C++参考书

#ifndef LINKLIST_H
#define LINKLIST_H

template<typename T> class LinkedList ;

template<typename T>
class ListEntry
{
	private:
		ListEntry( T & ) ;
		friend class LinkedList<T> ;

		T thisEntry ;
		ListEntry *nextEntry ;
		ListEntry *prevEntry ;
} ;

template<typename T>
ListEntry<T>::ListEntry( T &entry )
{
	thisEntry = entry ;
	nextEntry = NULL ;
	prevEntry = NULL ;
}

template<typename T>
class LinkedList
{
	public:
		LinkedList( void ) ;
		~LinkedList( void ) ;

		void appendEntry( T & ) ;
		void removeEntry( int = -1 ) ;
		void insertEntry( T &, int = -1 ) ;

		T* findEntry( int ) ;
		T* currentEntry( void ) ;
		T* FirstEntry( void ) ;
		T* LastEntry( void ) ;
		T* nextEntry( void ) ;
		T* prevEntry( void ) ;

	private:
		ListEntry<T> *firstEntry ;
		ListEntry<T> *lastEntry ;
		ListEntry<T> *iterator ;

		void removeEntry( ListEntry<T> * ) ;
		void insertEntry( T &, ListEntry<T> * ) ;
} ;

template<typename T>
LinkedList<T>::LinkedList( void )
{
	iterator = NULL ;
	firstEntry = NULL ;
	lastEntry = NULL ;
}

template<typename T>
LinkedList<T>::~LinkedList( void )
{
	while ( firstEntry )
		removeEntry( firstEntry ) ;
}

template<typename T>
void LinkedList<T>::appendEntry( T &entry )
{
	ListEntry<T> *newEntry = new ListEntry<T>( entry ) ;
	newEntry->prevEntry = lastEntry ;

	if ( lastEntry )
		lastEntry->nextEntry = newEntry ;

	if ( firstEntry == NULL )
		firstEntry = newEntry ;

	lastEntry = newEntry ;
}

template<typename T>
void LinkedList<T>::removeEntry( ListEntry<T> *lentry )
{
	if ( lentry == NULL )
		return ;

	if ( lentry == iterator )
		iterator = lentry->prevEntry ;

	if ( lentry->nextEntry )
		lentry->nextEntry->prevEntry = lentry->prevEntry ;

	if ( lentry->prevEntry )
		lentry->prevEntry->nextEntry = lentry->nextEntry ;

	if ( lentry == lastEntry )
		lastEntry = lentry->prevEntry ;

	if ( lentry == firstEntry )
		firstEntry = lentry->nextEntry ;

	delete lentry ;
}

template<typename T>
void LinkedList<T>::insertEntry( T &entry, ListEntry<T> *lentry )
{
	ListEntry<T> *newEntry = new ListEntry<T>( entry ) ;
	newEntry->nextEntry = lentry ;

	if ( lentry ) {
		newEntry->prevEntry = lentry->prevEntry ;
		lentry->prevEntry = newEntry ;
	}

	if ( newEntry->prevEntry )
		newEntry->prevEntry->nextEntry = newEntry ;

	if ( lentry == firstEntry )
		firstEntry = newEntry ;
}

template<typename T>
void LinkedList<T>::removeEntry( int pos )
{
	findEntry( pos ) ;
	removeEntry( iterator ) ;
}

template<typename T>
void LinkedList<T>::insertEntry( T &entry, int pos )
{
	findEntry( pos ) ;
	insertEntry( entry, iterator ) ;
}

template<typename T>
T* LinkedList<T>::currentEntry( void )
{
	return iterator ? &( iterator->thisEntry ) : NULL ;
}

template<typename T>
T* LinkedList<T>::findEntry( int pos )
{
	if ( pos != -1 ) {

		iterator = firstEntry ;

		if ( iterator )
			while ( pos-- )
				iterator = iterator->nextEntry ;
	}

	return currentEntry() ;
}

template<typename T>
T* LinkedList<T>::FirstEntry( void )
{
	iterator = firstEntry ;
	return currentEntry() ;
}

template<typename T>
T* LinkedList<T>::LastEntry( void )
{
	iterator = lastEntry ;
	return currentEntry() ;
}

template<typename T>
T* LinkedList<T>::nextEntry( void )
{
	if ( iterator == NULL )
		iterator = firstEntry ;
	else
		iterator = iterator->nextEntry ;

	return currentEntry() ;
}

template<typename T>
T* LinkedList<T>::prevEntry( void )
{
	if ( iterator == NULL )
		iterator = lastEntry ;
	else
		iterator = iterator->prevEntry ;

	return currentEntry() ;
}

#endif