Hello, I am writing a single-linked list, here’s a piece:

template<typename T> struct one_list; template<typename T> struct node_list { node_list(const T& val) : data(val), next(nullptr) { } const T& get_data() { return data; } node_list<T>* get_next() { return next; } friend struct one_list<T>; private: T data; node_list<T>* next; }; template<typename T> struct one_list { typedef node_list<T> node_t; one_list() : size(0), root(nullptr) { } void push(const T& val) { ++size; node_t* ptr = &(*(root + (size - 1))); ptr = new node_t(val); ptr->next = nullptr; } void pop() { if (size) { node_t* ptr = root + size - 1; delete ptr; ptr = nullptr; --size; } else throw std::runtime_error("remove nullable element\n"); } const size_t& get_size() { return size; } node_t* get_root() { return root; } private: size_t size; node_t* root; }; int main() { one_list<int> list; list.push(1); list.push(2); list.push(3); list.pop(); }

an exception is thrown in the pop method in a line with delete ptr ... I can’t understand why root is still zero ... help solve the problem

  • Well, the push method is also strangely written. It would be necessary first to allocate memory (make new ), and only then assign pointers. You first have ptr=&(*(root + (size - 1))); , that is, some value was assigned, and then ptr=new node - you assign the value again - Alexey Sarovsky
  • The push method should look something like this: node_t* ptr = new node_t(val); ptr->next=nullptr; (root+size)->next = ptr; ++size; node_t* ptr = new node_t(val); ptr->next=nullptr; (root+size)->next = ptr; ++size; - Alexey Sarovsky
  • hmm, now the exception is already in the push method - xperious

1 answer 1

push and pop functions are incorrect

 void push(const T& val) { ++size; node_t* ptr = &(*(root + (size - 1))); ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ptr = new node_t(val); ptr->next = nullptr; }

Nodes for the list are not allocated in a continuous chunk of memory, as is the case for arrays. Therefore, pointer arithmetic is not applicable here. Moreover, you first assign the value of the expression &(*(root + (size - 1))) ptr pointer, which in itself, as already mentioned, does not make sense, and then rewrite this value with the new value returned by the expression new node_t(val)

Similar problems occur with the pop function.

The push function can be written much easier.

 void push( const T &val ) { node_t **ptr = &root; while ( *ptr ) ptr = &( *ptr )->next; *ptr = new node_list<T>( val ); ++size; }

The pop function might look like

 void pop() { if ( size ) { node_t **ptr = &root; while ( ( *ptr )->next ) ptr = &( *ptr )->next; delete *ptr; *ptr = nullptr; --size; } else { throw std::runtime_error("remove nullable element\n"); } }

Keep in mind that when you define a single-linked list, it is much more efficient to add and remove items from the beginning of the list than from the end of the list, as you intend to do.

  • thanks, about the impossibility of using pointer arithmetic not to do it yourself - xperious
  • @xperious There is nothing. :) - Vlad from Moscow