DaniWeb Forum Index > Software Development > C++

C++ RSS

Doubly Linked List Help

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Feb 2009

Posts: 136

Reputation: lancevo3 is an unknown quantity at this point

Solved Threads: 0

lancevo3

Offline

Junior Poster

Doubly Linked List Help

Sep 2nd, 2009

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

 Help with Code Tags 
 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*/

•

Join Date: Aug 2009

Posts: 66

Reputation: Protuberance will become famous soon enough

Solved Threads: 14

Protuberance Protuberance is offline

Offline

Junior Poster in Training

Re: Doubly Linked List Help

Sep 2nd, 2009

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

 Help with Code Tags 
 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.

"If a problem can be decided - it is not needed to worry, and if to decide it is impossible - worrying is useless." (с)

•

Join Date: Feb 2009

Posts: 136

Reputation: lancevo3 is an unknown quantity at this point

Solved Threads: 0

lancevo3

Offline

Junior Poster

Re: Doubly Linked List Help

Sep 2nd, 2009

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.

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

•

Join Date: Jul 2005

Posts: 1,699

Reputation: Lerner is a name known to all

Solved Threads: 272

Lerner

Offline

Posting Virtuoso

Re: Doubly Linked List Help

Sep 2nd, 2009

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.

Klatu Barada Nikto

•

Join Date: Jun 2008

Posts: 147

Reputation: GDICommander is an unknown quantity at this point

Solved Threads: 19

GDICommander GDICommander is offline

Offline

Junior Poster

Re: Doubly Linked List Help

Sep 2nd, 2009

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.

•

Join Date: Feb 2009

Posts: 136

Reputation: lancevo3 is an unknown quantity at this point

Solved Threads: 0

lancevo3

Offline

Junior Poster

Re: Doubly Linked List Help

Sep 2nd, 2009

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?

 Help with Code Tags 
 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;
      }

•

Join Date: Aug 2009

Posts: 66

Reputation: Protuberance will become famous soon enough

Solved Threads: 14

Protuberance Protuberance is offline

Offline

Junior Poster in Training

Re: Doubly Linked List Help

Sep 3rd, 2009

•

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?
Help with Code Tags

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

 Help with Code Tags 
 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

 Help with Code Tags 
 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.

"If a problem can be decided - it is not needed to worry, and if to decide it is impossible - worrying is useless." (с)

•

Join Date: Jul 2005

Posts: 1,699

Reputation: Lerner is a name known to all

Solved Threads: 272

Lerner

Offline

Posting Virtuoso

Re: Doubly Linked List Help

Sep 3rd, 2009

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

 Help with Code Tags 
 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;
     }
  }
}

Klatu Barada Nikto

•

Join Date: Feb 2009

Posts: 136

Reputation: lancevo3 is an unknown quantity at this point

Solved Threads: 0

lancevo3

Offline

Junior Poster

Re: Doubly Linked List Help

Sep 5th, 2009

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?

 Help with Code Tags 
 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;
      }

•

Join Date: Mar 2008

Posts: 675

Reputation: Sky Diploma is a splendid one to behold

Solved Threads: 100

Sky Diploma Sky Diploma is offline

Offline

Practically a Master Poster

Re: Doubly Linked List Help

#10

Sep 5th, 2009

firstly,

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

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
      while(p1 != NULL and p2 != NULL)
      while(p1 != NULL and p2 != NULL)

Changed to

 Help with Code Tags 
 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.

Help with Code Tags

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

 Help with Code Tags 
 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

1. Please Mark Your Thread as Solved After Getting Your Answers.
2. Please Use CODE TAGS .

Quick Reply to Thread

Show Printable Version

Similar Threads

PHP Doubly Linked List (PHP)
Doubly Linked List Problem (C++)
doubly linked list--- help needed1 (C++)
To create contact manager using doubly linked list(c++) (C++)
"doubly linked list" question (C)
How Can I Sort a Doubly Linked List Queue? (C)
Need Help to Print Doubly Linked List(DLL) (Java)
doubly linked list implementation (Java)

Other Threads in the C++ Forum

Previous Thread: link list
Next Thread: Problem Setting up Variables for Program

Thread Tools	Search this Thread
Show Printable Version Email this Page

DaniWeb Message

Cancel Changes