C doubly linked circular list insert

Question

Doesn't insert and doesn't keep adresses of next and prev node: I'm trying to read input from file; It can read all data corectly and based on every line, creates an Aeronava object. It seems that the insert doesn't work.any suggestions?

void insertFAV_Av(FAVnode*list, Aeronava *av){
        FAVnode* nn = (FAVnode*)malloc(sizeof(FAVnode));
        //first = list;
        nn->infoUtil = (Aeronava*)malloc(sizeof(Aeronava));
        nn->infoUtil->idAeronava = (char*)malloc(strlen(av->idAeronava) + 1);
        //strcpy(nn->infoUtil->idAeronava, av->idAeronava);
        nn->infoUtil = av;
        if (first == NULL){
            nn->prev = nn->next = nn;
            first = nn;
        }
        else{
            list = first;
            while (list->next != first){
                list = list->next;
            }
            nn->prev = list;
            list->next = nn;
            nn->next = first;

        }
}


struct Aeronava{
    char* idAeronava;
    tipA tipAero;
    short int nrLocuri;
    double greutateMaxima;
};

struct FAVnode{
    FAVnode*next;
    FAVnode*prev;
    Aeronava* infoUtil;
};

Standard Warning : Please [do not cast](http://stackoverflow.com/q/605845/2173917) the return value of `malloc()` and family in `C`. — Sourav Ghosh, May 15 '15 at 12:30
if `nn->infoUtil = av;` is there, why did you `malloc()`ed in first place? apart anaything, it's a memory leak. — Sourav Ghosh, May 15 '15 at 12:32
Please elaborate what "doesn't insert" means; what *should* happen, and what happens instead. — Scott Hunter, May 15 '15 at 12:32
insert here means, creating a new node based on the object sent as parameter and insert it at the end of the list — hallelujah, May 15 '15 at 12:36
@hallelujah how do you know it does not add it at the end of the list. Because you do `nn->infoUtil = av;`, you are not able to test if it is inserted, if you overwrite the original `av`. — wimh, May 15 '15 at 12:48
it doesn't add anything right at the end of the list. i added a quick watch.and it doesn't make proper connections between nodes. — hallelujah, May 15 '15 at 12:51
After fixing about a half dozen errors in your code: What is `first`? http://ideone.com/icNRXP — Bill Lynch, May 15 '15 at 12:55
Are you sure this isn't C++ code? Your `FAVnode` won't compile in a C compiler. — Bill Lynch, May 15 '15 at 12:56
You don't neet to iterate round the whole list to find its end, if it is doubly linked. Just use `list = first->prev`. — CiaPan, May 15 '15 at 13:04
why did you delet your code from the question? It invalidates the answers and make the question make no sense. I've rolled back your edit. — bolov, May 17 '15 at 14:26

score 2 · Answer 1 · answered May 15 '15 at 12:57

        nn->prev = list;   // 1
        list->next = nn;   // 2
        nn->next = first;  // 3

Lines 1 and 2 link nn to list in both directions, but line 3 links nn with first in one direction only. You lack the opposite link update here:

        first->prev = nn;

score 0 · Answer 2 · answered May 15 '15 at 15:08

I see a few problems here. First is this:

     else{
        list = first;
        while (list->next != first){
            list = list->next;
        }
        nn->prev = list;
        list->next = nn;
        nn->next = first;

You are assigning first to list. List is the passed parameter. By doing this, you are clobbering it. A proper insert routine looks like this:

void insert_node(node_t **head, node_t **tail, nodedata_t *data)
  {
    /* Do some stuff */


    /* Insert Node */
    if (*list == NULL)
        {
          *head = data;
          *tail = data;
      else
        {
          *tail->next = data;
          *tail->next->prev = *tail;
          *tail->next->next = NULL;
          *tail = data;
        }
  }

This inserts at the end of the list. For the middle of the list, you would change the code in the else to the following:

data->next = curr->next;
data->prev = curr;
data->next->prev = data;
curr->next = data;

The variable curr is being defined as "node_t *curr;" The way this works is that you have a pointer to data, and you have a pointer to the current node, and the node after current exists, which we call blue. So you set next in data to point to blue and prev in data to point to curr. Then you set prev in blue to point to data, and next in curr to point to data. Then the list insert is done. There is another special case that this didn't address, which is insertion at end of list. But I will leave that as an exercise for the reader.

One more thing I noticed. There is no need to typecast the pointer result from malloc. It's a void type which is compatible with all pointer types.

C doubly linked circular list insert

2 Answers2