12 Replies - 1840 Views - Last Post: 01 April 2010 - 05:08 AM Rate Topic: -----

#1 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Segmentation fault in double linked list

Posted 01 April 2010 - 02:49 AM

I am getting segmentation fault in double linked list in pop_front and pop_back() function. Here is the two codes :
pop_front() :
void pop_front(List *list) {
        Node *temp;
        
        if (!size(list)) {
                printf("\n  List is empty.\n");
                exit(0);
        }
        
        temp = list->head;
        list->head = list->head->next;
        list->head->prev = NULL;
        free(temp);
        list->size--;
}

pop_back() :
void pop_back(List *list) {
        Node *temp;
        
        if (!size(list)) {
                printf("\n  List is empty.\n");
                exit(0);
        }
        
        temp = list->tail;
        list->tail = list->tail->prev;
        list->tail->next = NULL;
        free(temp);
        list->size--;
}

The structures are :
typedef long long int data_type;

typedef struct NodeStruct {
        struct NodeStruct *prev;
        data_type data;
        struct NodeStruct *next;
} Node;

typedef struct ListStruct{
        Node *head;
        Node *tail;
        size_t size;
} List;


And main() function is :
#include <stdio.h>
#include "list.h"


int main() {
	List list;
	data_type i;
	system("clear");
	set_list(&list);
        
        for (i = 1; i <= 10; i++) {
		push_back(&list, i);
	}
	
	display_forward(&list);
	printf("\n  Size : %u\n", size(&list));
	display_backward(&list);
	printf("\n");		
	
	for (i = 1; i <= 10; i++) {
		pop_front(&list);
	}
	return 0;
}

If needed I will provide the other functions used in main().
Output :
1 2 3 4 5 6 7 8 9 10 
  Size : 10
10 9 8 7 6 5 4 3 2 1 
Segmentation fault



Is This A Good Question/Topic? 0
  • +

Replies To: Segmentation fault in double linked list

#2 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 03:02 AM

I have also added this module in the pop_front() and pop_back() function :
if (!list->size) {
                set_list(list);
        }

But same result.
The set_list() function is :
void set_list(List *list) {
        list->head = NULL;
        list->tail = NULL;
        list->size = 0;
}

Was This Post Helpful? 0
  • +
  • -

#3 citus  Icon User is offline

  • D.I.C Head

Reputation: 16
  • View blog
  • Posts: 140
  • Joined: 28-March 10

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 03:50 AM

I admit that I don't know much about vectors, linked lists, or their functions, but I have a few ideas that might help you out. In your code
        for (i = 1; i <= 10; i++) {
                push_back(&list, i);
        }


Is that a legal call to push_back? I thought it only took one parameter. Also, I don't see you calling pop_back() anywhere in that code. I will try to research it more and see if I can come up with anything.
Was This Post Helpful? 1
  • +
  • -

#4 gregoryH  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 60
  • View blog
  • Posts: 656
  • Joined: 04-October 06

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:05 AM

Hi Tapas

Your going great guns with your work. Lists are always a little pesky but you appear to be on the right track

Have you thought about the actual error? It only happens when you execute your code, right?

Segementation faults might be caused because you haven't allocated memory for the list object, or... your code can't detect when you have reached the end of the list in the "backward" direction :)

Hope this helps
Was This Post Helpful? 1
  • +
  • -

#5 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:14 AM

The problem is solved : here is pop_back() function :
void pop_back(List *list) {
        Node *temp;
        
        if (!size(list)) {
                printf("\n  List is empty.\n");
                exit(0);
        }

        temp = list->tail;
        
        if (list->size == 1) {
                set_list(list);
        }
        else {
                list->tail = list->tail->prev;
                list->tail->next = NULL;
                list->size--;
        }
        
        free(temp);
}


citus said:

Is that a legal call to push_back? I thought it only took one parameter.

Actually I am writing a header file list.h in C. So this structure is needed there. I am showing you a code :
#include <stdio.h>
#include "list.h"


int main() {
	List list1, list2;
	data_type i;
	system("clear");
	
	set_list(&list1);
	set_list(&list2);
	
	for (i = 1; i <= 10; i++) {
		push_back(&list1, i);
		push_back(&list2, i+i);
	}
	
	printf("\n  This is list1 : "); display_forward(&list1);
	printf("\n");
	printf("\n  This is list2 : "); display_forward(&list2);
	printf("\n");
	
	return 0;
}


View PostgregoryH, on 01 April 2010 - 03:35 PM, said:

you haven't allocated memory for the list object.

I don't understand sir. Please clarify.
Was This Post Helpful? 0
  • +
  • -

#6 citus  Icon User is offline

  • D.I.C Head

Reputation: 16
  • View blog
  • Posts: 140
  • Joined: 28-March 10

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:16 AM

I see, well I'm glad you got it worked out, sorry I could not be of any assistance.
Was This Post Helpful? 1
  • +
  • -

#7 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:21 AM

View Postcitus, on 01 April 2010 - 03:46 PM, said:

I see, well I'm glad you got it worked out, sorry I could not be of any assistance.

Its okay.
Was This Post Helpful? 0
  • +
  • -

#8 gregoryH  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 60
  • View blog
  • Posts: 656
  • Joined: 04-October 06

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:23 AM

View PostTapas Bose, on 01 April 2010 - 08:14 PM, said:

The problem is solved : here is pop_back() function :
Actually I am writing a header file list.h in C. So this structure is needed there. I am showing you a code :

View PostgregoryH, on 01 April 2010 - 03:35 PM, said:

you haven't allocated memory for the list object.

I don't understand sir. Please clarify.

Hi Tapas

Allocation of memory is also known as dynamic memory. in C language memory allocation is done with malloc or calloc calls.

In C++ new and delete.

Have I helped there Tapas?

This post has been edited by gregoryH: 01 April 2010 - 04:44 AM

Was This Post Helpful? 1
  • +
  • -

#9 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:27 AM

View PostgregoryH, on 01 April 2010 - 03:53 PM, said:

Hi Tapas

Allocation of memory is also known as dynamic memory. in C language memory allocation is done with malloc or calloc calls.

In C++ new and delete.

Have I helped there Tapas?

Here is the push_back() function :
void push_back(List *list, data_type data) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        
        if (!newNode) {
                printf("\n  Memory allocation unsuccessful.\n");
                exit(0);
        }
        
        newNode->data = data;
        newNode->next = NULL;
        
        if (!list->head) {
                list->head = newNode;
                newNode->prev = NULL;
        }
        else {
                newNode->prev = list->tail;
                list->tail->next = newNode;
        }

        list->tail = newNode;
        list->size++;                
}

Am I in the right way sir? Please check these two functions : pop_back() and push_back() sir.
Was This Post Helpful? 0
  • +
  • -

#10 gregoryH  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 60
  • View blog
  • Posts: 656
  • Joined: 04-October 06

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 04:47 AM

Hi tapas

I haven't tried to compile that but it looked ok.

you don't actually need to maintain a counter of the list size, when u use the correct code logic you will get automatic indication when to stop (hint - list->tail->next == NULL, or when list->previous == head
Was This Post Helpful? 1
  • +
  • -

#11 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 05:04 AM

I think that the reason behind of my previous pop_back() function was giving error is when the list contain only one node then
    
        temp = list->tail;
        list->tail = list->tail->prev;
        list->tail->next = NULL;
        free(temp);
        list->size--;



makes list->tail = NULL. But list->head remain unchanged. That is why I check whether the list->size is 1 or not if it is true then I call set_list() function, which make reset the list as :
list->head = NULL;
list->tail = NULL;
list->size = 0;


This is also working :
temp = list->head;
        
        if (list->head == list->tail) {
                set_list(list);
        }
        else {
                list->head = list->head->next;
                list->head->prev = NULL;
                list->size--;
        }
        
        free(temp);

Was This Post Helpful? 0
  • +
  • -

#12 tauit_dnmd  Icon User is offline

  • D.I.C Head

Reputation: 8
  • View blog
  • Posts: 129
  • Joined: 25-March 10

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 05:05 AM

i dont think so.
If you want to check whether list is contain any element or not
by:
if(list->phead!=NULL) //list contain >=1 element.
{
//do anythings that you want
}



==>I think you dont understand about Linked List

This post has been edited by tauit_dnmd: 01 April 2010 - 05:07 AM

Was This Post Helpful? 0
  • +
  • -

#13 Tapas Bose  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 23
  • View blog
  • Posts: 472
  • Joined: 09-December 09

Re: Segmentation fault in double linked list

Posted 01 April 2010 - 05:08 AM

I wrote function size() which can determine what is the size of the list at any moment.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1