How would I do this in C?

Question

I'm use to programming in Java but I'm trying to learn C. In Java you have dynamic arrays like an ArrayList to use but in C you don't. How do you make a dynamic array in C that I can insert search and delete stuff? Mostly I just need the insert and search functions for my particular usage. Anyone know? I searched google for an hour but couldn't find anything.

Would a linked list be my best bet?

Answer 1

I suppose you're talking about something like Java's ArrayList class. You absolutely can reproduce this behavior in C, but how to go about it depends on what additional restrictions and functionality you want the data structure to have. For instance, adding a new item to the end of a linked list is really fast (constant time, if you keep a pointer to the end of the list), but searching even a sorted linked list is far slower (linear time) than searching a sorted array (logarithmic time). You have to think about what you need your data structure to do, and how fast, before deciding how to implement it. If you are only ever going to access the list at one end or the other, or by iterating through all of it (and doing something important with each item), then a linked list is good. But if you want to be able to search through a long list very quickly for a specific item, then a linked list is bad.



Here is a simple data structure and set of functions that together essentially work as a basic ArrayList:



typedef struct intal

{

int size;

int len;

int* list;

} intal;



intal* new_intal()

{

intal* r=malloc(sizeof(intal));

r->size=1;

r->len=0;

r->list=malloc(sizeof(int));

return r;

}



void add(intal* thisal,int toadd)

{

if(thisal->len>=thisal->size)

{

int newsize=2*thisal->size;

int* newlist=malloc(newsize*sizeof(int));

int i=0;

while(isize)

{

newlist[i]=thisal->list[i];

i++;

}

thisal->size=newsize;

free(thisal->list);

thisal->list=newlist;

}

thisal->list[thisal->len]=toadd;

thisal->len=thisal->len+1;

}



int remove(intal* thisal,int check)

{

int found=0;

int i=0;

while(ilen)

{

if(thisal->list[i]==check)

{

found=1;

break;

}

i++;

}

if(found)

{

thisal->len=thisal->len-1;

while(ilen)

{

thisal->list[i]=thisal->list[i+1];

i++;

}

}

return found;

}



int geterror;



int get(intal* thisal,int index)

{

geterror=0;

if(index>0 && indexlen)

{

return thisal->list[index];

}

geterror=1;

return 0;

}



The add() and remove() functions are fairly self-explanatory. The remove() function returns 1 if a matching integer was found and removed, and 0 otherwise. The get() function is a little harder to use, since its return value provides no indication of whether the function succeeded. In order to check whether it succeeded, you have to check geterror, which on completion of the get() call will be 0 if the call succeeded and 1 if it failed. For instance, one might have code that looks like the following:



int tenthitem=get(somelist,9);

if(geterror)

{

//do something appropriate to the error

}

else

{

//do something with tenthitem

}



I have not actually tested any of the above code, so I can't guarantee that it works. However, you can at least see what is going on in principle here.

Answer 2

Linked list would be your best bet if what you *need* is a linked list (java.util.LinkedList in Java, std::list in C++).

If you're looking for a resizeable array (java.util.ArrayList in Java, std::vector in C++), you have to implement exactly that, a resizable array: write insert/erase functions that take a pointer to your struct and call realloc() as necessary to change the size of the array it holds - the struct would hold a pointer to a malloc()'d array and its size.



A list and an array are entirely different data structures, regardless of the language. List has constant time insert and linear time access, array has linear time insert and constant time access.



To be more efficient, your struct would hold a pointer to the malloc()'d array and two sizes: the capacity (how many elements were actually allocated) and size (how many of those elements are currently in use) -- that way you avoid having to realloc() on every single-element insert.

Answer 3

Java is an interpreted language; C is a compiled language. Interpreted languages are not directly executed by the hardware. Instead, they are examined by a run-time interpreter, which then carries out the actions specified in the interpreted source program. A compiled language, on the other hand, is actually translated into machine language for direct execution by the hardware at run time.



Interpreted languages have a lot of run-time flexibility, including the ability to dynamically allocate data items. Compiled languages lack this flexibility because there is no overseeing run-time module to provide it. However, interpreted languages run much more slowly than compiled languages and take up more space with greater waste.



The reason you don't have dynamically-sized variables in C is that it's a compiled language. However, you can still allocate memory with malloc() or new when required, but you must use pointers to manipulate data in allocated memory. This is closer to the way the hardware does it but it's more awkward than the interpreted methods that an interpreted language like Java (or Visual Basic, or Python, or Perl) provides.

Answer 4

If you've made a linked list from scratch in java, you'll know that you use a "node" class that's got some data and a pointer to the next node. You can implement a node like this in C by using an array of 2 void pointers. The first void pointer is used to point to the next array of 2 void pointers, and the second void pointer should point to your data. Then you just have to write some methods to go along with this to work with your nodes to give them linked list functionality. You could also implement a structure that has a pointer of its own type and a void pointer to point to the data.

Answer 5

Link list can solve your problem.