Array of linked structs in c++

Question

I want to create an array of linked structs, but I don't know how to populate such array. Here is an example of what I want to do.

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

I want to declare the array inside a loop

while(1) {
    foo array[n];
    // init array, data to -1 and next to NULL;

I'd like to put things inside of it, creating new instances of foo in a way that all foo's linked in index i share a common property.

    foo* new_foo = new foo;
    new_foo -> data = x;
    new_foo -> next = array + i; // index
    array[i] = *new_foo;

    //do things
    iterate(array);

    //delete[] array; maybe
} // end loop, start again with a new array.

The iterate method would be something like this.

for(int i=0; i<n; ++i) {
    foo* iter = array + i;
    while(iter != NULL) {
        //do things
        iter = iter -> next;
    }
}

It doesn't work at all, the iterate method goes on an infinite loop. The error could be somewhere else, but I still don't know if this is the proper way of doing it. I know I have to use delete somewhere too. I'm still new to c++ and I'd love any advice from you. Thanks!

Edit:

This works fine, if anyone wonders.

foo* array[n] = {NULL};

foo* new_foo = new foo;
new_foo -> data = x;
new_foo -> next = array[i];
array[i] = new_foo;

No clue what your goal is, but `new_foo -> next = array + i;` has `next` point to the array element you are about to assign to. End result, each `foo` links to itself and iteration is infinite. Also leaks like a sieve because the `foo` was dynamically allocated an not deleted. Thinking [a good introductory book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) might be the best option here — user4581301, Mar 27 '17 at 05:55
Yeah, mixing stack and dynamic allocation isn't a good idea, I guess. Gonna give it a read thank you. You made me realize it was better to use an array of pointers. — camtorr95, Mar 27 '17 at 14:46

Chandini · Accepted Answer · 2017-03-27T08:01:16.517

1

From what I have understood through your question, You need a way to populate a linked struct and iterate through it. Correct me if I am wrong.

Lets say if u want to populate n structs.

foo* new_foo = new foo;
new_foo -> data = 1;
foo* head = new_foo; // store a starting pointer to the linked list
foo* prev = new_foo;
i=2;
while(i<=n)
{
  foo* new_foo = new foo;
  new_foo -> data = i++;
  prev -> next = new_foo; 
  prev=new_foo;
}
prev->next=NULL;

Now if you u wish to iterate and do things to the populated list.

foo* iter =head;
while(iter!=NULL)
{
  //do things
  iter=iter->next;
}

Now as u want an array of such Linked structs, you can store the head pointers of all the linked structs in an array.

edited Mar 27 '17 at 08:01

answered Mar 27 '17 at 06:31

Chandini

540
2
11

Pretty good cut at an answer, given the nature of the question. There are uses for arrays of linked lists. Hash tables are a common one. – user4581301 Mar 27 '17 at 07:13
Yeah I agree, sorry about that. Modified the answer, Thanks. – Chandini Mar 27 '17 at 07:57
Thank you both! Those created in the stack were only changing the value of the reference and were not pushed back in the link chain, thus referencing itself and looping infinitely. So storing the head pointer like this worked like a charm. – camtorr95 Mar 27 '17 at 14:44

Array of linked structs in c++

1 Answers1