Use a vector to initialize the linked list in C++

Question

Here is my code of struct of linked list. I want to use a vector to initialize the TreeNode. But in constructor, ptr->next = tem has the error Exception thrown: write access violation. ptr was 0xCDCDCDCD. Does someone know the reason and how to correct it?

#include<iostream>
#include<vector>

using namespace std;

struct ListNode {
    int val = 0;
    ListNode* next = NULL;

    ListNode(int val) : val(val){};

    ListNode(vector<int> vec) {
        if (vec.empty())
            return;
        val = vec[0];
        ListNode* ptr = this;
        for (int i = 1; i < vec.size();i++)
        {
            ptr->next = new ListNode(vec[i]);
            ptr = ptr->next;
        }
    }
};

@user6703592 The approach does not make sense. A node can not be initialized by a vector. It is a list that can be initialized by a vector. — Vlad from Moscow, Sep 11 '19 at 15:32
It seems you fundamentally misunderstand `new` and `delete`. If you `delete tem;` then `tem` **and every other pointer to that same object** become invalidated. `delete` does not "release" a pointer to an object (pointers aren't any kind of reference counting handle) it deletes the actual object the pointer points to. — François Andrieux, Sep 11 '19 at 15:33
That code looks random to me. Can you explain to rubber duck what each line of it is supposed to do and why it is there? — SergeyA, Sep 11 '19 at 15:35
sorry actually here `ListNode` is the `LinkedList`. And I have updated my code. — user6703592, Sep 11 '19 at 15:59

score 1 · Answer 1 · answered Sep 11 '19 at 15:30

1

On the first iteration, "next" is going to be uninitialised, so ptr->next is not going to point to anything meaningful and likely will cause a seg fault.

This is not the only bug in the method.

Also, in debug mode, some compilers put a specific bit pattern in uninitialised memory to aid debugging. 0xCDCDCDCD looks suspiciously like one of those bit patterns.

answered Sep 11 '19 at 15:30

Chuu

4,301
2
28
54

CD is indeed uninitialised heap memory: https://en.wikipedia.org/wiki/Magic_number_(programming)#Magic_debug_values – Alan Birtles Sep 11 '19 at 15:39

Vlad from Moscow · Accepted Answer · 2019-09-11T16:06:33.600

For starters it is a bad design. It does not make sense to initialize a node with elements of a vector.

It is a list that may be initialized by elements of a vector not a node.

The definition of the constructor ListNode also does not make sense.

For example its data member next is not initialized.

    ListNode* ptr = next;

So this statement

        ptr->next = tem;

invokes undefined behavior.

A node was allocated and then deleted

        ListNode* tem = new ListNode(*it);
        // ...
        delete tem;

So what the list will contain?:)

Also it is a bad idea to use a typedef like this

typedef vector<int>::iterator vit;

It only confuses readers of the code.

The class can be defined the following way as it is shown in the demonstrative program. Of course you yourself need to append the class definition with other constructors, assignment operators and the destructor.

#include <iostream>
#include <vector>

class List 
{
protected:
    struct Node
    {
        int val;
        Node *next;
    } *head = nullptr;      

public:

    explicit List() = default;

    List( const std::vector<int> &v )
    {
        Node **current = &head;

        for ( const auto &value : v )
        {
            *current = new Node { value, *current };
            current = &( *current )->next;
        }
    }

    friend std::ostream & operator <<( std::ostream &, const List & );
};

std::ostream & operator <<( std::ostream &os, const List &list )
{
    for ( List::Node *current = list.head; current != nullptr; current = current->next )
    {
        os << current->val << " -> ";
    }

    return os << "nullptr";
}

int main()
{
    std::vector<int> v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    List list( v );

    std::cout << list << '\n';
}

The program output is

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> nullptr

As the constructor of the list that accepts a vector is not explicit then you may declare a list the following way

List list( { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } );

possum · Answer 3 · 2019-09-11T16:09:22.500

Your first iteration is not initialized properly.

Try

...
    ListNode(vector<int> vec) {
             ListNode* ptr = this;
...

It's also not aligning the values from the list properly. Set the value for this and then move on with the iterator

        vit it = vec.begin();
        val = *it;

        for ( ++it; it != vec.end(); it++)
        {
            ListNode* tem = new ListNode(*it);
            ptr->next = tem;
            ptr = ptr->next;
        }

instead

Use a vector to initialize the linked list in C++

3 Answers3