Linked-lists in c

Question

I'm fairly new to coding in c and have stumbled upon a problem. The code below is what I have so far.

The trouble I'm running into is the syntax, more specifically on how to loop through the list. I've spent the past week looking at different resources but none explained how to work with a similar struct data type. The way I've attempted to loop through the list results in an error, and I'm having trouble adding the job in the right place since the list is in increasing order - based on the reference number.

The other problem I've run into is within function 5. I'm not entirely too sure of how to return both an integer and character value through a char pointer, unless you return just the entire job_node. As of now, I have casted the value of the node to be a char.

Since I haven't coded much in c - any other suggestions on how to make the code more efficient without changing the values of the functions would be extremely helpful.

Answer 1

A linked list is a container of nodes, and each node has some data payload. Often each data record has a key, a value used to compare two records. In students' assignments in general the data is a simple letter or a number. In your case is a pointer to a "job post".

Below I will show you an alternative way to write his. But first...

It is important to note that the list is a container of nodes, not a list of job posts. A list is not a node, a node is not a list, and the data is not a node.

Mixing these things like you did in your program leads only to problems: you will not be able to use the list to contain other data, for example. You will have trouble changing the implementation of the list without changing the data. You will need to change the list functions if you change a field in the job post. Only problems.

example

bool job_insert(int refNum, char job_name[], struct job_list * list);    

should be like

    int     insert_l( Job* job_post ,List* the_list ,int(*compare_function)(void*,void*)); 

Why?

• Using the former way you can use just a pointer to Job --- in general you should use a void* so you can use anything inside the data record without the need to change the arguments list.
• this way if you add a field to Job or change perhaps the reference number to a char[] to add a check-digit you do not need to change a thing here
• compare_function() compare two Job and return -1 if the 1st is greater, 1 if the 2nd is greater, or 0. This way you can change the sorting criteria at any time, just writing a new 10-line function, and have records inserted by new criteria. C qsort() uses this, C++ sort() uses this, Borland Turbo Pascal used this in the 80;s. It is simple and flexible.
• the function can be as simples as

int compare_reference(void* a, void* b)
{
    int first =  ((Job*) a)->reference_number;
    int second = ((Job*) b)->reference_number;
    if (first < second ) return 1;
    if (first > second ) return -1;
    return 0;
}; 

and used like this

    int    res = insert_l( one_job, new_jobs, compare_reference );

and if res is 0 one_job was inserted in new_jobs list at the correct position. It is also easier to read: insert record into list according to criteria.

And if at any time you need to use descending order or sort by another criteria you just need to pass a new function. This means that you can use the same List-related functions to contain any data. This is the reason to use only void pointers to the data element also...

Back to the program

This could be a test file to drive your tests:

    1    engineer
    2    magician
    3    astronaut
    4    actress
    5    truck driver
    6    writer

The structures

typedef struct
{
  int       reference_number;
  char*     job_name;

}   Job;

typedef struct node_
{
    Job*            info; // pointer to data record
    struct node_    *next;
    struct node_    *prev;

}   Node;

typedef struct 
{
    unsigned  size; // actual size
    unsigned  capacity; // limit in # of nodes
    Node*     head;
    Node*     tail;

}   List;

And you have a List that is a collection of Node. Each Node has a pointer info that point to a Job, that is the data record. Inside a Job you have the reference number and the job's name. reference_number is called key because it is the field used to compare Job records.

The List has no reference to Job, only to Node. Node has no data, just a pointer. So to use List to contain songs or cars or books like the next assignment in line is easy ;)

the functions

List*       create_l(unsigned); // return new List
List*       delete_l(List*); // erase one
int         insert_l( Job*,List*,int(*)(void*,void*)); // insert based on function
List*       merge_l(List*,List*,int(*)(void*,void*) ); // merge 2 lists into a 3rd
int         remove_by_ref_l(int,List*); // delete a record
char*       search_job_l(int,List*); // search for job description for a reference#

I believe that now you see some added convenience:

• insert() receives just a pointer to a Job and to a List, and the name of a function to compare 2.
• create() returns a pointer to a new List with the limit set to a max # of nodes
• remove() gets a reference number and if it is found in List removes the record and returns 0
• search() works the same way

I suggest you write this way. If you need help I can provide more code. I had no time today to write a full example.