dynamic list of structures

[irwa82]

Hi,

I am new to C and created a list of structures linked together with
pointers. But I am wondering how you create a list if you don't have a
fixed number of entries. like if you had an address book you may not
know how many entries are there etc.

here is some sample code of my fix sized list:

#include <stdio.h>
#include <stddef.h>

int main(void) {
struct sTest {
int number;
struct sTest *next;
} s1, s2, s3, s4, s5, *sPointer;

sPointer = &s1;

s1.next = &s2;
s2.next = &s3;
s3.next = &s4;
s4.next = &s5;
s5.next = (struct sTest *) NULL;

s1.number = 15;
s2.number = 25;
s3.number = 35;
s4.number = 45;
s5.number = 55;

while (sPointer != (struct sTest *) NULL) {
printf("%i\n", sPointer->number);
sPointer = sPointer->next;
}

return 0;
}

 

[Bartc]

Hi,

I am new to C and created a list of structures linked together with
pointers. But I am wondering how you create a list if you don't have a
fixed number of entries. like if you had an address book you may not
know how many entries are there etc.

here is some sample code of my fix sized list:

#include <stdio.h>
#include <stddef.h>

int main(void) {
struct sTest {
int number;
struct sTest *next;
} s1, s2, s3, s4, s5, *sPointer;

sPointer = &s1;

s1.next = &s2;
s2.next = &s3;
s3.next = &s4;
s4.next = &s5;
s5.next = (struct sTest *) NULL;

s1.number = 15;
s2.number = 25;
s3.number = 35;
s4.number = 45;
s5.number = 55;

while (sPointer != (struct sTest *) NULL) {
printf("%i\n", sPointer->number);
sPointer = sPointer->next;
}

return 0;
}

Your code is not easily scaleable (imagine 5000 nodes). Proper linked list
code has already been posted, but it might be useful to look at code only
slightly modified from yours. The following uses an array as storage for the
nodes, instead of naming individual nodes:

#define SIZE 5

int main(void) {
struct sTest {
int number;
struct sTest *next;
} sarray[SIZE]={0}, *sPointer;
int i;

sPointer = &sarray[0];

for (i=0; i<SIZE-1; ++i)
sarray.next = & sarray[i+1];
sarray[SIZE-1].next = NULL; /* Already NULL but just in case..
*/

for (i=0; i<SIZE; ++i)
sarray.number = i*10+15;

while (sPointer != (struct sTest *) NULL) {
printf("%i\n", sPointer->number);
sPointer = sPointer->next;
}
return 0;
}

Now you can change the number of nodes very easily. The SIZE nodes are
allocated here consecutively in elements 0 to SIZE-1 of the array, but could
be in any order.

 

[CBFalconer]

I am new to C and created a list of structures linked together
with pointers. But I am wondering how you create a list if you
don't have a fixed number of entries. like if you had an address
book you may not know how many entries are there etc.

You create a node:

typedef struct node {
struct node *next;
void *data;
} *node;

and an empty list:

node list = NULL;

Now you can write all your list manipulation code, not caring about
what the data pointer holds. The addition to the list will malloc
a suitable pointer for the data, copy the data into there, malloc a
"struct node", and set the *data pointer. The code to insert that
into the list will do:

node addtolisthead(void *new) {
node p;

if (!(p = malloc(sizeof *p))) return NULL; /* failure */
p->next = list;
p->data = new;
list = p;
return p; /* non-NULL, success */
}

Note how easily you can alter this so that list is no longer a
global. Note that addtolisthead doesn't need to know anything
about the data.