Segmentation faults on Linked Lists. (Please help!!)

Hi guys,

I'm kind of new here and I have a massive problem. :( I was hoping anyone is willing to rescue a damsel in distress...

I've defined a linked list using a template which does the basics of a FIFO Queue. When value enters, I basically just add the value to the back of the queue, etc, etc. (No sorting, whatsoever)

I've tried this using a small set of values (about 10 of them) and nothing goes wrong. However, when I input this into my main program(which is thousands and thousands of lines), all I get is the words free(): invalid pointer ****** Segmentation fault

Did I miss out anything in the linked list? Or did I actually initialise something to a null by accident? Or do I have null pointers all over the place? Or is there "unfreed" nodes dangling all over the place when I extracted the nodes and didn't really take it in mind? It was running fine for weeks and then this happens and I'm just ready to sit here and cry.

I also defined the list in the constructor classes as:

List<double>Queue0;
List<double>Queue1;

and my main function calls the list by Queue0.insert(value). I actually input ALOT of values, I checked and I actually have about 7000 inserts in 5 seconds, and I sometimes run the program for 100 seconds.

Is there anyone who can help? I will be forever grateful to that person.

Or is there any other suggestions on other things I can use to store my values and get them out later? I'm half thinking of using file streams because I'm just so desperate already.

Thanks so much.

This is the linkedlist.h file which seems to be the one giving me the segmentation faults.

Code:

---


#ifndef LIST_H
#define LIST_H

template <class X> struct elem { //structure of node, as it is a queuing system, each node has only next pointer
        X data; //queueid
        elem *next;
       
        elem (X d=0, elem *n=0) : data(d), next(n) {};
};

template <class X> class List {
        protected:
                elem<X> *head, *tail;
        public:
                List(): head(0), tail(0) {}; //initialization of both head pointers to be null.
       
        //function prototypes
       
        void insert(X el) { //From SCPQenqueue(), the queueid and the instantaneous arrival time is recorded
               
                elem<X> *tmp=new elem<X>(el,0); //New node created with instantaneous arrival time..
       
                if (head==0 && tail==0) { //Linked List is empty
                        tail = head = tmp;
                       
                }       
                        else {
                                tmp->data=el;
                                tmp->next=0;
                       
                                //if (isEmpty(head))
                                if (head == 0)
                                        head=tmp;
                                else
                                        tail->next=tmp;
                               
                                tail=tmp;
                        }
        };
       
        X get_data() { //Obtaining the data from the head node pointer - node in head of queue.
                if(head != 0)
                        return head->data;
                else
                        return 0;
        };
       
        void extract() { //extracts from the list the head of queue - packet to be dequeued
                if (head!=0) {
                        if(head->next!=0) {
                                elem<X> *tmp_head=head->next;
                                delete head;
                                head=tmp_head;
                        }
                       
                        else { //only head in the list
                                delete head;
                                head=0;
                                tail=0;
                        }
                }
        };
};
       
#endif

---

I don't see anything wrong with your code, but you are missing a deconstructor.

You don't need this code here

Code:

---

tmp->data=el;
tmp->next=0;

---

because you've already initilized it with

Code:

---

elem<X> *tmp=new elem<X>(el,0);

---

You also don't need

Code:

---

if (head == 0)

---

because every time you set head to 0, tail is also set to zero. So your first if statement will be executed.

The semi-colons( ; ) are not required the way you defined your member functions.

Thanks so much.. ;o) but really sorry for my ignorance, how do I define a deconstructor? Is it what's causing the free(): invalid pointer problem? I don't even use free() in my program at all..

It could be causing the problem.

To define the deconstructor it ~YourClassName();. If you're going to be using the class in inheritance you should use virtual ~YourClassName(); so that the deconstructor is called from inherited classes.

The deconstructors will be called automatically when the object is out of scope. If you use malloc or new to assign a new object to a pointer, it will need to freed up manually.

In your case the deconstructor will look like:

Code:

---

~List(){
/*
You must step through your linkedlinst deleting each node.
*/
}

---