Array Implementation of Linked List

Question

Trying to implement linked list using arrays, list gets created but while printing the array gets messed up and prints garbage values

I have used gdb to debug the issue, the array is properly formed just before printing. As soon as I print the array, it starts printing garbage values.

int MAX_SIZE=10;

int *head;
int end = -1;

void appendToList(int value){
    if (end == -1){
        int list[MAX_SIZE] = {0};
        head = list;
        *(head + end + 1) = value;
        end++;
    }
    else
    {
        *(head + end + 1) = value;
        end++;
    }

}

int main(){
    appendToList(1);
    appendToList(8);
    appendToList(3);
    appendToList(4);
    appendToList(5);

    std::cout<< head[0] << "\n";
    std::cout<< head[1] << "\n";
    std::cout<< head[2] << "\n";
    std::cout<< head[3] << "\n";
    std::cout<< head[4] << "\n";

    return 0;
}

It should print "1 8 3 4 5". The output is like "1 8 0 0 42050", but that is wrong.

int list[MAX_SIZE] = {0}; gets destructed after going out of scope. — nada
– nada, Commented Jul 15, 2019 at 11:16
The list array in your function is local. Once the scope it's defined in ends, so does the life-time of the list array. Any pointer you have to it will become invalid. — Some programmer dude
– Some programmer dude, Commented Jul 15, 2019 at 11:17
Besides, what you're trying to implement is not a linked list, but an arraylist, i.e. an array which prevents you from exceeding its boundary. — Massimo Di Saggio
– Massimo Di Saggio, Commented Jul 15, 2019 at 11:18
BTW, int list[MAX_SIZE] = {0}; initializes only the first element of the array. — vahancho
– vahancho, Commented Jul 15, 2019 at 11:24
@vahancho No that's wrong, the remaining elements of the array will be initialized as well. — Some programmer dude
– Some programmer dude, Commented Jul 15, 2019 at 11:29

eerorika · Accepted Answer · 2019-07-15 11:38:53Z

int list[MAX_SIZE] is a local variable. It's lifetime extends to the end of the scope where it was declared. In this case, the array does not exist outside of the if-statement.

head = list sets the pointer in static storage to point to the local array. Once the array is destroyed (at the end of the if-statement block) the pointer no longer points to an object. It is said to be dangling.

Upon further calls to the function, as well as in main the program indirects through the dangling head pointer, and the behaviour of the program is undefined. To fix this, you must use an array whose lifetime extends for at least as long as it is being used.

You should always be on your toes when a pointer / reference / iterator has longer lifetime than the object they are pointing to.

P.S. Your array appears to have nothing to do with a linked list.

P.P.S The program is ill-formed because MAX_SIZE is not a compile time constant expression. The size of an array must be compile time constant. To fix this, declare the variable either const or constexpr.

Thank you, got it. It is an implementation of linked list using an array, it simulates a linked list or rather it will when the code is complete.
@hasnain095 It looks more like an implementation of a stack using an array.

Collectives™ on Stack Overflow

Array Implementation of Linked List

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related