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

  1. #1
    Registered User
    Join Date
    Mar 2005
    Posts
    2

    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
    Last edited by summerrainx; 03-18-2005 at 09:15 PM.

  2. #2
    Registered User KonArtis's Avatar
    Join Date
    Mar 2003
    Posts
    34
    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.

  3. #3
    Registered User
    Join Date
    Mar 2005
    Posts
    2
    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..

  4. #4
    Registered User KonArtis's Avatar
    Join Date
    Mar 2003
    Posts
    34
    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.
    */
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Locating A Segmentation Fault
    By Stack Overflow in forum C Programming
    Replies: 12
    Last Post: 12-14-2004, 01:33 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 11:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM