I am trying to implement a linked list, and I am completely lost. I'm getting break points all over the place, specifically with the erase method. Whenever I alter the erase method, some error will inevitably spring up. I've got pointer errors, problems with the destructor that only occur when the erase method is called, and so on.
Here's what I have so far:
Header file:
#pragma once
class IntList {
private:
class IntNode {
public:
IntNode(int v, IntNode *pr, IntNode *nx);
~IntNode();
IntNode* previous;
IntNode* next;
class iterator {
public:
iterator(IntNode* t);
int& operator*();
iterator& operator++();
iterator& operator--();
bool operator!=(iterator other)const;
private:
IntNode* target;
};
private:
int value;
};
IntNode* head;
IntNode* tail;
int count;
public:
IntList();
~IntList();
void push_back(int v);
void pop_back();
int size() const { return count; }
typedef IntNode::iterator iterator;
iterator begin();
iterator end();
//unsigned int size() const;
void push_front(int value);
bool empty() const;
int& front();
int& back();
void clear();
iterator erase(iterator position);
};
Implementation:
#include "IntList.h"
#include <stdexcept>
IntList::IntList() : head{ nullptr }, tail{ nullptr }, count{ 0 }
{}
IntList::~IntList() {
while (head) {
head = head->next;
delete head;
}
}
void IntList::push_back(int v) {
tail = new IntNode{ v, tail, nullptr };
if (!head) { head = tail; }
count += 1;
}
void IntList::pop_back() {
tail = tail->previous;
delete tail->next;
count -= 1;
}
IntList::iterator IntList::begin()
{
return iterator{ head };
}
IntList::iterator IntList::end() {
return iterator{ nullptr };
}
void IntList::push_front(int value) {
head = new IntNode{ value, nullptr, head };
if (!tail) { tail = head; }
count += 1;
}
bool IntList::empty() const{
return (count==0);
}
int& IntList::front() {
return *begin();
}
int& IntList::back() {
return *begin();
}
void IntList::clear() {
head = nullptr;
tail = nullptr;
count = 0;
}
IntList::iterator IntList::erase(iterator position) {
int midpointL = 0;
for (iterator index = begin(); index != position; ++index) {
midpointL++;
}
if (midpointL == 0) {
head = head->next;
}
else if (midpointL == count) {
tail = tail->previous;
}
else {
// Move head to get a reference to the component that needs to be deleted
for (int i = 0; i < midpointL; i++) {
head = head->next;
}
// Change the previous and next pointers to point to each other
(head->previous)->next = (head->next);
(head->next)->previous = (head->previous);
for (int i = midpointL-1; i > 0; i++) {
head = head->previous;
}
}
count-=1;
return position;
}
IntList::IntNode::IntNode(int v, IntNode * pr, IntNode * nx)
: previous{ pr }, next{ nx }, value{ v }
{
if (previous) { previous->next = this; }
if (next) { next->previous = this; }
}
IntList::IntNode::~IntNode() {
if (previous) previous->next = next;
if (next) next->previous = previous;
}
IntList::IntNode::iterator::iterator(IntNode* t)
: target{ t }
{}
int& IntList::IntNode::iterator::operator*() {
if (!target) { throw std::runtime_error{ "Deferenced sentinel iterator." }; }
return target->value;
}
IntList::IntNode::iterator& IntList::IntNode::iterator::operator++()
{
if (target) { target = target->next; }
return *this;
}
IntList::IntNode::iterator& IntList::IntNode::iterator::operator--()
{
if (target) { target = target->previous; }
return *this;
}
bool IntList::IntNode::iterator::operator!=(iterator other)const
{
return (!(target == other.target));
}
Could anyone help point me in the right direction?
Thanks!
end()returnbegin()? That just doesn't make sense.vectorcan be a memory fragmentation fatality waiting to happen. Mind you, in this world you pre-allocate all of the list nodes and when you run out... Well, what you do depends on what you happen to need the node for.