Inserting linked list nodes from an array, but not all are being inserted

0
votes

I have the following doubly linked list struct:

struct coords
{
    int x;
    int y;
    struct coords* previous;
    struct coords* next;
};

I have a linked list with the following values, shown here as (x, y):

head                                                          tail
(-1, -1) <--> (0, 1) <--> (2, 1) <--> (1, 0) <--> (0, 2) <--> (-1, -1)

Under my implementation, head and tail with always be (-1, -1). I also have newCoords, an size 4 array of coords* with the following elements:

[(0, 2), (2, 2), (1, 3), no value]

newCoords can have anywhere between zero and four assigned elements. I also keep track of the number of nodes in an int called newCoords (which currently has the value of 3). I want to add these nodes to my linked list, between tail and the last non-tail node. For this, I have the following code (print statements removed for clarity):

void insert (struct coords* position, struct coords* newCoord)
    {
        newCoord->next = position->next;
        newCoord->previous = position;
        position->next = newCoord;
    }
... //here I create the initial linked list
struct coords* newCoords[4]; //4 is the maximum number of new coords that can be added
int numberOfNewCoords = 0;
... //here I fill newCoords, and as I do I increment numberOfNewCoords by 1
if (numberOfNewCoords > 0) //numberOfNewCoords stores the number of coords in newCoords
    {
        struct coords* temp = tail->previous;
        /* add new possible locations to list */
        for (int i = 0; i < numberOfNewCoords; i++)
            {
                insert(temp, newCoords[i]);
                temp = temp->next;
            }
     }

The first two values in newCoords are added just as I expect them to be. However, the last value is not inserted into the linked list. What is inserted where it should be is a node with numbers that change every time I run the program. The list should be

head                                                                                              tail
(-1, -1) <--> (0, 1) <--> (2, 1) <--> (1, 0) <--> (0, 2) <--> (0, 2) <--> (2, 2) <--> (1, 3) <--> (-1, -1)

but instead it's

head                                                                                                          tail
(-1, -1) <--> (0, 1) <--> (2, 1) <--> (1, 0) <--> (0, 2) <--> (0, 2) <--> (2, 2) <--> (9765060, 9770824) <--> (-1, -1)
2
carrayslinked-list
Please, add the newCoords and numberOfNewCoords declaration. Maybe you've missed a character there and now there is one element less. - Viktor Latypov
OK, and how do you initalize the newCoords array ? Looks like you have to allocate each of newCoords[i]. Have you done that ? - Viktor Latypov
@ViktorLatypov I printed the contents of newCoords, and they are correct. To display how I initialize them would be rather long (because it depends on other parts of my program that I'm omitting here), but as far as I can tell, the values are correct. - blacktrance
@Will i: 0, x: 0, y: 2 (new line) i:1, x: 2, y: 2 (new line) i:2, x: 1, y:3 - blacktrance

2 Answers

0
votes

Just to clarify, are you sure you used malloc to allocate memory?

0
votes

I guess you have missed to allocate memory for the new coords that you wish to add. When we add new element to the existing list, we should make sure the memory is allocated before hand to provide space for the new elements. The code you have posted needs modification in this part-

    for (int i = 0; i < numberOfNewCoords; i++)
                {
                    insert(temp, newCoords[i]);
                    temp = temp->next;
                }

After Changes-

    for (int i = 0; i < numberOfNewCoords; i++)
                {
                    temp = malloc(sizeof(struct* coords));
                    insert(temp, newCoords[i]);
                    temp = temp->next;
                }

You can typecast malloc if the compiler does not support automatic typecasting with (struct *)

Hope this will work.