?
Solved

Double Link List

Posted on 1998-12-01
3
Medium Priority
?
314 Views
Last Modified: 2008-02-01
I am confused with template classes and lost in all errors I got when trying to debug doble link list project.
Please, help!!!
There is h and cpp files:
#ifndef __List__
#define __List__
#include <iostream.h>
#include <stdlib.h>

template <class Etype>   // Incomplete class declaration
class ListItr;           // so friend is visible


template <class Etype>
class List
{
  public:
        List();
      friend class ListItr<Etype>;

    class ListNode
    {
            Etype Element;      
        ListNode *Next;
            ListNode *Prev;
            ListNode();

            friend class List<Etype>;
        friend class ListItr<Etype>;
    };

  };

// ListItr class interface

template <class Etype>
class ListItr
 
{
  public:
        ListItr( const List<Etype> & L ) : Header(L.Header)
   // ~ListItr( ) { }

    // Insert X before Current position
    // Current: Set to new node on success; unchanged otherwise
    void InsertBefore( const Etype & X );
      // Insert X after Current position
    // Current: Set to new node on success; unchanged otherwise
   
   void InsertAfter( const Etype & X );
       
   
      // Find first occurence of X on the list
      int FindFirst( const Etype & X );
      // Find las occurence of X on the list
      int FindLast(const Etype & X);
   

    // Removes first occurrence of X on the list; do nothing if X is not found
    int RemoveFirst( const Etype & X );

    // Remove  last occurence of X on the list; do nothing if X is not found
    int RemoveLast(const Etype & X );

    // Returns 1 if Current is not NULL or Header, 0 otherwise
    int operator--( ) const { return Current && Current != Header; }

   
    // Set Current to the header node
    void MoveToHead(){ Current = Header; }
      void MoveToTail(){ Current = Tail;}                  

    // Set Current to the tail node
   
    void First( );
      // return 1st node on the list
     
  private:
    List<Etype>::ListNode *Current;         // Current position
 
    //List<Etype>::List( const List & ) { } // Disable copy constructor
}




#endif

#include "List.h"
#include <iostream.h>
#include <stdlib.h>


template <class Etype>
List<Etype>::ListNode( )
{
      Header = new ListNode;
      Tail = new ListNode;
      Header->Next = *Tail;
      Tail->Prev = *Header;

}




template <class Etype>
void
ListItr<Etype>::InsertAfter( const Etype & X )
{
   
    List<Etype>::ListNode *NewNode;

    NewNode = new List<Etype>::ListNode( X );
    NewNode->Prev = Current;
      NewNode->Next = Current->Next;
      NewNode->Prev->Next = NewNode;
      NewNode->Next->Prev = NewNode;
      Current = NewNode;

}

template <class Etype>
void
ListItr<Etype>::InsertBefore( const Etype & X )
{
      List<Etype>::ListNode *NewNode;

    NewNode = new List<Etype>::ListNode( X );
    NewNode->Prev = Current;
      NewNode->Next = Current->Next;
      NewNode->Prev->Next = NewNode;
      NewNode->Next->Prev = NewNode;
      Current = NewNode;      
      
}



template <class Etype>
int
ListItr<Etype>::FindFirst( const Etype & X )
{
    List<Etype>::ListNode *Ptr = Header->Next;

    while( Ptr != NULL && Ptr->Element != X )
        Ptr = Ptr->Next;

    if( Ptr == Tail )
        return 0;

    Current = Ptr;
    return 1;
}

int <class Etype>
int
ListItr<Etype>::FindLast( const Etype & X )
{
    List<Etype>::ListNode *Ptr = Tail->Prev;

    while( (Ptr != NULL) && (Ptr->Element) != X )
        Ptr = Ptr->Prev;

    if( Ptr == Header )
        return 0;

    Current = Ptr;
    return 1;
}


template <class Etype>
int
ListItr<Etype>::RemoveFirst( const Etype & X )
{
    List<Etype>::ListNode *Ptr = Header;

    while( Ptr->Next != NULL && Ptr->Next->Element != X )
        Ptr = Ptr->Next;

    if( Ptr->Next == NULL )
        return 0;    // Remove fails

        // Bypass and reclaim memory
    List<Etype>::ListNode *DeletedNode = Ptr->Next;
    Ptr->Next = Ptr->Next->Next;

    delete DeletedNode;

    Current = Header;    // Reset Current
    return 1;
}



template <class Etype>
int
ListItr<Etype>::RemoveLast( const Etype & X )
{
    List<Etype>::ListNode *Ptr = Tail;

    while( Ptr->Next != NULL && Ptr->Prev->Element != X )
        Ptr = Ptr->Prev;

    if( Ptr->Prev == NULL )
        return 0;    // Remove fails

        // Bypass and reclaim memory
    List<Etype>::ListNode *DeletedNode = Ptr->Prev;
    Ptr->Prev->Next = Ptr;

    delete DeletedNode;

    Current = Tail;    // Reset Current
    return 1;
}


template <class Etype>
int
ListItr<Etype>::IsFound( const Etype & X ) const
{
    List<Etype>::ListNode *Ptr = Header->Next;

    while( Ptr != NULL && Ptr->Element != X )
        Ptr = Ptr->Next;

    return Ptr != NULL;
}

int <class Etype>
const Etype &
ListItr<Etype>::operator( ) ( ) const
{
   

    return Current->Element;
}

template <class Etype>
void
ListItr<Etype>::First( )
{
   
    Current = Header->Next;
}

int <class Etype>
void
ListItr<Etype>::Last( )
{
    Current = Tail->Prev;
}





template <class Etype>
void
ListItr<Etype>::operator--( )
{
 
    Current->Prev = Current->Prev->Next;
      Current->Next = Current
      Current = Current->Prev;
}

0
Comment
Question by:romark
3 Comments
 
LVL 2

Expert Comment

by:cyrilbdt
ID: 1179045
#ifndef __List__
#define __List__
#include <iostream.h>
#include <stdlib.h>

template <class Etype> // Incomplete class declaration
class ListItr;// so friend is visible


template <class Etype>
class List{
      public:
      List();
      friend class ListItr<Etype>;

      class ListNode{
            Etype Element;
            ListNode *Next;
            ListNode *Prev;
            ListNode();

            friend class List<Etype>;
            friend class ListItr<Etype>;
      };
};

// ListItr class interface

template <class Etype>
class ListItr{
public:
      ListItr( const List<Etype> & L ) : Header(L.Header) {};
   // ~ListItr( ) { }

    // Insert X before Current position
    // Current: Set to new node on success; unchanged otherwise
      void InsertBefore( const Etype & X );
// Insert X after Current position
    // Current: Set to new node on success; unchanged otherwise

      void InsertAfter( const Etype & X );
// Find first occurence of X on the list
      int FindFirst( const Etype & X );
// Find las occurence of X on the list
      int FindLast(const Etype & X);


      // Removes first occurrence of X on the list; do nothing if X is not found
      int RemoveFirst( const Etype & X );

      // Remove  last occurence of X on the list; do nothing if X is not found
      int RemoveLast(const Etype & X );
      int IsFound(const Etype & X ) const;

      // Returns 1 if Current is not NULL or Header, 0 otherwise
//      void operator--( ) { return Current && Current != Header; } - you got it twice - decide what it will be
      void operator--();
      const Etype& operator( ) ( ) const;

      // Set Current to the header node
      void MoveToHead(){ Current = Header; }
      void MoveToTail(){ Current = Tail;}
      void Last( );

      // Set Current to the tail node
      
      void First( );
// return 1st node on the list
private:
      List<Etype>::ListNode *Current;         // Current position

      //List<Etype>::List( const List & ) { } // Disable copy constructor
};

#endif

#include "h1.h"
#include <iostream.h>
#include <stdlib.h>


template <class Etype>
List<Etype>::ListNode()
{
      Header = new ListNode;
      Tail = new ListNode;
      Header->Next = *Tail;
      Tail->Prev = *Header;
}




template <class Etype>
void
ListItr<Etype>::InsertAfter( const Etype & X)
{
      List<Etype>::ListNode *NewNode;
      NewNode = new List<Etype>::ListNode( X );
      NewNode->Prev = Current;
      NewNode->Next = Current->Next;
      NewNode->Prev->Next = NewNode;
      NewNode->Next->Prev = NewNode;
      Current = NewNode;
}

template <class Etype>
void ListItr<Etype>::InsertBefore( const Etype & X )
{
      List<Etype>::ListNode *NewNode;

      NewNode = new List<Etype>::ListNode(X);
      NewNode->Prev = Current;
      NewNode->Next = Current->Next;
      NewNode->Prev->Next = NewNode;
      NewNode->Next->Prev = NewNode;
      Current = NewNode;
}

template <class Etype>
int ListItr<Etype>::FindFirst( const Etype & X )
{
      List<Etype>::ListNode *Ptr = Header->Next;

      while( Ptr != NULL && Ptr->Element != X )
            Ptr = Ptr->Next;
            if( Ptr == Tail )
                  return 0;

      Current = Ptr;
      return 1;
}

template <class Etype>
int ListItr<Etype>::FindLast( const Etype & X )
{
      List<Etype>::ListNode *Ptr = Tail->Prev;

      while( (Ptr != NULL) && (Ptr->Element) != X )
            Ptr = Ptr->Prev;

      if( Ptr == Header )
            return 0;
      Current = Ptr;
      return 1;
}


template <class Etype>
int
ListItr<Etype>::RemoveFirst( const Etype & X )
{
    List<Etype>::ListNode *Ptr = Header;

    while( Ptr->Next != NULL && Ptr->Next->Element != X )
        Ptr = Ptr->Next;

    if( Ptr->Next == NULL )
        return 0;    // Remove fails

        // Bypass and reclaim memory
    List<Etype>::ListNode *DeletedNode = Ptr->Next;
    Ptr->Next = Ptr->Next->Next;

    delete DeletedNode;

    Current = Header;    // Reset Current
    return 1;
}



template <class Etype>
int
ListItr<Etype>::RemoveLast( const Etype & X )
{
    List<Etype>::ListNode *Ptr = Tail;

    while( Ptr->Next != NULL && Ptr->Prev->Element != X )
        Ptr = Ptr->Prev;

    if( Ptr->Prev == NULL )
        return 0;    // Remove fails

        // Bypass and reclaim memory
    List<Etype>::ListNode *DeletedNode = Ptr->Prev;
    Ptr->Prev->Next = Ptr;

    delete DeletedNode;

    Current = Tail;    // Reset Current
    return 1;
}


template <class Etype>
int ListItr<Etype>::IsFound(const Etype & X ) const
{
    List<Etype>::ListNode *Ptr = Header->Next;

    while( Ptr != NULL && Ptr->Element != X )
        Ptr = Ptr->Next;

    return Ptr != NULL;
}

template <class Etype>
const Etype& ListItr<Etype>::operator( ) ( ) const
{
      return Current->Element;
}

template <class Etype>
void ListItr<Etype>::First( )
{
    Current = Header->Next;
}

template <class Etype>
void ListItr<Etype>::Last( )
{
    Current = Tail->Prev;
}

template <class Etype>
void ListItr<Etype>::operator--( )
{
      Current->Prev = Current->Prev->Next;
      Current->Next = Current;
      Current = Current->Prev;
}

void main()
{}

hope this helps
0
 

Author Comment

by:romark
ID: 1179046
Thanks, but this 2 syntax corrections not solving a problem.  I think it's need logical changes.

0
 

Accepted Solution

by:
dmcreyno earned 400 total points
ID: 1179047
Here's a working example (node.h, list.h).

//////////////////////////////////////////////////////////////////////////////
// Declarations and Implementation for Class Node
//
// Defines a linked list node and the operations associated with it.
//
//////////////////////////////////////////////////////////////////////////////
#ifndef NODE_CLASS
#define NODE_CLASS

template <class T>
class Node {
public:
                                        // The data is public
  T data;
   
                                            // Constructor
  Node (const T& item, Node<T>* ptrnext = NULL);
       
                                    // List modification methods
  void InsertAfter(Node<T> *p);
  Node<T> *DeleteAfter(void);
       
                                    // Obtain the address of the next node
  Node<T> *NextNode(void) const;
private:
                                    // Next is the address of the
                                    // following node
  Node<T> *next;
};                                  // End class Node declaration

                                    // Constructor. initialize data and
                                    // pointer members
template <class T>
Node<T>::Node(const T& item, Node<T>* ptrnext) :
             data(item), next(ptrnext)
{}
 
                                    // return value of private member next
template <class T>
Node<T> *Node<T>::NextNode(void) const {
    return next;
}

                                    // insert a node p after the current one
template <class T>
void Node<T>::InsertAfter(Node<T> *p) {
                                        // p points to successor of the current
                                    // node, and current node  points to p.
    p->next = next;
    next = p;
}

                                    // delete the node following current and
                                    // return its address
template <class T>
Node<T> *Node<T>::DeleteAfter(void) {
                                        // save address of node to be deleted
    Node<T> *tempPtr = next;
                                        // if there isn't a successor, return NULL
    if (next == NULL)
        return NULL;
                                        // current node points to successor of
                                    // tempPtr.
    next = tempPtr->next;
                                        // return the pointer to the unlinked node
    return tempPtr;
}


#endif  // NODE_CLASS


#ifndef LINKEDLIST_CLASS
#define LINKEDLIST_CLASS

#include <iostream.h>
#include <stdlib.h>

#ifndef NULL
const int NULL = 0;
#endif  // NULL

#include "node.h"

template <class T>
class SeqListIterator;

template <class T>
class LinkedList
{
   private:
      // pointers maintain access to front and rear of list
      Node<T> *front, *rear;
     
      // used for data retrieval, insertion and deletion
      Node<T> *prevPtr, *currPtr;
     
      // number of elements in the list
      int size;
     
      // position in list. used by Reset method
      int position;
      // private methods to allocate and deallocate nodes
      Node<T> *GetNode(const T& item,Node<T> *ptrNext=NULL);
      void FreeNode(Node<T> *p);
     
      // copies list L to current list
      void CopyList(const LinkedList<T>& L);
     
   public:
      // constructors
      LinkedList(void);
      LinkedList(const LinkedList<T>& L);
     
      // destructor
      ~LinkedList(void);
     
      // assignment operator
      LinkedList<T>& operator= (const LinkedList<T>& L);
     
      // methods to check list status
      int ListSize(void) const;              
      int ListEmpty(void) const;
     
      // Traversal methods
      void Reset(int pos = 0);
      void Next(void);
      int EndOfList(void) const;
      int CurrentPosition(void) const;
     
      // Insertion methods
      void InsertFront(const T& item);
      void InsertRear(const T& item);
      void InsertAt(const T& item);
      void InsertAfter(const T& item);
     
      // Deletion methods
      T DeleteFront(void);
      void DeleteAt(void);

      // Data retrieval/modification
      T& Data(void);
     
      // method to clear the list
      void ClearList(void);
     
      // this class (Ch. 12) needs access to front
      friend class SeqListIterator<T>;
};

template <class T>
Node<T> *LinkedList<T>::GetNode(const T& item,
                      Node<T>* ptrNext)
{
   Node<T> *p;

   p = new Node<T>(item,ptrNext);
   if (p == NULL)
   {
      cout << "Memory allocation failure!\n";
      exit(1);
   }
   return p;
}

template <class T>
void LinkedList<T>::FreeNode(Node<T> *p)
{
   delete p;
}

// copy L to the current list, which is assumed to be empty
template <class T>
void LinkedList<T>::CopyList(const LinkedList<T>& L)
{
   // use p to chain through L
   Node<T> *p = L.front;
   int pos;

   // insert each element in L at the rear of current object
   while (p != NULL)
   {
      InsertRear(p->data);
      p = p->NextNode();
   }
   
   // if list is empty return
   if (position == -1)
      return;

   // reset prevPtr and currPtr in the new list
   prevPtr = NULL;
   currPtr = front;
   for (pos = 0; pos != position; pos++)
   {
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
   }
}

// create empty list by setting pointers to NULL, size to 0
// and list position to -1
template <class T>
LinkedList<T>::LinkedList(void): front(NULL), rear(NULL),
      prevPtr(NULL),currPtr(NULL), size(0), position(-1)
{}

template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)
{
   front = rear = NULL;
   prevPtr = currPtr = NULL;
   size = 0;
   position = -1;
   CopyList(L);
}

template <class T>
void LinkedList<T>::ClearList(void)
{
   Node<T> *currPosition, *nextPosition;

   currPosition = front;
   while(currPosition != NULL)
   {
      // get address of next node and delete current node
      nextPosition = currPosition->NextNode();
      FreeNode(currPosition);
      currPosition = nextPosition;  // Move to next node
   }
   front = rear = NULL;
   prevPtr = currPtr = NULL;
   size = 0;
   position = -1;
}

template <class T>
LinkedList<T>::~LinkedList(void)
{
   ClearList();
}

template <class T>
LinkedList<T>& LinkedList<T>::operator=
               (const LinkedList<T>& L)
{
   if (this == &L)      // Can't assign list to itself
      return *this;

   ClearList();
   CopyList(L);
   return *this;
}

template <class T>
int LinkedList<T>::ListSize(void) const
{
   return size;
}
                     
template <class T>
int LinkedList<T>::ListEmpty(void) const
{
   return size == 0;
}

// move prevPtr and currPtr forward one node
template <class T>
void LinkedList<T>::Next(void)
{
   // if traversal has reached the end of the list or
   // the list is empty, just return
   if (currPtr != NULL)
   {
      // advance the two pointers one node forward
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
      position++;
   }
}

// True if the client has traversed the list
template <class T>
int LinkedList<T>::EndOfList(void) const
{
   return currPtr == NULL;
}

// return the position of the current node
template <class T>
int LinkedList<T>::CurrentPosition(void) const
{
   return position;
}

// reset the list position to pos
template <class T>
void LinkedList<T>::Reset(int pos)
{
   int startPos;
   
   // if the list is empty, return
   if (front == NULL)
      return;
     
   // if the position is invalid, terminate the program
   if (pos < 0 || pos > size-1)
   {
      cerr << "Reset: Invalid list position: " << pos
           << endl;
      return;
   }
   
   // move list traversal mechanism to node pos
   if(pos == 0)
   {
      // reset to front of the list
      prevPtr = NULL;
      currPtr = front;
      position = 0;
   }
   else
   // reset currPtr, prevPtr, and position
   {
       currPtr = front->NextNode();
       prevPtr = front;
       startPos = 1;
         // move right until position == pos
         for(position=startPos; position != pos; position++)
         {
             // move both traversal pointers forward
             prevPtr = currPtr;
             currPtr = currPtr->NextNode();
      }
   }
}

// return a reference to the data value in the current node
template <class T>
T& LinkedList<T>::Data(void)
{
   // error if list is empty or traversal completed
   if (size == 0 || currPtr == NULL)
   {
      cerr << "Data: invalid reference!" << endl;
      exit(1);
   }
   return currPtr->data;
}

// Insert item at front of list
template <class T>
void LinkedList<T>::InsertFront(const T& item)
{
   // call Reset if the list is not empty
   if (front != NULL)
      Reset();
   InsertAt(item);        // inserts at front
}

// Insert item at rear of list
template <class T>
void LinkedList<T>::InsertRear(const T& item)
{
   Node<T> *newNode;
   
   prevPtr = rear;
   newNode = GetNode(item);      // create the new node
   if (rear == NULL)                        // if list empty, insert at front
      front = rear = newNode;
   else
   {
      rear->InsertAfter(newNode);
      rear = newNode;
   }
   currPtr = rear;
   position = size;
   size++;
}

// Insert item at the current list position
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{
   Node<T> *newNode;

   // two cases: inserting at the front or inside the list
   if (prevPtr == NULL)
   {
      // inserting at the front of the list. also places
      // node into an empty list
      newNode = GetNode(item,front);
      front = newNode;
   }
   else
   {
      // inserting inside the list. place node after prevPtr
      newNode = GetNode(item);
      prevPtr->InsertAfter(newNode);
   }
   
   // if prevPtr == rear, we are inserting into empty list
   // or at rear of non-empty list; update rear and position
   if (prevPtr == rear)
   {
      rear = newNode;
      position = size;
   }

   // update currPtr and increment the list size
   currPtr = newNode;
   size++;              // increment list size
}

// Insert item after the current list position
template <class T>
void LinkedList<T>::InsertAfter(const T& item)
{
   Node<T> *p;

   p = GetNode(item);
   if (front == NULL)       // inserting into an empty list
   {
      front = currPtr = rear = p;
      position = 0;
   }
   else
   {
      // inserting after last node of list
      if (currPtr == NULL)
        currPtr = prevPtr;
      currPtr->InsertAfter(p);
      if (currPtr == rear)
      {
        rear = p;
        position = size;
      }
      else
            position++;
      prevPtr = currPtr;
      currPtr = p;
   }
   size++;              // increment list size
}

// Delete the node at the front of list
template <class T>
T LinkedList<T>::DeleteFront(void)
{
   T item;

   Reset();
   if (front == NULL)
   {
      cerr << "Invalid deletion!" << endl;
      exit(1);
   }
   item = currPtr->data;
   DeleteAt();
   return item;
}

// Delete the node at the current list position    
template <class T>
void LinkedList<T>::DeleteAt(void)
{
   Node<T> *p;

   // error if empty list or at end of list
   if (currPtr == NULL)
   {
      cerr << "Invalid deletion!" << endl;
      exit(1);
   }
   
   // deletion must occur at front node or inside the list
   if (prevPtr == NULL)
   {
      // save address of front and unlink it. if this
      // is the last node, front becomes NULL
      p = front;
      front = front->NextNode();
   }
   else
      // unlink interior node after prevPtr. save address
      p = prevPtr->DeleteAfter();
     
   // if rear is deleted, new rear is prevPtr and position
   // is decremented; otherwise, position is the same
   // if p was last node, rear = NULL and position = -1
   if (p == rear)
   {
      rear = prevPtr;
      position--;
   }
       
   // move currPtr past deleted node. if p is last node
   // in the list, currPtr becomes NULL
   currPtr = p->NextNode();
   
   // free the node and decrement the list size
   FreeNode(p);
   size--;
}

#endif  // LINKEDLIST_CLASS
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
Suggested Courses

807 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question