Singly Linked Circular List

This is a discussion on Singly Linked Circular List within the C++ Programming forums, part of the General Programming Boards category; Ok I'm creating a template class for a singly linked circular list. I was wondering if someone could look it ...

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    109

    Singly Linked Circular List

    Ok I'm creating a template class for a singly linked circular list. I was wondering if someone could look it over and tell me if they see any errors. I had people here go over it and have spotted some but its still not working so if anyone can take a look and let me know it would be greatly appreciated.

    Code:
    #include sclist.h
    
    
    
    sclist::sclist()
    {
    	headPtr = NULL;
    	size = 0;
    }
    
    sclist::~sclist()
    {
    //here need to delete all the nodes and set the headPtr back to NULL
    //and size equal to 0
    
    //temp count variable
    int i;
    
    //loops through starting at the front and uses the RemoveFromHead
    //function to remove all the nodes till none are left at which point
    //the loop is broken and size and headPtr get set back to their
    //starting values of 0 and NULL respectively.
        for(i=1;i <= 5;i++)
    {
    	RemoveFromHead();
    }
        size = 0;
        headPtr = NULL;
    
    }	
    
    template <class T>
    void sclist::InsertAtHead(const T& data)
    {
    //this is a temp pointer that points to the current node
    slnode<T>* currentPtr = new slnode<T>(data);
    
        //if there is nothing in the list
        if(headPtr == NULL)
        {  
            //sets the headPtr of the list to the newly created node
            headPtr = currentPtr;
           
            //since its a circular list the only nodes nextPtr must point to 		
            //itself
            nextPtr = headPtr;
        }
        
        //if there is something in the list
        else if(headPtr != NULL)
    	{
            //it will fist make a new node
            slnode = new slnode<T>(data);
           
            //it will first set the headPtr to the new node
            headPtr = slnode;
           
            //will set the nextPtr of the slnode equal to teh currentPtr
            //so that it will now point to the previous node
            nextPtr = currenPtr;       
        }
            //increments the size
            size++;       
     
    }
    
    template <class T>
    void sclist::InsertAtTail(const T& data)
    {
    //first will walk through size times to get to the correct node then
    //will take that node that has the nextPtr pointing to the head and 
    //set currentPtr equal to that nextPtr. Then it will have that nextPtr
    //point to the new node. Then have the new nodes nextPtr set 
    //equal to the currentPtr.
    
    //temp count variable
    int i;
    
    //check to see if this is the first node in the list being added and if it is
    //the node will just be inserted at the head
    if(headPtr = NULL)
    {
        InsertAtHead();
    }
    else if(headPtr != NULL)
    {
    
    //will set the currentPtr back to headPtr so it starts at the beginning of
    //the list
    
    currentPtr = headPtr;	
    //this for loop will go through chaging what currentPtr is equal to
        for(i=1;i<=size;i++)
        {
        currentPtr = currentPtr->nextPtr;
    	}
    
    //creates a new node with the data in it.
    slnode = new slnode<T>(data);
    
    //set the nextPTr of the new node equal to the currentPtr which will be
    //pointing to the headPtr
    nextPtr = currentPTr;
    
    //sets the last end nodes nextPtr equal to the new node
    nextPtr = slnode;	
    }
    }
    
    //returns a pointer to the node removed from the head of the list
    slnode<T>* sclist::RemoveFromHead()
    {
    //going to have the currentPtr set equal to the headPtr. Then set the headPtr
    //equal to the nextPtr of the node we are removing from the head. Then delete 
    //the currentPtr because it will be pointing to the now unliked node
    
    currentPtr = headPtr;
    headPtr = headPtr->nextPtr;
    delete currentPtr;
    
    }
    
    template <class T>
    //returns a pointer to the node removed from the tail of the list.
    slnode<T>* sclist::RemoveFromTail()
    {
    
    //Walk through the list size number of times.
    //Set up a temp pointer named delete equal to that
    //node. Then walk through the list again but this time size-1 times and
    //set that nodes nextPtr  equal to headPtr.Then delete the delete pointer
    
    //temp count variable
    int i;
    
    //the tempPtr named tempEnd
    T* delete = new delete;
    
    //set currentPtr equal to the head
    delete = head;
    
    //the for loop to walk to the end of the list
    for(i=1;i<=size;i++)
    {
        delete = delete->nextPtr;
    }
    
    //now will go through size-1 times
    for(i=1;i<=size-1;i++)
    {
        currentPtr = currentPtr->nextPtr;
    }
    
    //this leaves the previous tail node unlinked
    nextPtr = headPtr;
    
    //deletes the unlinked node
    delete delete;
    
    
    }
    
    template <class T>
    //true if the list is empty, otherwise false.
    bool sclist::IsEmpty()
    {
    
    //if the headPtr is equal to null then its empty;
    if(headPtr == NULL)
    {
        IsEmpty = true;
    }
    else 
    {
        IsEmpty = false;
    }
    
    }
    
    template <class T>
    //moves headPtr one node forward in the list.
    void sclist::Advance()
    {
    
    //is just advancing one spot so just set currentPtr equal to the nextPtr
    currentPtr = currentPtr->nextPtr;
    
    }
    
    template <class T>
    //returns a pointer to the first node in the list, starting from the head of
    //the list,that contains the indicated data. If the data is not in the list,
    //returns NULL.
    slnode<T>* sclist::Locate(T data)
    {
    
    //will first set currentPtr equal to head. Then it will advance one at a
    //time and check the data to see if it matches the data in the parameter.
    //If not it will continue to move on. A if statement will be used here.
    
    //a temporary counter so that when or if the data is found it will have a 
    //number that will correspond to where in the size it is.
    int count;
    
    if(*currentPtr != data)
    {
        Advance();
        //need an if statement to see if its at the end of the list will compare
        //count to the size if they are equal it will stop and print not found.
        
        if(size = count)
        {
            cout << "Data not found." << endl;
            break;
        }
        count++;
    }
    
    //if the data is found
    else if(*currentPtr == data)
    {
        //will print the count number the data is located at and then break.
        cout << "Data found at node #" << count << endl;
        break;
    }
    
    }
    Last edited by DarkDot; 04-26-2007 at 02:15 PM.

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    What does #include sclist.h look like? For example sclist::Advance() uses a currentPtr, which isn't declared locally, so it must be declared in sclist? And is * overloaded in the scnode class to get at the data, so that this line (if(*currentPtr != data)) works?

  3. #3
    Registered User
    Join Date
    Mar 2007
    Posts
    109
    sclist.h
    Code:
    #ifndef SCLIST_H
    #define SCLIST_H
    
    #include "slnode.h"
    
    template<class T>
    class sclist
    {
        public:
            //default constructor
            sclist();
            
            //deconstructor
            ~sclist();
            
            //inserts a node at the head of the list
            void InsertAtHead(const T&);
    
            //inserts a node at the tail of the list
            void InsertAtTail(const T&);
            
            //returns a pointer to the node removed 
            //from the head of the list	
            slnode<T>* RemoveFromHead();
            
            //returns a pointer to the node removed 
            //from the tail of the list
            slnode<T>* RemoveFromTail();
            
            //true if the list is empty, otherwise false
            bool IsEmpty();
            
            //moves headPtr one node forward in the list
            void Advance();
            
            //returns a pointer to the first node in the list
            //starting from the head of the list, that contains
            //the indicated data. If the data is not in the list, 
            //returns NULL.
            slnode<T>* Locate(T data);
    	
        private:
            T* headPtr;
            int size;
    };
    #include "sclist.template"
    
    #endif

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    If the list is circular, you don't need a tail.
    Code:
        //if there is nothing in the list
        if(headPtr == NULL)
        {  
            //sets the headPtr of the list to the newly created node
            headPtr = currentPtr;
           
            //since its a circular list the only nodes nextPtr must point to 		
            //itself
            nextPtr = headPtr;
        }
        
        //if there is something in the list
        else if(headPtr != NULL)
    	{
            //it will fist make a new node
            slnode = new slnode<T>(data);
    You already know it's not NULL because you just checked for that. No need to do it again.
    Code:
           
            //it will first set the headPtr to the new node
            headPtr = slnode;
    This shouldn't be done until you've fixed up the pointers. You should set "slnode->next = headPtr;" before this.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked List
    By devarishi in forum C Programming
    Replies: 4
    Last Post: 12-24-2008, 12:00 AM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  4. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 07:47 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21