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?

I am afraid I don’t understand exactly what your two (or is it just one?) new functions are meant to do. If you want to insert multiple entries, that should build on your basic insert function – then you only have to get it right once. If you want to insert at the end (as your insert does), consider maintaining a tail as well as head, to obviate the scan to find the end. In this case, you could put head+tail into a struct list. If you want the list (as represented by the head) to be an argument to your second new function, you should make that function your basic insert function. — PJTraill
– PJTraill, Commented Jun 1, 2015 at 22:12
i dont want to insert multiple entries, i want to insert to the list i created but im not sure how to handle previous and next struct members in the insertion and where to make them point to — hack-is-art
– hack-is-art, Commented Jun 1, 2015 at 22:32

Gerard van Helden · Accepted Answer · 2015-06-01 21:52:02Z

4

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).

answered Jun 1, 2015 at 21:52

Gerard van Helden

1,61210 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

hack-is-art Over a year ago

can you please post you suggested code because i need this asap?

Gerard van Helden Over a year ago

I'm sorry. My fine art should suffice :P Maybe someone else wants to get a quick reputation win from this, but I really think you're better of implementing it yourself. Each of the steps portrayed is needed in your code, and it's not that hard

Michael Dorgan Over a year ago

I'll give you points for that fine response and excellent ASCII art :)

hack-is-art · Accepted Answer · 2015-06-02 00:52:49Z

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;
}

answered Jun 2, 2015 at 0:52

hack-is-art

3256 silver badges20 bronze badges

Collectives™ on Stack Overflow

Doubly Linked List Insertion to Specific List function & parameters

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related