Exception thrown in ordered linked list(write access violation)

Question

I am getting a write access violation exception when I try to run my code.

 int main() { OrderedList<int> l; l.insert(3); l.insert(6); l.insert(56); l.insert(1); return 0; }

Here is OrderedList.h including all the functions of OrderedList class:

#pragma once #include <iostream> using namespace std; template <class T, class LessComp = less<T>, class Equal = equal_to<T> > class OrderedList { private: struct Node { T value; Node* next; Node(const T& value, Node* next = nullptr) : value(value), next(next) {} }; Node* first; int numElements; public: OrderedList(); ~OrderedList(); bool isEmpty(); void insert(const T&); void remove(const T&); int size() const; bool find(const T&) const; void listItems(ostream&); }; template <class T, class LessComp, class Equal > OrderedList<T, LessComp, Equal>::OrderedList() { this->first = nullptr; this->numElements = 0; } template <class T, class LessComp, class Equal > OrderedList<T, LessComp, Equal>::~OrderedList() { Node* current = this->first; Node* next; while (current != nullptr) { next = current->next; delete current; current = next; } this->numElements = 0; } template <class T, class LessComp, class Equal > bool OrderedList<T, LessComp, Equal>::isEmpty() { return this->numElements > 0; } template <class T, class LessComp, class Equal > void OrderedList<T, LessComp, Equal>::insert(const T& element) { Node* temp = this->first; Node* node=nullptr; LessComp lesscomp; if (this->first == nullptr) { this->first->value=element; this->first->next = nullptr; } else { if (lesscomp(element, this->first->value)) { node->value = element; node->next = this->first; this->first = node; } else { while (temp->next != nullptr && !(lesscomp(element, temp->value) && element >= temp->value)) { temp = temp->next; } if (temp->next == nullptr) { temp = temp->next; temp->value = element; temp->next = nullptr; } else { node->value = element; node->next = temp->next; temp->next = node; } } } ++this->numElements; } template <class T, class LessComp, class Equal > void OrderedList<T, LessComp, Equal>::remove(const T& element) { Node* temp = this->first; Node* prev; if (temp == nullptr && temp->value == element) { this->first = temp->next; delete temp; return; } while (temp != nullptr && temp->value != element) { prev = temp; temp = temp->next; } if (temp == nullptr) { return; } prev->next = temp->next; delete temp; --this->numElements; } template <class T, class LessComp, class Equal > int OrderedList<T, LessComp, Equal>::size() const { return this->numElements; } template <class T, class LessComp, class Equal > bool OrderedList<T, LessComp, Equal>::find(const T& element) const { Node* current = this->first; while (current != nullptr) { if (current->value == element) { return true; } current = current->next; } return false; } template <class T, class LessComp, class Equal > void OrderedList<T, LessComp, Equal>::listItems(ostream& os) { Node* temp = this->first; while (temp != nullptr) { os << temp->value << endl; temp = temp->next; } }

And the error:

I don't know what to try to solve this problem.

I want to create a sorted linked list using templates.

Any ideas or suggestions?

Thanks in advance.

Did you try to step through your code, line-by-line, with a debugger, while investigating the values of all of the variables, at each execution step, while seeing where it stops matching your expectations? Visual Studio has an excellent debugger. — Algirdas Preidžius
– Algirdas Preidžius, Commented Dec 4, 2019 at 19:07
@RemyLebeau thanks for your answer! How could I implement insert()function? — lambozsolty
– lambozsolty, Commented Dec 4, 2019 at 19:13

Remy Lebeau · Accepted Answer · 2019-12-04 19:39:18Z

insert() is coded all wrong. When the list is empty, it tries to access the members of first when first hasn't been allocated yet and is still nullptr. In fact, insert() doesn't even try to allocate any Node instances at all. You need to add calls to new inside of insert().

Also, remove() is accessing Node members via nullptr pointers, too.

Also, isEmpty() is returning the wrong value, it needs to use == instead of >.

Try something more like this instead:

#pragma once #include <iostream> template <class T, class LessComp = std::less<T>, class EqualComp = std::equal_to<T> > class OrderedList { private: struct Node { T value; Node* next; Node(const T& value, Node* next = nullptr) : value(value), next(next) {} }; Node* first = nullptr; int numElements = 0; public: OrderedList() = default; OrderedList(const OrderedList&) = delete; ~OrderedList(); bool isEmpty() const; void insert(const T&); void remove(const T&); int size() const; bool find(const T&) const; void listItems(std::ostream&) const; }; template <class T, class LessComp, class EqualComp > OrderedList<T, LessComp, EqualComp>::~OrderedList() { Node* current = first; Node* next; while (current) { next = current->next; delete current; current = next; } numElements = 0; } template <class T, class LessComp, class EqualComp > bool OrderedList<T, LessComp, EqualComp>::isEmpty() const { return numElements == 0; // or: return first == nullptr; } template <class T, class LessComp, class EqualComp > void OrderedList<T, LessComp, EqualComp>::insert(const T& element) { Node* temp = first; Node* node = nullptr; LessComp lesscomp; if (!first) { first = new Node(element); } else if (lesscomp(element, first->value)) { first = new Node(element, first); } else { while (temp->next && !lesscomp(element, temp->value)) { temp = temp->next; } temp->next = new Node(element, temp->next); } ++numElements; } template <class T, class LessComp, class EqualComp > void OrderedList<T, LessComp, EqualComp>::remove(const T& element) { Node* current = first; Node** prev = &first; EqualComp equalcomp; while (current) { if (equalcomp(current->value, element)) { *prev = current->next; delete current; --numElements; return; } prev = &(current->next); current = current->next; } } template <class T, class LessComp, class EqualComp > int OrderedList<T, LessComp, EqualComp>::size() const { return numElements; } template <class T, class LessComp, class EqualComp > bool OrderedList<T, LessComp, EqualComp>::find(const T& element) const { Node* current = first; EqualComp equalcomp; while (current) { if (equalcomp(current->value, element)) { return true; } current = current->next; } return false; } template <class T, class LessComp, class EqualComp > void OrderedList<T, LessComp, EqualComp>::listItems(std::ostream& os) const { Node* temp = first; while (temp) { os << temp->value << std::endl; temp = temp->next; } }

int main() { OrderedList<int> l; l.insert(3); l.insert(6); l.insert(56); l.insert(1); l.listItems(cout); return 0; }

Live Demo

Collectives™ on Stack Overflow

Exception thrown in ordered linked list(write access violation)

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related