Doubly Linked List Insertion to Specific List function & parameters

Question

I have the following code which is a part of doubly linked list implementation. Then I have to use my ADT implementation to create a table of the form value (which is a string), address (which is of type uint32_t) (so a 2 columns table).

typedef struct {
    char *label; // is a string like "mov".
    uint32_t labelAddress; // the address of the label.
} individualEntry;

typedef void( *FreeList )( void* );

typedef struct listEntries {
    individualEntry newInstr;
    struct listEntries *prev;
    struct listEntries *next;
} listEntries;

listEntries *head;

/*
 * HELPER FUNCTIONS
 */

listEntries *createNewList() {
    listEntries *newListPtr = malloc(sizeof(listEntries));
    return newListPtr;
}

listEntries *createNewEntry( char *label, uint32_t address ) {
    listEntries *newEntry = (listEntries*) malloc(sizeof(listEntries));
    newEntry->prev = NULL;
    newEntry->next = NULL;
    newEntry->newInstr.label = label;
    newEntry->newInstr.labelAddress = address;
    return newEntry;
}

void insert( char *label, uint32_t address ) {
    listEntries *temp = head;
    listEntries *newEntry = createNewEntry(label, address);
    if ( head == NULL ) {
        head = newEntry;
        return;
    }
    while ( temp->next != NULL ) {
        temp = temp->next;
    }
    temp->next = newEntry;
    newEntry->prev = temp;
}

I need to first create this table and then add to this the records.

My difficulty is on the implementation of a function that inserts to this specific table the values to be added. Do I need another insert function, or do I have to edit the one I have?

If I need a new function that takes as parameters: a pointer to the new table of type struct listEntries, string and address of the record to be added, do I need to consider in the parameters the previous and next records of my list?

I'm not sure how to handle the previous and next pointers after the insertion.

Can someone post an implementation of such a function?

Answer 1

So this is my answer to my own question (compiled, tested, and it works). I used iterators, thanks for the visualisation above but I needed more tips, like the word iterators.

void insert(struct list *listPtr, listIterator iter, int value) { 

struct listEntry *newEntry = list_alloc_elem(); // a helper that allocates memory for an individual entry; 
newEntry->value = value;
newEntry->prev = iter->prev;
newEntry->next = iter;
iter->prev->next = newEntry;
iter->prev = newEntry;
}

Answer 2

The only thing you need to insert an item into a (doubly) linked list, is a reference node, and where whether you want to insert it before or after that node. The definite best way to solve this is to visualize it. You should always be careful that you make sure the references both ways are correct, and you would probably do well to have some self-test for that in place, so each node pointed to, points back to the same node, otherwise you have an integrity problem.

And now for the visualization. Think of it like this (double lines represent double links):

A = B = C

Say I want to add an item to this list at the end, i just need to tell C to point to that item, e.g.:

A = B = C - D

And point that item back:

A = B = C = D

Now, if I wanted to move D to another position, say at the second, I can let the reference node 'A' to point to 'D':

A - B = C = D
 \_________/

Have D point back to A

A - B = C - D
 \`========'/

Have C no longer point to D:

A - B = C   D
 \`========'/

Have D point to B:

      ______
     /      \
A - B = C   D
 \`========'/

Have B point back to D:

      .=====
     //     \\
A   B = C   D
 \`========'/

As you can now see, B no longer points to a, and visually rearranging this solves the problem:

   C = B ===.
           \\
A           D
 \`========'/

equals:

A = D = B = C

If you understand this, you can do any operation on a doubly linked list. a And thank you for the opportunity to do some ascii art.

To summarize: you don't actually have a "list". You only have nodes, pointing to another node that points back, or to nothing (NULL).