Solved

Double Link List

Posted on 1998-12-01
3
260 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 200 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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

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…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

747 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now