Linked List in C

[Greg White]

Hello,

Can someone supply me with a small sample of c showing how to build a linked list of records that are ordered by a string key?

I am converting thousands of lines of Pascal that is filled with linked lists and I would like a good sample to work from. These lists are single-linked but anything will help.

Thanks very much.

[A. Clay Stephenson]

Hi Prog:

I'm sure I have something but it'll at least be tomorrow before I'll have a chance to dig a few functions up.

[A. Clay Stephenson]

Hi Again:

By the way, dynamic arrays are an option in C that generally replace linked lists. A couple of neat features there is that you get doubly-linked lists for free and the array can very easily be sorted in another order by calling qsort and supplying a comparison function to the qsort function. The comparison function is equivalent to a functional parameter in Pascal. In C, they are called pointers to functions. Man qsort for details.

Regards, Clay

[Greg White]

Thanks Clay.

I really need the linked lists at the moment but I would like to understand how you can grow an array during execution. I did look at qsort and I think I understand how to use it.

[A. Clay Stephenson · Accepted solution]

Hi Pascal:

I spent about 10 minutes over lunch grabbing and editing some of my standard linked list routines and a small main to populate and display the list. I should warn you that I do set up muy linked lists a little bit differently. I always initialize the list with both a head (root) and a tail (last) and then
root->ptr = last. This does blow 2 records BUT the advantage is that you are then ALWAYS inserting in the middle of the list. No exceptions for insertion at the head or at the end of the list. Nowadays, what's two extra records anyway? I find that the simplicity and reliabilty is well worth a few bytes of wasted space.

This example uses the same my_rec with the addition of a pointer. The list is actually ordered by name with a secondary age key. If a person is found with matching name and age then the income is simply added to the existing list record otherwise a new record is inserted. This should serve as a general example for any linked list stuff that you need. If you weant to convert this to doubly-linked routines, that execise is left to the reader.

I've broken this into 3 attachments: the header file "local.h"; list.c and main.c.

Here's the header file.

Regards and Enjoy, Clay

[A. Clay Stephenson]

Here's the linked list routines:

list.c

[A. Clay Stephenson]

Here's the main program, main.c

You should compile it like this:

cc -Aa main.c list.c -o list

and then simply execute list.

Note that the header file includes a couple of cpp macros assign_errno and S_Copy. This is normally considered goods practice in C and all your defines and macros should go into the header file(s). I would also suggest that you create a makefile for practice to compile and link this code.

Clay

[Greg White]

Wow! This is great. I can't believe the responses I've gotten in this forum. Clay, I'll have to think about using two records but I will say that you insertion routine is much simpler than my pascal version.

[A. Clay Stephenson]

Hi Pascal:

I spent another few minutes over lunch today and put together the dynamic array version of the same program. The first part is the header file, local.h.

Clay

[A. Clay Stephenson]

The next part are array routines themselves. I also included a function to sort the array; since this calls qsort all that is necessary is a comparison function which is almost exactly the same as the linked link version.

Here is array.c

[A. Clay Stephenson]

Finally, the main routine.

Compile it like this:
cc -Aa main.c array.c -o array.

Then execute array.

By the way, I think I have now retired from teaching C though I might answer specific questions.


Enjoy, Clay