Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

linked list question for nietod

Posted on 2000-03-09
6
Medium Priority
?
172 Views
Last Modified: 2010-04-02
Hello,
  I'm working on my linked list for the objects again, and I've come across another stump.  For some reason when adding and item, I cannot set the tail->next field.  It gives me a segmentation fault.  Have a lookie at the code again.  The problem is the add method.

     1  #ifndef LIST_CXX
     2  #define LIST_CXX
     3  #include <iostream.h>
     4  #include <stdlib.h>
     5  #include "list.h"
     6  #include "/home/mud/classes/object/object.cpp"
     7
     8  template<class T>
     9  List<T>::List()
    10  {
    11          head = NULL;
    12          tail = NULL;
    13  }
    14
    15  template<class T>
    16  List<T>::~List()
    17  {
    18          Node<T>* p;
    19
    20          if(head != NULL)
    21          {
    22                  while(head->next != NULL)
    23                  {
    24                          p = head->next;
    25                          delete head;
    26                          head = p;
    27                  }
    28          }
    29          delete head;
    30  }
    31
    32  template<class T>
    33  void List<T>::add(T new_item)
    34  {
    35          // create an instance of the object
    36          T new_obj(new_item);
    37
    38          // create a node pointer
    39          Node<T>* p;
    40
    41          // create an empty node
    42          p = new Node<T>;
    43
    44          if(head == NULL)
    45          {
    46                  p->item = new_obj;
    47                  p->next = tail;
    48                  head = p;
    49          }
    50          else
    51          {
    52                  p->item = new_obj;
    53                  p->next = NULL;
    54                  // FIGURE OUT WHY THIS DOESN'T WORK
    55                  tail->next = p;
    56                  tail = p;
    57          }
    58
    59  }
    60
    61  template<class T>
    62  void List<T>::kill(int x)
    63  {
    64          Node<T>* p;
    65          Node<T>* q;
    66
    67          p = head;
    68
    69          if(head->item.getNum() == x)
    70          {
    71                  head = head->next;
    72          }
    73          else
    74          {
    75                  while(p->item.getNum() != x)
    76                  {
    77                          q = p;
    78                          p = p->next;
    79                  }
    80
    81                  q->next = p->next;
    82          }
    83
    84          delete p;
    85
    86  }
    87
    88  #endif // LIST_CXX
0
Comment
Question by:scottd1978
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 2
6 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 2600823
I don't remember the previous time.  Actualy I don't remember which--linked list questions probably come up twice a week.

 template<class T>
33  void List<T>::add(T new_item)
34  {
35          // create an instance of the object
// Why are you doing this?  What do you need new_obj for?
// it is a copy of new_item, just use new item instead.
36          T new_obj(new_item);
                    37
                    38          // create a node pointer
                    39          Node<T>* p;
                    40
                    41          // create an empty node
                    42          p = new Node<T>;
                    43
                    44          if(head == NULL)
                    45          {
// Note here you copy new_obj which was a copy of new_item.
//Just copy the original.  i.e don't copy  new_obj, copy new_item.
                    46                  p->item = new_obj;
                    47                  p->next = tail;
// Youdon't set tail here.
                    48                  head = p;
                    49          }
                    50          else
                    51          {
                    52                  p->item = new_obj;
                    53                  p->next = NULL;
                    54                  // FIGURE OUT WHY THIS DOESN'T WORK
// tail was never set to anything the first time something was added.
                    55                  tail->next = p;
                    56                  tail = p;
                    57          }
0
 
LVL 22

Accepted Solution

by:
nietod earned 100 total points
ID: 2600826
meant to be an answer.
0
 

Author Comment

by:scottd1978
ID: 2601288
Ok, I was being a dummy ... that statement to create the new_obj was supposed to create an object that I defined.  I wanted to pass an integer, not an object.  I added another if else statement to handle the second addition which I put in the tail.  Let me know if this is good practice or not.    

     1  #ifndef OBJ_LIST
     2  #define OBJ_LIST
     3  #include <iostream.h>
     4  #include "list.h"
     1  #ifndef LIST_CXX
     2  #define LIST_CXX
     3  #include <iostream.h>
     4  #include <stdlib.h>
     5  #include "list.h"
     6  #include "/home/mud/classes/object/object.cpp"
     7
     8  template<class T>
     9  List<T>::List()
    10  {
    11          head = NULL;
    12          tail = NULL;
    13  }
    14
    15  template<class T>
    16  List<T>::~List()
    17  {
    18          Node<T>* p;
    19
    20          if(head != NULL)
    21          {
    22                  while(head->next != NULL)
    23                  {
    24                          p = head->next;
    25                          delete head;
    26                          head = p;
    27                  }
    28          }
    29          delete head;
    30  }
    31
    32  template<class T>
    33  void List<T>::add(int new_item)
    34  {
    35          // create an instance of the object
    36          T new_obj(new_item);
    37
    38          // create a node pointer
    39          Node<T>* p;
    40
    41          // create an empty node
    42          p = new Node<T>;
    43
    44          if(head == NULL)
    45          {
    46                  p->item = new_obj;
    47                  p->next = tail;
    48                  head = p;
    49          }
    50          else if(tail == NULL)
    51          {
    52                  p->item = new_obj;
    53                  p->next = NULL;
    54                  tail = p;
    55          }
    56          else
    57          {
    58                  p->item = new_obj;
    59                  p->next = NULL;
    60                  tail->next = p;
    61                  tail = p;
    62          }
    63
    64  }
    65
    66  template<class T>
    67  void List<T>::kill(int x)
    68  {
    69          Node<T>* p;
    70          Node<T>* q;
    71
    72          p = head;
    73
    74          if(head->item.getNum() == x)
    75          {
    76                  head = head->next;
    77          }
    78          else
    79          {
    80                  while(p->item.getNum() != x)
    81                  {
    82                          q = p;
    83                          p = p->next;
    84                  }
    85
    86                  q->next = p->next;
    87          }
    88
    89          delete p;
    90
    91  }
    92
    93  #endif // LIST_CXX
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 22

Expert Comment

by:nietod
ID: 2601403
>> was supposed to create an object that I
>> defined.  I wanted to pass an integer, not
>> an object
Why?  Usually you woudl pass the object to be added to the list.  (Or at least a copy of the object would be added to the list.)  Now you are passing an int.  What is the relationship between an int and the data to be added?  What if it is a list of strings.  How do you know aht string to add when the int is 1?  What it is 2?

>> 35          // create an instance of the object
>> 36          T new_obj(new_item);
You still have new_obj and don't need it for anything.  new_obj won't be stored in the list.  new_obj is a local variable that is stored in in the add() function's scope.  when add ends new_obj is destroyed.  But the data added to the list continues to exist.  So new_obj isn't beign stored in the list.  A copy of new_obj is being stored in the list.  so your orignal code was to copy new_item to new_obj then copy new_obj into the node.  So you had an unneded copy.  You could just copy newItem into the node.  Now you have.... a mess.

when the list is empty, head AND tail will be NULL.  When there are items in the list head and tail will both be NOT NULL  (They may be the same, they may be different, but they will both not be NULL.)  So head and tail are NULL at the same time or NOT-NULL at the same time.

In

44          if(head == NULL)
45          {
46                  p->item = new_obj;
47                  p->next = tail;
48                  head = p;
49          }
50          else if(tail == NULL)
51          {
52                  p->item = new_obj;
53                  p->next = NULL;
54                  tail = p;
55          }

if the list starts out empty, head and tail will be NULL.  When you add the first item head will get set, but tail is still NULL.  So you broke the rule I said above.  things get worse.  When you add the 2nd item head is not NULL but tail is so tail gets sets.  But the new that HEAD points to doesn't point to this new item.  So now there are two items in the list, but the list isn't linked.  i.e the first item doesn't point the second.

Rule 1: If list is empty head and tail are NULL
Rule 2: if list is not empty.  head points to first item, tail points to last.  The first and last items may be the same item (when one item is in the list.
Rule 3: Each item in the list contains a pointer to the next item in the list.  The last item in the list contain a NULL next pointer.  This last item will also be the first item when the list contains 1 item.  Tail will point to this last item.

These rules are called invarients.  You need to develop rules like this whenever you create a design.  then you must make sure yoru software enforces them at all times.  It may violate them for short periods when it is doing some work.  i.e like while you add an item to the list, it might violate the rules but once the add has been compled the rules should apply again.  In essence, you should be able to say that whenever a procedure is called the rules will hold and when the procedure returns the rules will hold.
0
 

Author Comment

by:scottd1978
ID: 2602080
Ok, I should have told you that this class is only going to be for about 8 objects(classes) that I've defined, and it is going to be specialized towards them.  I will rename it when I'm done.  This means that it will never take a string type.  The int that I'm passing is going to be sent to a database query in the object that get's created.  I changed a few things that you told me to if you want to check out what I have now.  Also, am I going to be able to create a list of type MyType within the MyType class??

check out the revamped code:
(pay no attention to the lack of comments ... the comment fairy will be here soon)

     1  #ifndef LIST_CXX
     2  #define LIST_CXX
     3  #include <iostream.h>
     4  #include <stdlib.h>
     5  #include "list.h"
     6  #include "/home/mud/classes/object/object.cpp"
     7
     8  template<class T>
     9  List<T>::List()
    10  {
    11          head = NULL;
    12          tail = NULL;
    13  }
    14
    15  template<class T>
    16  List<T>::~List()
    17  {
    18          Node<T>* p;
    19
    20          if(head != NULL)
    21          {
    22                  while(head->next != NULL)
    23                  {
    24                          p = head->next;
    25                          delete head;
    26                          head = p;
    27                  }
    28          }
    29          delete head;
    30  }
    31
    32  template<class T>
    33  void List<T>::add(int new_item)
    34  {
    35          // create an instance of the object
    36          T new_obj(new_item);
    37
    38          // create a node pointer
    39          Node<T>* p;
    40
    41          // create an empty node
    42          p = new Node<T>;
    43
    44          if(head == NULL)
    45          {
    46                  p->item = new_obj;
    47                  p->next = tail;
    48                  head = p;
    49                  tail = head;
    50          }
    51          else
    52          {
    53                  p->item = new_obj;
    54                  p->next = NULL;
    55                  tail->next = p;
    56                  tail = p;
    57          }
    58  }
    59
    60  template<class T>
    61  void List<T>::kill(int x)
    62  {
    63          Node<T>* p;
    64          Node<T>* q;
    65
    66          int temp;
    67
    68          p = head;
    69
    70          temp = p->item.getNum();
    71
    72          if(x == temp)
    73          {
    74                  head = head->next;
    75          }
    76          else
    77          {
    78                  while(x != temp)
    79                  {
    80                          q = p;
    81                          p = p->next;
    82
    83                          temp = p->item.getNum();
    84                  }
    85
    86                  q->next = p->next;
    87          }
    88
    89          delete p;
    90
    91  }
    92
    93  template<class T>
    94  void List<T>::print()
    95  {
    96          Node<T>* p;
    97
    98          p = head;
    99
   100          while(p)
   101          {
   102                  p->item.getDesc();
   103                  p = p->next;
   104          }
   105  }
   106
   107  #endif // LIST_CXX
0
 
LVL 22

Expert Comment

by:nietod
ID: 2602181
>> The int that I'm passing is going to be sent
>> to a database query in the object that get's
>> created.
Would have been good to know.  :-)

Add should work fine now, but can be simplified.

You know that the last item in the list will always have a next pointer set to NULL.  You code does this, but it is unclear how.  For example when the list is empty, it sets the new item's next pointer to tail, and tail should be NULL so it does set the next pointer to NULL, but that fact is hard to see.  Instead make it clearer.   explicitly set net to NULL  before the if().  Then you will easily see that it is set correctly.  (Also the two lines within the if() that set next won't be needed.)

Also the statement that sets the "item" in the node appears in both parts of the if, this can also be moved before the if too.

The destructor seems to work correctly, but it can be simplified too.  You don't need that outer if() at all.
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
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.
Suggested Courses

610 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