Solved

linked list question for nietod

Posted on 2000-03-09
6
166 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
Comment Utility
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
Comment Utility
meant to be an answer.
0
 

Author Comment

by:scottd1978
Comment Utility
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> 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
Comment Utility
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
Comment Utility
>> 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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

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…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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.

744 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now