CODEWITHSUNDEEP
c++arrayslinked-list
hasnain095
hasnain095

Reputation: 118

Array Implementation of Linked List

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.

Upvotes: 0

Views: 89

Answers (1)

eerorika
eerorika

Reputation: 238281

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.

Upvotes: 2

Related Questions