Ad:

C++ Discussion Thread
Unsolved
Views: 2070

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Sep 2nd, 2009

Doubly Linked List Help

Expand Post »

I am working on a doubly linked list assignment for my class and I am getting a segmentation fault on my test for the copy constructor. I don't know if the problem lies within my copyList method or my copy constructor logic. Any assistance be great.

Here is my header file and link to the assignment.
http://turing.cs.niu.edu/~t90kjm1/CS...s01340f09.html

C++ Syntax (Toggle Plain Text)
#ifndef LIST_H
#define LIST_H
 
#include <iostream>
 
template <class T>
class List;
 
template <class T>
std::ostream& operator<<(std::ostream&, const List<T>&);
 
template <class T>
struct LNode
       {
       T data;
       LNode<T>* prev;
       LNode<T>* next;
 
       LNode(const T&);
       };
 
       template <class T>
       LNode<T>::LNode(const T& newdata)
       {
       data = newdata;
       prev = next = NULL;
       }
 
template <class T>
class List
      {
      friend std::ostream& operator<< <>(std::ostream&, const List<T>&);
 
      private:
              LNode<T>* head;
              LNode<T>* tail;
      public:
             List();
             ~List();
             List(const List<T>&);
             LNode<T>* copyList(LNode<T>*);
             List<T>& operator=(const List<T>&);
             void clear();
             int size() const;
             bool empty() const;
             const T& front() const;
             T& front();
             const T& back() const;
             T& back();
             void push_front(const T&);
             void push_back(const T&);
             void pop_front();
             void pop_back();
             bool operator==(const List<T>&) const;
             bool operator<(const List<T>&) const;
      };
 
      template <class T>
      List<T>::List()
      {
      head = NULL;
      tail = NULL;
      }
 
      template <class T>
      List<T>::~List()
      {
      clear();
      }
 
      template <class T>
      List<T>::List(const List<T>& oldList)
      {
      head = copyList(oldList.head);
      tail = copyList(oldList.tail);
      }
 
      template <class T>
      LNode<T>* List<T>::copyList(LNode<T>* ptr)
      {
      LNode<T>* newNode;
 
      if(ptr==NULL)
          return NULL;
      else
          {
          newNode = new LNode<T>(ptr->data);
          newNode->prev = copyList(ptr->prev);
          newNode->next = copyList(ptr->next);
          }
      return newNode;
      }
 
      template <class T>
      List<T>& List<T>::operator=(const List<T>& rightOp)
      {
	  if (this != &rightOp)
         {
         clear();
         head = copyList(rightOp.head);
         tail = copyList(rightOp.tail);
         }	
      return *this;
      }
 
      template <class T>
      void List<T>::clear()
      {
      while(!empty())
          pop_front();
      }
 
      template <class T>
      int List<T>::size() const
      {
      LNode<T>* ptr = head;
      int count = 0;
 
      while(ptr != NULL)
      {
      	count++;
	ptr = ptr->next;
      }
      return count;
      }      
 
      template <class T>
      bool List<T>::empty() const
      {
      if(head == NULL or tail == NULL)
          return true;
      else
          return false;
      }
 
      template <class T>
      const T& List<T>::front() const
      {
      return head->data;
      }
 
      template <class T>
      T& List<T>::front()
      {
      return head->data;
      }
 
      template <class T>
      const T& List<T>::back() const
      {
      return tail->data;
      }
 
      template <class T>
      T& List<T>::back()
      {
      return tail->data;
      }
 
      template <class T>
      void List<T>::push_front(const T& item)
      {
      LNode<T>* newNode;
 
      if(!empty())
            {
            newNode->prev = NULL;
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
            }
      else
            {
            newNode->prev = NULL;
            newNode->next = head;
            tail = newNode;
            head = newNode;
            }
      }
 
      template <class T>
      void List<T>::push_back(const T& item)
      {
      LNode<T>* newNode;
      newNode = new LNode<T>(item);      
 
      newNode->next = NULL;
      newNode->prev = tail;
      if(empty())
	    head = newNode;
      else
            tail->next = newNode;
      tail = newNode;
      }
 
      template <class T>
      void List<T>::pop_front()
      {
      if(size() > 1)
            {
            LNode<T>* delNode = head;
            head = delNode->next;
            head->prev = NULL;
            delete delNode;
            }
      if(size() == 1)
            {
            LNode<T>* delNode = head;
            head = delNode->next;
            tail = NULL;
            delete delNode;
            }
      }
 
      template <class T>
      void List<T>::pop_back()
      {
      if(size() > 1)
            {
            LNode<T>* delNode = tail;
            tail = delNode->prev;
            tail->next = NULL;
            delete delNode;
            }
      if(size() == 1)
            {
            LNode<T>* delNode = tail;
            tail = delNode->prev;
            head = NULL;
            delete delNode;
            }
      }
 
      template <class T>
      bool List<T>::operator==(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;
 
      while(p1 != NULL and p2 != NULL)
            {
            if(p1->data != p2->data)
                        return false;
            }
      if(p1 == NULL and p2 == NULL)
            return true;
      else
            return false;
      }
 
      template <class T>
      bool List<T>::operator<(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;
 
      while(p1 != NULL and p2 != NULL)
      {
             if(p1->data < p2->data)
                         return true;
             if(p1->data > p2->data)
                         return false;
      }
      if(p2 == NULL)
            return false;
      else
            return true;
      }
 
      template <class T>
      std::ostream& operator<<(std::ostream& leftOp, const List<T>& rightOp)
      {
      LNode<T>* current;
 
      for (current=rightOp.head; current != NULL; current = current->next)
		std::cout << current->data << " ";
	  return leftOp;
      }
#endif /*LIST_H*/
#ifndef LIST_H
#define LIST_H

#include <iostream>

template <class T>
class List;

template <class T>
std::ostream& operator<<(std::ostream&, const List<T>&);

template <class T>
struct LNode
       {
       T data;
       LNode<T>* prev;
       LNode<T>* next;
       
       LNode(const T&);
       };
       
       template <class T>
       LNode<T>::LNode(const T& newdata)
       {
       data = newdata;
       prev = next = NULL;
       }
       
template <class T>
class List
      {
      friend std::ostream& operator<< <>(std::ostream&, const List<T>&);
      
      private:
              LNode<T>* head;
              LNode<T>* tail;
      public:
             List();
             ~List();
             List(const List<T>&);
             LNode<T>* copyList(LNode<T>*);
             List<T>& operator=(const List<T>&);
             void clear();
             int size() const;
             bool empty() const;
             const T& front() const;
             T& front();
             const T& back() const;
             T& back();
             void push_front(const T&);
             void push_back(const T&);
             void pop_front();
             void pop_back();
             bool operator==(const List<T>&) const;
             bool operator<(const List<T>&) const;
      };
      
      template <class T>
      List<T>::List()
      {
      head = NULL;
      tail = NULL;
      }
      
      template <class T>
      List<T>::~List()
      {
      clear();
      }
      
      template <class T>
      List<T>::List(const List<T>& oldList)
      {
      head = copyList(oldList.head);
      tail = copyList(oldList.tail);
      }
      
      template <class T>
      LNode<T>* List<T>::copyList(LNode<T>* ptr)
      {
      LNode<T>* newNode;
      
      if(ptr==NULL)
          return NULL;
      else
          {
          newNode = new LNode<T>(ptr->data);
          newNode->prev = copyList(ptr->prev);
          newNode->next = copyList(ptr->next);
          }
      return newNode;
      }
      
      template <class T>
      List<T>& List<T>::operator=(const List<T>& rightOp)
      {
	  if (this != &rightOp)
         {
         clear();
         head = copyList(rightOp.head);
         tail = copyList(rightOp.tail);
         }	
      return *this;
      }
      
      template <class T>
      void List<T>::clear()
      {
      while(!empty())
          pop_front();
      }
      
      template <class T>
      int List<T>::size() const
      {
      LNode<T>* ptr = head;
      int count = 0;

      while(ptr != NULL)
      {
      	count++;
	ptr = ptr->next;
      }
      return count;
      }      
                         
      template <class T>
      bool List<T>::empty() const
      {
      if(head == NULL or tail == NULL)
          return true;
      else
          return false;
      }
      
      template <class T>
      const T& List<T>::front() const
      {
      return head->data;
      }
      
      template <class T>
      T& List<T>::front()
      {
      return head->data;
      }
      
      template <class T>
      const T& List<T>::back() const
      {
      return tail->data;
      }
      
      template <class T>
      T& List<T>::back()
      {
      return tail->data;
      }
      
      template <class T>
      void List<T>::push_front(const T& item)
      {
      LNode<T>* newNode;
      
      if(!empty())
            {
            newNode->prev = NULL;
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
            }
      else
            {
            newNode->prev = NULL;
            newNode->next = head;
            tail = newNode;
            head = newNode;
            }
      }
      
      template <class T>
      void List<T>::push_back(const T& item)
      {
      LNode<T>* newNode;
      newNode = new LNode<T>(item);      

      newNode->next = NULL;
      newNode->prev = tail;
      if(empty())
	    head = newNode;
      else
            tail->next = newNode;
      tail = newNode;
      }
      
      template <class T>
      void List<T>::pop_front()
      {
      if(size() > 1)
            {
            LNode<T>* delNode = head;
            head = delNode->next;
            head->prev = NULL;
            delete delNode;
            }
      if(size() == 1)
            {
            LNode<T>* delNode = head;
            head = delNode->next;
            tail = NULL;
            delete delNode;
            }
      }
      
      template <class T>
      void List<T>::pop_back()
      {
      if(size() > 1)
            {
            LNode<T>* delNode = tail;
            tail = delNode->prev;
            tail->next = NULL;
            delete delNode;
            }
      if(size() == 1)
            {
            LNode<T>* delNode = tail;
            tail = delNode->prev;
            head = NULL;
            delete delNode;
            }
      }
      
      template <class T>
      bool List<T>::operator==(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;
      
      while(p1 != NULL and p2 != NULL)
            {
            if(p1->data != p2->data)
                        return false;
            }
      if(p1 == NULL and p2 == NULL)
            return true;
      else
            return false;
      }
      
      template <class T>
      bool List<T>::operator<(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;
      
      while(p1 != NULL and p2 != NULL)
      {
             if(p1->data < p2->data)
                         return true;
             if(p1->data > p2->data)
                         return false;
      }
      if(p2 == NULL)
            return false;
      else
            return true;
      }
      
      template <class T>
      std::ostream& operator<<(std::ostream& leftOp, const List<T>& rightOp)
      {
      LNode<T>* current;
	
      for (current=rightOp.head; current != NULL; current = current->next)
		std::cout << current->data << " ";
	  return leftOp;
      }
#endif /*LIST_H*/

Similar Threads

PHP Doubly Linked List in PHP
Doubly Linked List Problem in C++
doubly linked list--- help needed1 in C++
To create contact manager using doubly linked list(c++) in C++
"doubly linked list" question in C

lancevo3

Reputation Points: 10

Solved Threads: 0

Junior Poster

Offline

146 posts
since Feb 2009

Permalink

Sep 2nd, 2009

Re: Doubly Linked List Help

I dont understand why you use copyList method for just copying two pointers...
For copying one list to another you must copy head and tail pointers.
So your copy constructror will be like this

cpp Syntax (Toggle Plain Text)
template <class T>
      List<T>::List(const List<T>& oldList)
      {
         this->head = oldList.head;
         this->tail = oldList.tail;
      }
template <class T>
      List<T>::List(const List<T>& oldList)
      {
         this->head = oldList.head;
         this->tail = oldList.tail;
      }

And another one - c++ does not have "and" operator. Just use "&&" operator

P.S. I advise to clean "copyList" method. He can be replaced assignment of head and tail pointers.

Last edited by Protuberance; Sep 2nd, 2009 at 4:37 pm.

Protuberance

Reputation Points: 78

Solved Threads: 17

Junior Poster in Training

Offline

88 posts
since Aug 2009

Permalink

Sep 2nd, 2009

Re: Doubly Linked List Help

I went ahead and updated my copy consturctor as you said and that worked great, thank you!

On this part of my output I am getting an error:

Testing clear() of non-empty list...
list 1 (size 0):
list 2 (size 4): 0 32178176 32178208 32178240

The error is with the list 2.

This is the code from the driver for that line.

C++ Syntax (Toggle Plain Text)
 cout << "list 2 (size " << list2.size() << "): " << list2 << endl << endl;
 cout << "list 2 (size " << list2.size() << "): " << list2 << endl << endl;

lancevo3

Reputation Points: 10

Solved Threads: 0

Junior Poster

Offline

146 posts
since Feb 2009

Permalink

Sep 2nd, 2009

Re: Doubly Linked List Help

I recommend you think twice about simple copying of head and tail pointers to copy one list to another. This is called shallow copy and works okay in simple programs but it can quickly cause problems if you aren't aware of what is happening. In particular, under this scenario if either list is deleted then the other list is useless because there is now no longer any place in memory to point to.

I recommend doing hard copy within the copy constructor, copy function. That way each list has it's own memory, even if it contains the same information.

Don't try to copy an empty list. If the list to copy is empty, then return from the function/constructor.

Lerner

Reputation Points: 718

Solved Threads: 373

Nearly a Posting Maven

Offline

2,253 posts
since Jul 2005

Permalink

Sep 2nd, 2009

Re: Doubly Linked List Help

If your operator=() works, extract the code that creates a new list with the one provided as a parameter and use it in your copy constructor. Search for the refactoring tip Extract Method.

Last edited by GDICommander; Sep 2nd, 2009 at 7:48 pm.

GDICommander

Reputation Points: 72

Solved Threads: 26

Posting Whiz in Training

Offline

209 posts
since Jun 2008

Permalink

Sep 2nd, 2009

Re: Doubly Linked List Help

I tried the copy constructor posted and its giving me a program crash this just doesn't look right to me either any ideas whats up with it?

C++ Syntax (Toggle Plain Text)
      template <class T>
      List<T>::List(const List<T>& oldList)
      {
      this->head = oldList.head;
      this->tail = oldList.tail;
      }
      template <class T>
      List<T>::List(const List<T>& oldList)
      {
      this->head = oldList.head;
      this->tail = oldList.tail;
      }

lancevo3

Reputation Points: 10

Solved Threads: 0

Junior Poster

Offline

146 posts
since Feb 2009

Permalink

Sep 3rd, 2009

Re: Doubly Linked List Help

Click to Expand / Collapse Quote originally posted by lancevo3 ...

I tried the copy constructor posted and its giving me a program crash this just doesn't look right to me either any ideas whats up with it?
C++ Syntax (Toggle Plain Text)
      template <class T>
      List<T>::List(const List<T>& oldList)
      {
      this->head = oldList.head;
      this->tail = oldList.tail;
      }
template <class T> List<T>::List(const List<T>& oldList) { this->head = oldList.head; this->tail = oldList.tail; }

What kind of error did you get?
AV(Access Violation)
Exception
Segmentation fault
?

If you don't try to copy an empty list, that code works correctly.
For empty list just place condition before assignment

cpp Syntax (Toggle Plain Text)
 template <class T>
      List<T>::List(const List<T>& oldList)
      {
         if(!oldList.isEmpty())
         {
            this->head = oldList.head;
            this->tail = oldList.tail;
         }
         else
                throw "Empty list";
      }
 
//isEmpty method
template <class T>
bool List<T>::isEmpty() const
{
    return head == NULL;
}
 template <class T>
      List<T>::List(const List<T>& oldList)
      {
         if(!oldList.isEmpty())
         {
            this->head = oldList.head;
            this->tail = oldList.tail;
         }
         else
                throw "Empty list";
      }

//isEmpty method
template <class T>
bool List<T>::isEmpty() const
{
    return head == NULL;
}

Or if you wanna copy list, then delete it, then use copy method. Like that

cpp Syntax (Toggle Plain Text)
template <class T>
void List<T>::copyList(const List<T> &source)
{
   //condition for empty list
   LNode<T> *source_head_temp = source.head;
   while(source_head_temp)
   {
        push_back(source_head_temp->data);
        source_head_temp = source_head_temp->next;
   }
}
template <class T>
void List<T>::copyList(const List<T> &source)
{
   //condition for empty list
   LNode<T> *source_head_temp = source.head;
   while(source_head_temp)
   {
        push_back(source_head_temp->data);
        source_head_temp = source_head_temp->next;
   }
}

I hope it helps you.

Protuberance

Reputation Points: 78

Solved Threads: 17

Junior Poster in Training

Offline

88 posts
since Aug 2009

Permalink

Sep 3rd, 2009

Re: Doubly Linked List Help

Mock up copy constructor. Code untested. I'm comfortable with the logic and the comments. Adjustable to your needs as desired.

C++ Syntax (Toggle Plain Text)
//use deep copy protocol to copy rhs into a new List using a copy constructor. 
//type Node is used to create type List. 
//List is doubly linked
//List always adds to the end
List(const List & rhs)
{
   if(rhs.count == 0)  //rhs is empty, so assign default values to new List member variables
   {
      count = 0;
      firstNode = NULL;
      lastNode = NULL;
   }
   else
   {
       //declare a Node to run rhs, start with first node in rhs.
       Node * current = rhs.firstNode;
 
       //assign default values to member variables of new List
       count = 0;
       firstNode = lastNode = NULL;
 
       //use a loop to copy data from rhs into new List one Node at a time
      while(current != NULL)
      {
         //create a new Node to enter into the new List
         Node newNode = new Node;
         newNode->prev = NULL;
         newNode->next = NULL;
         newNode->data = current->data;
 
         //add new Node to new List
         if(count == 0) //new list is empty
           firstNode = lastNode = newNode;
         else //add new Node to end of new List
         {
           lastNode->next = newNode;
           newNode->prev = lastNode;
           lastNode = lastNode->next;
         } 
 
         //increment count and get next node in rhs to copy into new List
         ++count;
         current = current->next;
     }
  }
}
//use deep copy protocol to copy rhs into a new List using a copy constructor. 
//type Node is used to create type List. 
//List is doubly linked
//List always adds to the end
List(const List & rhs)
{
   if(rhs.count == 0)  //rhs is empty, so assign default values to new List member variables
   {
      count = 0;
      firstNode = NULL;
      lastNode = NULL;
   }
   else
   {
       //declare a Node to run rhs, start with first node in rhs.
       Node * current = rhs.firstNode;
       
       //assign default values to member variables of new List
       count = 0;
       firstNode = lastNode = NULL;

       //use a loop to copy data from rhs into new List one Node at a time
      while(current != NULL)
      {
         //create a new Node to enter into the new List
         Node newNode = new Node;
         newNode->prev = NULL;
         newNode->next = NULL;
         newNode->data = current->data;
       
         //add new Node to new List
         if(count == 0) //new list is empty
           firstNode = lastNode = newNode;
         else //add new Node to end of new List
         {
           lastNode->next = newNode;
           newNode->prev = lastNode;
           lastNode = lastNode->next;
         } 
         
         //increment count and get next node in rhs to copy into new List
         ++count;
         current = current->next;
     }
  }
}

Lerner

Reputation Points: 718

Solved Threads: 373

Nearly a Posting Maven

Offline

2,253 posts
since Jul 2005

Permalink

Sep 5th, 2009

Re: Doubly Linked List Help

I been able to get this list going for the most part but I am getting a segmentation fault and I believe its being caused by my equality operator, I though I had everything coded right. Any thoughts?

C++ Syntax (Toggle Plain Text)
      template <class T>
      bool List<T>::operator==(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;
 
      while(p1 != NULL and p2 != NULL)
            {
            if(p1->data != p2->data)
                        return false;
            }
      if(p1 == NULL and p2 == NULL)
            return true;
      else
            return false;
      }
      template <class T>
      bool List<T>::operator==(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;

      while(p1 != NULL and p2 != NULL)
            {
            if(p1->data != p2->data)
                        return false;
            }
      if(p1 == NULL and p2 == NULL)
            return true;
      else
            return false;
      }

lancevo3

Reputation Points: 10

Solved Threads: 0

Junior Poster

Offline

146 posts
since Feb 2009

Permalink

Sep 5th, 2009

Re: Doubly Linked List Help

firstly,

logical and in C++ is represented by '&&' so you will need to have.

C++ Syntax (Toggle Plain Text)
      while(p1 != NULL and p2 != NULL)
      while(p1 != NULL and p2 != NULL)

Changed to

C++ Syntax (Toggle Plain Text)
      while(p1 != NULL && p2 != NULL)
      while(p1 != NULL && p2 != NULL)

The same applies to the if loop below as well.

Secondly, Your Logical error is that you make 2 nodes p1 and p2, but donot assign any location for them to point to.

So it goes on looping infinitely i guess.

you should instead do something like this.

C++ Syntax (Toggle Plain Text)

p1= this-> head;
p2= rightOp.head;

Then let it go through the while loop and. During the while loop checks you will need to move to the next position to.

so

C++ Syntax (Toggle Plain Text)
      while(p1 != NULL and p2 != NULL)
            {
            if(p1->data != p2->data)
                        return false;
 
            p1= p1->next;
            p2= p2->next;
}
return true;
      while(p1 != NULL and p2 != NULL)
            {
            if(p1->data != p2->data)
                        return false;
            
            p1= p1->next;
            p2= p2->next;
}
return true;

Last edited by Sky Diploma; Sep 5th, 2009 at 3:49 am. Reason: Code corrections

Sky Diploma

Reputation Points: 673

Solved Threads: 125

Practically a Posting Shark

Offline

818 posts
since Mar 2008

Page 1
2
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: link list

Next Thread in C++ Forum Timeline: Problem Setting up Variables for Program

DaniWeb Message

Cancel Changes

User Name
Password