Doubly Linked List Help

Question

lancevo3 0 Junior Poster

15 Years Ago

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/CS340/Assign/as01340f09.html

#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*/

c++

6 Contributors
16 Replies
510 Views
1 Month Discussion Span
Latest Post 15 Years Ago Latest Post by native

Protuberance 67 Junior Poster in Training

15 Years Ago

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

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.

Lerner 582 Nearly a Posting Maven

15 Years Ago

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.

GDICommander 54 Posting Whiz in Training

15 Years Ago

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.

Protuberance 67 Junior Poster in Training

15 Years Ago

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?
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

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

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.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

lancevo3 0 Junior Poster · Answer 1 · 2009-09-03T02:58:55+00:00

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.

cout << "list 2 (size " << list2.size() << "): " << list2 << endl << endl;

lancevo3 0 Junior Poster · Answer 2 · 2009-09-03T07:10:40+00:00

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?

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

Lerner 582 Nearly a Posting Maven · Answer 3 · 2009-09-04T01:16:43+00:00

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

//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;
     }
  }
}

lancevo3 0 Junior Poster · Answer 4 · 2009-09-05T11:42:24+00:00

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?

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;
      }

Sky Diploma 571 Practically a Posting Shark · Answer 5 · 2009-09-05T12:47:01+00:00

firstly,

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

while(p1 != NULL and p2 != NULL)

Changed to

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.

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

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

lancevo3 0 Junior Poster · Answer 6 · 2009-09-05T21:32:03+00:00

Got that equality operator working thanks for the assistance. My very last problem I am facing is with my less than operator everything tests as less than which its not suppose to obviously.

template <class T>
      bool List<T>::operator<(const List<T>& rightOp) const
      {
      LNode<T>* p1;
      LNode<T>* p2;
      
      p1 = this->head;
      p2 = rightOp.head;
      
      while(p1 != NULL &&p2 != NULL)
      {
             if(p1->data < p2->data)
                         return true;
             if(p1->data > p2->data)
                         return false;
      p1 = p1->next;
      p2 = p2->next;
      }
      if(p2 == NULL)
            return false;
      else
            return true;
      }

Lerner 582 Nearly a Posting Maven · Answer 7 · 2009-09-06T10:18:00+00:00

If code compiles but doesn't provide the response you expect then run time debugging is what's called for. Either learn to use a debugger----many IDEs come with one built in or you can download one if you don't have an IDE that has it's own----OR-----toss in well placed output statements, program flags and program pauses to out put results of desired variables on the fly and that you are where you think you are with each step of the function/loop; and be sure to remove the debugging code before deploying the final project. In this case I'd first put code in to display the lists being compared. If you have the correct lists then I'd display the values of p1->data and p2->data each time through the while loop to be sure you're getting the right values compared.

Sky Diploma 571 Practically a Posting Shark · Answer 8 · 2009-09-06T18:07:48+00:00

What your function in the while loop does is that

if the first element in the lhs is greater than the second element it returns true. Or else it returns false.

Which is not what you actually want. So, Though the syntax is alright, your code is logically incorrect.

So Now, Try to analyse, what exactly you wish to do?

I am actually confused on how you wish to see whether a particular List is greater than another List.

Try to analyse the algorithm to get to the solution.

lancevo3 0 Junior Poster · Answer 9 · 2009-09-07T09:05:54+00:00

For some reason I am not seeing it. Don't I want to check that both pointers are NULL? That way I enter the while loop when something is in the list. When in the loop I check if the data in p1 is LESS than the data in p2 and since thats what I was testing for that would return true? Or if p1 is greater than p2 i return false? Then advance the list?

Ah I just don't know what I'm missing logically I keep looking at it and I just can't seem to put my finger on it.

lancevo3 0 Junior Poster · Answer 10 · 2009-09-07T21:34:02+00:00

lancevo3 0 Junior Poster

15 Years Ago

still no luck

Sky Diploma 571 Practically a Posting Shark · Answer 11 · 2009-09-07T22:20:08+00:00

Well, Here's an approach.

Firstly you will start up with the starting elements check if both of them are equal, if they are equal move to the next element and check the same condition.

If they are not equal, then you could check if the next element is lesser or larger than its counterpart in the other list.

if it is lesser, return true, else return false.
Keep in mind that if list is equal . then it would return false.

By, that you could try to implement the solution :)

native 0 Newbie Poster · Answer 12 · 2009-10-11T21:11:49+00:00

am nelson
please am working on a link list and am having lot of problem. please help