Solved

linked list question for nietod

Posted on 2000-03-09
6
168 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
  • 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 25 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
Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

 
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

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

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

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

825 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