Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Double Linked List Problem

linked list

  • Please log in to reply
7 replies to this topic

#1 Ennerggie

Ennerggie

    CC Lurker

  • New Member
  • Pip
  • 3 posts

Posted 19 February 2012 - 07:36 AM

Hello, Ive been trying to make this program using double linked lists work, but the "delete" function doesnt work, I am getting segmentation fault.

Inserted list in this case are structures who's variables = 1,2,3,4, respectively. SO the idea is:

1--> <--2 --> <-- 3 --> <--4
(--> is the "next*" pointer, <-- is the "prev*" pointer)

If used to delete 1,2,3, it doesnt give segmentation fault, but it sets the variables within the structures to 0, doesnt delete the structure.
If used to delete the last element (whose variables=4), it gives segmentation fault.

Plz tell me what's wrong / how I could improve / correct the way Im using dynamic lists, etc. All constructive help is greatly apreciated.


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct p{
float x,y,z;
char s;
struct p* next;
struct p* prev;
}DATA;

typedef DATA* LISTA_DATA;

void alloc_data(LISTA_DATA* lista_data, LISTA_DATA prev, float i)
{
	if(*lista_data==NULL)	
	{*lista_data=(LISTA_DATA)malloc(sizeof(DATA));
	if(*lista_data!=NULL)
		{(**lista_data).x=i;
		(**lista_data).y=i;
		(**lista_data).z=i;
		(**lista_data).s='C';
		(**lista_data).next=NULL;
		(**lista_data).prev=prev;
		}
	else
		printf("\nError alocating memory");
	}

	else
		alloc_data(&(**lista_data).next,*lista_data, i);	
}

void initate_data(LISTA_DATA* lista_data)
{	int i=0;
	for(i=0; i<5; i++)
	alloc_data(lista_data, NULL, i);
}

void show_data(LISTA_DATA lista_data)
{
	if(lista_data==NULL)	return;
	
	printf("\n%f %f %f %c\n", (*lista_data).x,(*lista_data).y,(*lista_data).z,(*lista_data).s);
	show_data((*lista_data).next);
}

void delete_data(LISTA_DATA* lista_data, float number)
{
	LISTA_DATA temp=NULL;
	if(*lista_data==NULL)	return;

	else if((**lista_data).x==number)
		{temp=*lista_data;
		if((**lista_data).prev!=NULL)
			{(*(**lista_data).prev).next=(**lista_data).next;}
		if((**lista_data).next!=NULL)
			{(*(**lista_data).next).prev=(**lista_data).prev;}
		if((**lista_data).prev==NULL)
			*lista_data=(**lista_data).next;
		
		
		if(temp!=NULL)
			{free(temp);
			temp=NULL;}			
		}
	else
		if((**lista_data).next!=NULL)	
			delete_data(&(**lista_data).next, number);

}

int main(){

	LISTA_DATA lista_data=NULL;
	
	initate_data(&lista_data);
	show_data(lista_data);

	printf("\n Expected 0 1 2 3 4 3 2 1 0:");
	printf("\n  %.1f  %.1f  %.1f  %.1f  %.1f    %.1f  %.1f  %.1f  %.1f   \n", 
	(*lista_data).x,  
	(*(*lista_data).next).x, 
	(*(*(*lista_data).next).next).x,
	(*(*(*(*lista_data).next).next).next).x,
	(*(*(*(*(*lista_data).next).next).next).next).x,
	(*(*(*(*(*(*lista_data).next).next).next).next).prev).x,
	(*(*(*(*(*(*(*lista_data).next).next).next).next).prev).prev).x,
	(*(*(*(*(*(*(*(*lista_data).next).next).next).next).prev).prev).prev).x,
	(*(*(*(*(*(*(*(*(*lista_data).next).next).next).next).prev).prev).prev).prev).x);

	/*WORKING*/

	printf("\n DATA 0 1 2 3 ");
	delete_data(&lista_data,4);/*segmentation fault*/
	show_data(lista_data); 
	
	/*FRAKKED UP*/


/*	printf("\n DATA 0 1 3 ");
	delete_data(&lista_data,2);
	show_data(lista_data);

	printf("\n DATA 0 3 ");
	delete_data(&lista_data,1);
	show_data(lista_data);

	printf("\n DATA 3 ");
	delete_data(&lista_data,1);
	show_data(lista_data);
*/

free(lista_data);

return 0;
}


(the printf function was to test if the pointers next and prev were working)

Edited by Ennerggie, 20 February 2012 - 05:03 AM.

  • 0

#2 fread

fread

    Programming God

  • Senior Member
  • PipPipPipPipPipPip
  • 897 posts
  • Location:Trinidad and Tobago
  • Learning:C, Java, C++, C#, PHP, Python, PL/SQL

Posted 19 February 2012 - 08:13 AM

This is not a good place to be. It says you lack basic programming concepts
(*lista_data).x,  
    (*(*lista_data).next).x, 
    (*(*(*lista_data).next).next).x,
    (*(*(*(*lista_data).next).next).next).x,
    (*(*(*(*(*lista_data).next).next).next).next).x,
    (*(*(*(*(*(*lista_data).next).next).next).next).pr  ev).x,
    (*(*(*(*(*(*(*lista_data).next).next).next).next).  prev).prev).x,
    (*(*(*(*(*(*(*(*lista_data).next).next).next).next  ).prev).prev).prev).x,
    (*(*(*(*(*(*(*(*(*lista_data).next).next).next).ne  xt).prev).prev).prev).prev).x);

I believe you need a data structures text book and a programming text book. Apart from that, I have re-written to much of the code to call it yours, so I won't post it.
Select the code then click # to format.
  • 0

#3 Ennerggie

Ennerggie

    CC Lurker

  • New Member
  • Pip
  • 3 posts

Posted 20 February 2012 - 05:01 AM

This is not a good place to be. It says you lack basic programming concepts

(*lista_data).x,  
    (*(*lista_data).next).x, 
    (*(*(*lista_data).next).next).x,
    (*(*(*(*lista_data).next).next).next).x,
    (*(*(*(*(*lista_data).next).next).next).next).x,
    (*(*(*(*(*(*lista_data).next).next).next).next).pr  ev).x,
    (*(*(*(*(*(*(*lista_data).next).next).next).next).  prev).prev).x,
    (*(*(*(*(*(*(*(*lista_data).next).next).next).next  ).prev).prev).prev).x,
    (*(*(*(*(*(*(*(*(*lista_data).next).next).next).ne  xt).prev).prev).prev).prev).x);

I believe you need a data structures text book and a programming text book. Apart from that, I have re-written to much of the code to call it yours, so I won't post it.
Select the code then click # to format.



This is the kind of retarded replies that I do not want. If you dont want to help, just dont post anything / leave the thread.

"(the printf function was to test if the pointers next and prev were working)" <-- did you read that? I was using the printf function to check whether the pointers between elements were working)

Youve rewritten too much of the code to call it mine? Do you think Im participating in a contest or anything? Im asking for help and tips, doesnt matter "whose code it is".

Expecting a decent reply from someone else.
  • 0

#4 voral

voral

    CC Regular

  • Member
  • PipPipPip
  • 30 posts

Posted 20 February 2012 - 05:56 AM

Code is strange :)
Line "alloc_data(&(**lista_data).next,*lista_data, i);" not used.

line
for(i=0; i<5; i++)
		alloc_data(lista_data, NULL, i);
work as
		alloc_data(lista_data, NULL, 5);


---------- Post added at 05:56 PM ---------- Previous post was at 05:53 PM ----------

alloc_data(lista_data, NULL, 0);
alloc_data(lista_data, NULL, 1);
alloc_data(lista_data, NULL, 2);
alloc_data(lista_data, NULL, 3);
alloc_data(lista_data, NULL, 4);
Memory leak
  • 0

#5 Flying Dutchman

Flying Dutchman

    CC Leader

  • Expert Member
  • PipPipPipPipPipPipPip
  • 1090 posts
  • Location:::1
  • Programming Language:C++, Python

Posted 20 February 2012 - 12:34 PM

C has -> operator which is equivalent to *(). :
*(lista_data).next == lista_data->next
I think it makes code more readable with -> operator since there aren't that many parentheses.
  • 0

The roots of education are bitter, but the fruit is sweet.


#6 voral

voral

    CC Regular

  • Member
  • PipPipPip
  • 30 posts

Posted 20 February 2012 - 12:52 PM

The code below works. But this is bad code. I'm not sure of your target
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SIZE 5

typedef struct p
{
	float x,y,z;
	char s;
	struct p* next;
	struct p* prev;
} DATA;

typedef DATA* LISTA_DATA;

LISTA_DATA alloc_data(LISTA_DATA prev_data, float i)
{
	DATA* data = (LISTA_DATA)malloc(sizeof(DATA));
	if(data!=NULL)	
	{
		if (prev_data!=NULL) prev_data->next = data;
		data->x=i;
		data->y=i;
		data->z=i;
		data->s='C';
		data->next=NULL;
		data->prev=prev_data;
	}
	else
		printf("Error alocating memory\n");
	return data;
}

LISTA_DATA initate_data()
{
	LISTA_DATA first = NULL;
	LISTA_DATA prev_data = NULL;
	int i;
	for(i=0; i<SIZE; ++i)
	{
		prev_data = alloc_data(prev_data, i);
		if (i==0) first = prev_data;
	}
	return first;
}

void show_data(LISTA_DATA lista_data)
{
	while (lista_data!=NULL)
	{
		printf("%f %f %f %c\n", lista_data->x,lista_data->y,lista_data->z,lista_data->s);
		lista_data = lista_data->next;
	}
}
void show_x(LISTA_DATA lista_data)
{
	while (lista_data!=NULL)
	{
		printf("%f ", lista_data->x);
		lista_data = lista_data->next;
	}
	printf("\n");
}

void delete_data(LISTA_DATA lista_data, float number)
{
	while (lista_data!=NULL)
	{
        if (lista_data->x == number)
		{
			LISTA_DATA temp = lista_data;
			if (temp->prev != NULL)
				temp->prev->next = temp->next;
			if (temp->next != NULL)
				temp->next->prev = temp->prev;
			free(temp);
			return;
		}
		lista_data = lista_data->next;
	}
}
void delete_all(LISTA_DATA lista_data)
{
	while (lista_data!=NULL)
	{
		LISTA_DATA temp = lista_data;
		lista_data = lista_data->next;
		free(temp);
	}
}

int main(){

	LISTA_DATA lista_data = initate_data();
	show_data(lista_data);
	printf("\n");
	show_x(lista_data);
	printf("\n");
	delete_data(lista_data,3);
	show_data(lista_data);
	delete_all(lista_data);
	return 0;
}

  • 0

#7 Ennerggie

Ennerggie

    CC Lurker

  • New Member
  • Pip
  • 3 posts

Posted 20 February 2012 - 01:43 PM

Thanks.

Why is it bad code? What can I improve in the way Im using / building lists? As far as I see:

-In inserting those elements to the list, your functions goes directly to the last element's poitner and adds it to it, that's alot less computationally heavy than my function, which everytime when it's called, goes trough all the list to add the new element, so I can see how that would be better.

- you preffer cicles to recursive functions. Are they computationally lighter?

- are you using simple pointers cause it simplifies synthax and less probably for mistakes to occur?

- Yeah, free(lista_data) wasnt deleting the entire list, while delete_all() function does, thanks.
  • 0

#8 voral

voral

    CC Regular

  • Member
  • PipPipPip
  • 30 posts

Posted 20 February 2012 - 10:21 PM

Why is it bad code?

I've said too strongly :)
1 IMHO. Type LISTA_DATA deceives us:
- This isn't pointer to list. It's pointer to one element.
- Makes the code less readable. DATA* looks better.

2. Function alloc_data is unnecessary in this sample code. It can unite with initate_data(). But it may be useful in more complex cases.
3. If we know the number of items in a list in advance and many of them, it is best to allocate memory for all the right elements. Memory allocation functions are very slow.

- you preffer cicles to recursive functions. Are they computationally lighter?

I think in this case there is no significant difference. With a large number of elements to be excessive consumption of the stack.

- Yeah, free(lista_data) wasnt deleting the entire list, while delete_all() function does, thanks.

I think you are mistaken because the use of type LISTA_DATA. :)

Do you understand me? (My Ebglish is poor :( )
  • 0





Also tagged with one or more of these keywords: linked list

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download