0

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!

7
  • 1) std::list already exists. 2) you probably really just want to use a std::vector instead (in real life, a linked list is a horrible data structure with abysmal performance). Commented Oct 3, 2017 at 17:04
  • I think he is doing this for practice, also Linked Lists have their own usage such as when you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical) Commented Oct 3, 2017 at 17:21
  • "int& IntList::back() { return begin(); }" - that just looks *wrong. Why yould end() return begin()? That just doesn't make sense. Commented Oct 3, 2017 at 17:21
  • @BlooB the research aspect is valid (but OP could have mentioned that he was doing it for learning purposes). The Big O argument doesn't really hold in real life - modern CPUs really don't like chasing pointers all over memory (which is what you'll be doing while looking for your insertion point) - a vector is much, much friendlier to the prefetcher. Sure, in theory lists have faster insertion, but in practice; vector beats them every time. Commented Oct 3, 2017 at 17:25
  • 1
    I share @JesperJuhl 's assessment, but on a low end micro controller, without all the bells and whistles of a modern processor, a linked list ain't that bad, and a vector can 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. Commented Oct 3, 2017 at 18:03

1 Answer 1

1

Let's make a kind of quick review here:

IntList::~IntList() {
    while (head) {
        head = head->next;
        delete head;
    }
}

you should do instead:

IntList::~IntList() {
    while (head) {
        IntNode* newHead = head->next;
        delete head;
        head = newHead;
    }
}

as you are deleting the "next" object and then you are trying to get access to it in the next iteration.

void IntList::pop_back() {
    tail = tail->previous;
    delete tail->next;
    count -= 1;
}

Here you are not checking if tail is null or if it is pointing to head..(what's the empty condition?), maybe count!=0? in case you may delete a not existing next-node

IntList::iterator IntList::end() {
    return iterator{ nullptr };
}

..end is null? ebd should be your tail...

int& IntList::back() {
    return *begin();
}

that's begin..not back.

void IntList::clear() {
    head = nullptr;
    tail = nullptr;
    count = 0;
}

a clear should release all the objects in the list. You are generating garbage here (leaks).

I stopped here, sorry for that, it's just a coffee break. But you should look carefully at: * null pointer usage * delete your node list item when not needed * pay attention to do not use invalid pointers (like head->previous->next I saw somewhere)

You have to review your code, bottom up. Hope that those first hints help you through your learning process.

Have fun, Ste

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.