Arrays of linked lists - help!

[hobbsalex]

Hi there,

I'm becoming increasingly confused trying to implement an array of pointers, that themselves point to nodes in a linked list. Basically my problem is that I need to sort through an existing linked list per element, over all other elements (which works fine) based on a particular criterion, and per element create a new linked list that any element in the original linked list that satisfies the criterion is added to. I have chosen to have these new linked lists in an array i.e. an array of linked lists, but am running into trouble owing to my lack of understanding both data types!

As I say, the sorting itself works fine its just the creating of an array of pointers that each point to a new linked list.

The basics of my main() function are as follows:

---------------------------------------------------------------------------------------

node *head = NULL;  //pointer to initial list of particles

  node* list[100];  //array of 100 pointers to nodes

    // For each particle loop over all other particles
    // Use the radius constraint to define neighbour lists

    search_particle_add(&head, &list[particleno], radius);

----------------------------------------------------------------------------------------

The search_particle_add() function takes the following arguments:

int search_particle_add(node **thisptr, node *list[], double rad)

And within the search_particle_add function there is another function that adds the new particle (assuming it satisfies the criterion) to a new linked list (i.e. one of those contained in the array list[]). That function is called in search_particle_add() by:

add_p(&list[i], &iterate->p);

And it is defined by:

node* add_p(node **ptr, struct particle *value)

My problem is either that the array of pointers isn't being created properly, or that particles aren't being added to the various linked lists properly, as when I try and display the contents of the various linked lists in the array list[], there's nothing there, even though quite a few relevant particles were definitely found by the sorting algorithm and the add_p() function was called on them.

Help! I've no doubt used wrong referencing or dereferencing somewhere, but can't figure out where!

Any advice would be appreciated.

Alex

[Narue]

Hmm, let me see if I understand what you're doing. Is it taking a single linked list and splitting it into an array of linked lists based on a certain criteria?

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

struct node {
  int data;
  struct node *next;
};

struct node *push_front ( struct node *head, int data )
{
  struct node *nn = malloc ( sizeof *nn );

  if ( nn != NULL ) {
    nn->data = data;
    nn->next = head;
  }

  return nn;
}

int main ( void )
{
  struct node *head = NULL;
  struct node *a[3] = {0};
  struct node *last;
  struct node *next;
  struct node *it;
  int i;

  for ( i = 0; i < 10; i++ )
    head = push_front ( head, i );

  for ( it = head; it != NULL; it = it->next )
    printf ( "%d ", it->data );

  printf ( "\n" );

  /* Let's start building the array of lists */
  while ( head != NULL ) {
    int index = 0;

    next = head->next;

    if ( head->data >= 0 && head->data < 3 )
      index = 0;
    else if ( head->data >= 3 && head->data < 7 )
      index = 1;
    else
      index = 2;

    head->next = a[index];
    a[index] = head;

    head = next;
  }

  for ( i = 0; i < 3; i++ ) {
    printf ( "a[%d]: ", i );

    for ( it = a[i]; it != NULL; it = it->next )
      printf ( "%d ", it->data );

    printf ( "\n" );
  }

  return 0;
}

[hobbsalex]

Not quite. Your code seems to split an existing linked list into 3 separate linked lists by reassigning the 'next' pointer fields of the nodes. What I need to do is leave the existing linked list intact (as I need to keep looping over it) but for each node within it, create a new linked list. The contents of that new linked list will then be any of the elements in the original list that satisfy a particular condition.

So, I initially create an array of 100 pointers to nodes (I hope!), i.e. list[0], list[1], list[2] etc. then start looping over the original list.

When looping over the original linked list we start at the first node, for which the following operations will be performed:

1) Loop over the rest of the original linked list
2) Check criteria
3) If criteria satisfied then add the node currently being evaluated for criteria to list[0]
4) Continue to loop, go back to 2)

this continues until it gets to the end of the original linked list. We then move to the next element in the original linked list, and the process starts all over again i.e.

1) Loop over the rest of the original linked list
2) Check criteria
3) If criteria satisfied then add the node currently being evaluated for criteria to list[1]
4) Continue to loop, go back to 2)

and so on and so forth. Sorry, I probably haven't explained this very well!

My problem lies I think in the way in which arrays of pointers are created and called as arguments to a function . Although the code compiles, I get a segmentation fault when trying to add nodes to the new lists i.e. list[n].

Alex

[Narue]

>Sorry, I probably haven't explained this very well!
No, I think I understand now.

>I get a segmentation fault when trying to add nodes to the new lists i.e. list[n]
It could be that you're not initializing the array elements (the new lists) to NULL. A segmentation fault with linked lists is almost always due to the list not being terminated with the correct sentinel, which in this case is a null pointer.

[hobbsalex]

Well, yes, that certainly helps in that now I don't get a segmentation fault! However, when printing out the lists i.e. list[0], list[1], list[2] etc. there's nothing in them, and there should be. The lists do seem to be there, however, so I think they are being created properly - it must be my add_p() function that isn't working.

My add_p() function is as follows:

node* add_p(node **ptr, struct particle *value) {
    node *added;
    int i;

    if((added = malloc(sizeof(node))) == NULL) {
	printf("Cannot allocate node\n");
	exit(1);
    }

    added->p.Id = value->Id;
    added->p.Mass = value->Mass;
    
    for(i=0;i<4;i++) {
	added->p.Pos[i] = value->Pos[i];
    }
    for(i=0;i<3;i++) {
	added->p.Vel[i] = value->Vel[i];
    }

    added->next = *ptr;
    (*ptr) = added;
    
    return *ptr;
}

and I call it, within my search_particle_add() function, by doing:

add_p(&list[i], &iterate->p);

Alex

[Narue]

>if((added = malloc(sizeof(node))) == NULL) {
>printf("Cannot allocate node\n");
>exit(1);
>}
Hmm, that's not cool. It's not up to utility code to terminate the program because utility code doesn't know what kind of cleanup and recovery is needed before doing so.

Your add_p function looks fine, by the way.

[hobbsalex]

Right, I've realised that the problem lies soley in returning my array list[] from the function it is updated in. It updates fine within the function, but when I refer to it in the main() section it appears blank. I've been reading about how you generally can't return an array from a function, so this is my problem! I must have to return a pointer to the first element or something, but am not sure how to do this correctly - my search_particle_add function now looks like:

node* search_particle_add(node **thisptr, node *list[], double rad) {
    node *current;
    node *iterate;
    node *arrayhead;

    int totalpn;
    int i;
	
    // Need to work out other particle (pr2) distances from particle pr1
    
    double rdiff[3];
    double d;

    // Search through list to see if particle 2 is within a given radius rad of particle 1, if so then add particle 2 to new list

    i = 0;

    for(current = *thisptr; current != NULL; current = current->next) {
	
	totalpn = 0;
	
	//Point to a new node in the array that will act as a head for a new linked list

	printf("i = %d\n", i);

	arrayhead = list[i] = NULL;

	for(iterate = *thisptr; iterate != NULL; iterate = iterate->next) {
	
	    // Define rdiff = r2-r1 where r1 is particle position

	    rdiff[0] = iterate->p.Pos[1] - current->p.Pos[1];
	    rdiff[1] = iterate->p.Pos[2] - current->p.Pos[2];
	    rdiff[2] = iterate->p.Pos[3] - current->p.Pos[3];

	    d = sqrt(rdiff[0]*rdiff[0] + rdiff[1]*rdiff[1] + rdiff[2]*rdiff[2]);  // Distance between the two particles

	    iterate->p.neighbourdist = d;

	    printf("d = %f\n", d);

	    if(d < rad) {

		printf("Adding particle...\n");

		//Add particle to list[i]
		
		add_p(&arrayhead, &iterate->p);

		(list[i]) = arrayhead;
		
		totalpn = totalpn + 1;
	    }

	}

	print_p(list[i]);

	printf("Number of particles within constraint: %d\n", totalpn);

	i = i + 1;

    }
    return *list;
}

And I call it in my main() function by doing:

search_particle_add(&head, &list[particleno], radius);

Any ideas?

Cheers,
Alex