c++链表ADT 和主要函数实现

template <class Type>
struct nodeType {
    int info;
    nodeType *next;
};

template <class Type>
class linkedListType {
    
    friend ostream& operator<< (ostream&, const linkedListType<Type>&);

public:
    const linkedListType<Type>& operator= (const linkedListType<Type>&);

    void initializedList();
    bool isEmptyList();
    int length();
    void destroyList();
    Type front();
    Type back();
    bool search(const Type& searchItem);
    void insertFirst(const Type& newItem);
    void insertLast(const Type& newItem);
    void deleteNode(const Type& deleteItem);

    linkedListType();
    linkedListType(const linkedListType<Type>& otherList);
    ~linkedListType();

protected:
    int count;
    nodeType<Type> *first;
    nodeType<Type> *last;

private:
    void copyList(const linkedListType<Type>& otherList);

};

主要函数实现

template <class Type>
bool linkedListType<Type>::search(const Type& searchItem) {
    nodeType<Type> *current;
    current = first;

    while(current!=NULL) {
        if(current->info == searchItem)
            return true;
        else
            current = current->next;
    }
    return false;
}

template <class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem) {
    nodeType<Type> *current;
    nodeType<Type> *trailCurrent;
    bool found;

    /*
     * if the list is empty
     */
    if(first == NULL)
        cerr<<"Cannot delete from an empty list.\n";

    /*
     * if the list is not empty
     */
    else {
        /*
         * if the delete item is equal to the first element of the list
         *
         */
        if(first->info == deleteItem) {
            current = first;
            first = first->next;
            count--;

            /*
             * if after delete the first element of list
             * the list become empty
             * do something(make the last pointer to be NULL)
             */
            if(first == NULL) {
             last = NULL;
             delete current;
          }
        }

        /*
         * if not equal to the first element of the list
         */
        else {
           found = false;
           trailCurrent = first;     
           current = first->next;

           /*
            *squence search the list
            */
           while(current!=NULL&&!found) {
               if(current->info != deleteItem) {
                   trailCurrent = current;
                   current = current->next;
               }else {
                   found = true;
               }
          }

           /*
            * if find the delete item in the list
            */
           if(found) {
               trailCurrent->next = current->next;
               count--;

               if(last==current)
                   last = trailCurrent;

               delete current;
           }else {
               cout<<"Item to be deleted is not in the list."<<endl;
           }
      }
  }

}