Dynamic Array in C, using Linked Lists. 
Author Message
 Dynamic Array in C, using Linked Lists.

Quote:

> I need to implement a dynamic array using linked lists.  I have searched
for
>info on this topic throughout the postings and responses and in the FAQ,
but
>can't seem to find what I am looking for.  I understand how to implement
>arrays and linked lists and also how to use malloc, but I can not figure
out
>how to put these things together to make an accessible dynamic array. I
have
>found much info on using pointers to implement a dynamic array, but nothing
>regarding linked lists.  I have set up an array of structures but it is a
>fixed array.  I don't know how to make it dynamic.  Also I need to be able
to
>add and delete structures from the list and determine the current array
size.
> I am very confused. Any info or guidance on this would be greatly
>appreciated. This is not for a C course, but it is part of a distance
>learning lesson on Data Structures and I can not move on to the next lesson
>until I figure this out.

I put together the following to improve my understanding of malloc,
realloc, and free. You might find it useful. Think of C1 as holding a
dynamic configuration and S1 as structures which represent a
configuration item.
------------------
Rick Smith

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

typedef struct
{
    int d1;
    char * ch1;

Quote:
}S1;

typedef struct
{
    size_t s1_limit;
    size_t s1_current;
    S1 ** s1; /* pointer to dynamic array of pointers to stuctures */

Quote:
}C1;

C1 * c1;
char ch[2];

S1 * new_S1 ( int i );
S1 * free_S1 ( S1 * st );

int main ( void )
{
size_t i;

/* allocate C1 */
c1 = malloc ( sizeof *c1 );
if ( c1 == NULL )
{
  fprintf( stdout, "c1 = malloc, in main\n" );
  fgets( ch, 2, stdin );
  exit( EXIT_FAILURE );

Quote:
}

/* get size of array of pointers to S1 */
c1->s1_limit = 100000;
c1->s1_current = 1000; /* initial allocation */

/* allocate pointer to array of pointers */
c1->s1 = malloc( sizeof (S1 *) * c1->s1_current );
if ( c1->s1 == NULL )
{
  fprintf( stdout, "c1->s1 = malloc, in main\n" );
  fgets( ch, 2, stdin );
  exit( EXIT_FAILURE );

Quote:
}

/* fill S1 */
for ( i=0; i < c1->s1_limit; i++ )
{
  S1 * tp;
  S1 ** ap;
  if ( i < c1->s1_current ) ; /* fine do nothing*/
  else
  { /* allocate more array pointers */
   if ( c1->s1_current < c1->s1_limit )
   {
    c1->s1_current += 1000; /* increase allocation size */
    ap = realloc( c1->s1, sizeof (S1 *) * c1->s1_current );
    if ( ap != NULL )
     c1->s1 = ap;
    else
    {
     fprintf( stdout, "c1->s1 = realloc, in main\n" );
     fgets( ch, 2, stdin );
     exit( EXIT_FAILURE );
    }
   }
   else
   {
    fprintf( stdout, "reached array limit in main\n" );
    fgets( ch, 2, stdin );
    exit( EXIT_FAILURE );
   }
  }
  tp = new_S1( i + 1 );
  if ( tp == NULL )
  {
   c1->s1[i] = NULL;
   fprintf( stdout, "Out of memory at %d records\n", i );
   fgets( ch, 2, stdin );
   break;
  }
  else
  {
   c1->s1[i] = tp;
  }
  if ( ( ( i + 1 ) % 10000 ) == 0 ) /* printing every 10000 added */
  {
   fprintf( stdout, "%7d\n", i + 1 );
  }

Quote:
}

/* print the contents */
for ( i=0; (i < c1->s1_limit) && (c1->s1[i] != NULL); i++ )
{
  /* print the record */ /* restriction to every 10000 added */
  if ( ( ( i + 1 ) % 10000 ) == 0 )
  {
   fprintf( stdout, "%7d, %s\n", c1->s1[i]->d1, c1->s1[i]->ch1 );
  }
  /* free the record */
  c1->s1[i] = free_S1( c1->s1[i] );
Quote:
}

fprintf( stdout, "%7d\n", i );
fflush( stdout );
fgets( ch, 2, stdin );

/* free the rest */
free( c1->s1 );
free( c1 );
return 0;

Quote:
}

S1 * new_S1 ( int i )
{
S1 * tp = malloc( sizeof *tp );
char * s = malloc( 30 );
if ( tp != NULL )
{
  tp->d1 = i;
  if ( s != NULL )
  {
   strcpy( s, "abcdefg" );
   tp->ch1 = s;
  }
  else
  {
   free( tp );
   tp = NULL;
  }

Quote:
}
return tp;
}

S1 * free_S1 ( S1 * st )
{
free( st->ch1 );
free( st );
return NULL;

- Show quoted text -

Quote:
}



Thu, 18 Jan 2001 03:00:00 GMT  
 Dynamic Array in C, using Linked Lists.

Quote:

> I need to implement a dynamic array using linked lists.

Tell us what you mean by a dynamic array, what operations need to be
supported and give some idea of how efficient these need to be. It could
well be that a linked list is not appropriate for what you want.

Quote:
> I have searched for
>info on this topic throughout the postings and responses and in the FAQ, but
>can't seem to find what I am looking for.

It isn't really a C language issue, rather a datastructures an algorithms
issue. A newsgroiup such as comp.programming may well be more appropriate.

Quote:
> I understand how to implement
>arrays and linked lists and also how to use malloc, but I can not figure out
>how to put these things together to make an accessible dynamic array. I have
>found much info on using pointers to implement a dynamic array, but nothing
>regarding linked lists.  I have set up an array of structures but it is a
>fixed array.  I don't know how to make it dynamic.  Also I need to be able to
>add and delete structures from the list and determine the current array size.

Have you considered using malloc and realloc? If these don't meet your needs
you need to explain more clearly what your needs are.

Quote:
> I am very confused. Any info or guidance on this would be greatly
>appreciated. This is not for a C course, but it is part of a distance
>learning lesson on Data Structures and I can not move on to the next lesson
>until I figure this out.

Even if you are just answering a homework assignment which asks you
to build a dynamic array using a linked list it should be instructive
and helpful to consider the issues raised here. Once you have a better
idea of what you want that should point more clearly to a way to implement
it.

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


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



Thu, 18 Jan 2001 03:00:00 GMT  
 Dynamic Array in C, using Linked Lists.
Quote:

>  I need to implement a dynamic array using linked lists.

[snip]

A dynamic array is an array that varies its capacity during run-time.
Arrays declared using the definition:
 {type} name[MAX_SIZE];

result in an allocation of MAX_SIZE elements of the given type, no more,
no less.

Dynamic arrays are useful when you don't know what the capacity is going
to be during run-time.  Dynamic arrays can be created using "malloc()"
or by using another data type such as a linked list.  When using a data
type to implement a dynamic array, you must provide access routines as
well as allocation routines.

A dynamic array can be implemented using a linked list.  The operation
"array[4]" would traverse the list to the 4th element.

Just remember some issues / operations that the linked list needs to
provide:
Removal -- (erase the element or remove it from the list)
Boundary Conditions (using an array index that is out of range)
Expanding the capacity.

--
Thomas Matthews



Fri, 19 Jan 2001 03:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Linked List using dynamic memory allocation (URGENT request for example)

2. dynamic linked list + dynamic struct members

3. Lists VS. Dynamic Arrays VS. Re-defining Arrays

4. link list of a linked list (chained links?)

5. Help Please!(linked lists/dynamic memory allocation etc.)

6. Seg Fault || Dynamic Linked Lists || ISSUES

7. Dynamic Memory Allocation and Linked Lists

8. Using array index in array initialization list's

9. Array pointing to Dynamic list thingie

10. Incompatible NULL Assignments || Linked List inside Linked List

11. Clearing Memory || Linked List INSIDE of a Linked List

12. Freeing a Linked List inside of a Linked List

 

 
Powered by phpBB® Forum Software