Problem with Array of Pointers in Linked List?

[rohanprabhu]

Mentor note: Long-time member who hasn't been around for a couple years. This is a problem worth investigating, though, IMO.
There was a problem in an assignment I was solving, which asked me to break up the elements of a linked list into 3 different linked lists. Rather than creating 3 linked lists, I tried to create a general program for any such number and hence used an array of pointers.

A node in my linked list is given as such:

struct node {
    int data;
    node* next;
};

and i had a function to add elements to it:

node* getNewNode(int data) {
    node* x = new node;
    if(x == NULL) {
        cout<<"Error: OVERFLOW";
        exit(0);
    }

    x->data = data;
    x->next = NULL;
    return x;
}
   
void addElement(node** start, int data) {
    node* x = getNewNode(data);
    if(*start == NULL) {
        *start = x;
    } else {
        x->next = *start;
        *start = x;
    }
}

and a function to display the list:

void displayList(node* start) {
    node* x = start;
   
    while(x != NULL) {
        cout<<x->info;
        x = x->next;

        if(x != NULL) {
            cout<<";";
        }
     }
}

and all of this works perfectly fine if i use something like this:

node* y;
addElement(&y, 21);
addElement(&y, 13);
displayList(y);

But, if i try using an array of pointers, for example:

node** iList = new node*[2];
node* m = *(iList+0);
addElement(&m, 21);
addElement(&m, 11);
displayList(m);

The output is something like:

21;11;<random-number>

and then the program segfaults. What am I doing wrong here? For all I know, *(iList+0) is a variable of type node* and hence should satisfy the requirements for it to be the first element in a linked list.. why is it not working?

 

[Future Bruno]

The answer has to do with memory management. When you create the array of pointers, you are allocating memory for the array itself, but not for the individual nodes. You need to explicitly allocate memory for each node before adding it to the linked list. This can be done by changing your addElement() function to something like this:void addElement(node** start, int data) { node* x = getNewNode(data); // Allocate memory for the new node if(*start == NULL) { *start = x; } else { x->next = *start; *start = x; } delete x; // Delete the node when finished}You also need to make sure that you delete the allocated memory when you're finished with the list, otherwise you'll end up with a memory leak.

 

[quicknote]

There are a few potential issues with your code that could be causing the problem with your array of pointers. First, it seems that you are not properly initializing the elements in your array of pointers. When you use the line `node* m = *(iList+0);`, you are assigning the value at the first index of your array to the variable `m`. However, since you have not yet added any elements to the linked list at this point, `m` will be a null pointer. This means that when you try to add elements to `m` using the `addElement` function, you are actually trying to dereference a null pointer, which can cause a segfault.

To fix this issue, you should initialize each element in your array of pointers to a null pointer before trying to use them. This can be done using a simple for loop, such as:

```
for(int i = 0; i < 2; i++) {
*(iList+i) = NULL;
}
```

Another potential issue is that you are passing the address of `m` to the `addElement` function, instead of the address of the element at the first index of your array. This means that you are only adding elements to the first index of your array, and not to the other elements. To fix this, you should pass the address of the element at the first index of your array, like so:

```
addElement(iList, 21);
addElement(iList, 11);
```

Overall, it is important to make sure you are properly initializing and using your array of pointers in order to avoid any potential errors or segfaults. I would recommend thoroughly reviewing your code and making sure all of your pointers and addresses are being used correctly.