Segmentation fault errors when implementing functions for a single linked list

Question

I'm trying to create a function for a Single Linked list that, starting from the i (argument) member, deletes every 2nd node. I'm doing this for benchmark purposes, I already have it working nicely in Java, but I haven't done much programming in C++ for a few years, so I'm a bit rusty.

void List::remove(long i) {
    bool changelastonfirstrun=false;
    if(i==size){                                                
        changelastonfirstrun=true;                            
    }
if(size==0||i>size){
    cout <<"Index out of bounds or empty list";
}
else{
    Node* aux=first;
    Node* aux2=new Node();
    int j=1;
    while(size>1&&i>1){

            for(j=1; j<(i-1); j++){
            aux=aux->Next();
            }
        aux2=NULL;
        aux2=aux->Next();
        aux->SetNext(aux2->Next());
        size--;
        i=i-2;
        if(changelastonfirstrun){
            last=aux;
            changelastonfirstrun=false;
        }
        if(i==1){                                             //updates reference if removing the first
            if(size>1){
                first=first->Next();
                size--;
                }
            if(size==1){                                      //Removing a unique member
                    clear();
                }

            }
    }
    delete aux, aux2;
}    
}

I'm getting the problem at

        while(size>1&&i>1){
        for(j=1; j<(i-1); j++){
        aux=aux->Next();
        }

As soon as I decrease i for the first time. If you need any more information, just tell me. Thank you.

code is definitely doing something different than what you are saying, my friend. — v78, Sep 22 '16 at 08:01
It looks like you need a thorough refresher on pointers - much more thorough than is appropriate for an SO post - but 1) a function that removes nodes shouldn't create any new nodes, and 2) `delete aux, aux2;` doesn't do what you think it does and a decent compiler would warn you about it. If you've lost your C++ book, start [here](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). If you haven't, read it. — molbdnilo, Sep 22 '16 at 08:06
Honestly, I don't know how I would get to the last node without those auxiliary nodes. Still, I'll try to refresh my pointer knowledge, I know I have been neglecting it for too long. — Wazowski, Sep 22 '16 at 08:50

score 0 · Answer 1 · answered Sep 22 '16 at 09:05

Recursion is a nice tool

// Example program
#include <iostream>

template <class T>
class Node {
private:
    T data_;
    Node *next_;
public:
    Node(const T &data) : data_(data), next_(nullptr) {}
    T data() const {return data_;}
    Node *next() const {return next_;}
    void setNext(Node *next) {next_ = next;}
};

template <class T>
class List {
private:
    size_t size_;
    T *begin_;
public:
    List() : size_(0), begin_(nullptr) {}
    size_t size() const {return size_;}
    void push_back(T *node) {
        if ( size_ ) {
            T *last = begin_;
            for(size_t ct = 0; ct < size_ - 1; ++ct)
                last = last->next();
            last->setNext(node);
        }
        else
            begin_ = node;
        ++size_;
    }
    T *begin() const {return begin_;}
    void removeEverySecondFrom(size_t startFrom) {
        if( startFrom >= size_ || size_ == 0)
            return;
        auto toDeleteNext = begin_;
        for(size_t ct = 1; ct < startFrom; ++ct)
            toDeleteNext = toDeleteNext->next();
        if( startFrom == size_ - 1 ) {
            toDeleteNext->setNext(nullptr);
            --size_;
        }
        else {
            T* toDelete = nullptr;
            if( startFrom == 0 ) {
                toDelete = begin_;
                begin_ = begin_->next();
            }
            else {
                toDelete = toDeleteNext->next();
                toDeleteNext->setNext(toDelete->next());
            }
            --size_;
            delete toDelete;
            removeEverySecondFrom(startFrom+1);
        }
    }
};

int main()
{
    using NodeType = Node<int>;
    using ListType = List<NodeType>;
    auto genList = [](){
        ListType list;
        for(size_t ct = 0; ct < 11; ++ct)
            list.push_back(new NodeType(ct));
        return list;
    };
    auto printList = [](const ListType& list){
        auto begin = list.begin();
        for(size_t ct = 0; ct < list.size(); ++ct) {
            std::cout << begin->data() << "\t";
            begin = begin->next();
        }
        std::cout << std::endl;
    };

    auto list = genList();
    printList(list);

    list = genList();
    list.removeEverySecondFrom(0);
    printList(list);

    list = genList();
    list.removeEverySecondFrom(1);
    printList(list);

    list = genList();
    list.removeEverySecondFrom(9);
    printList(list);

    list = genList();
    list.removeEverySecondFrom(10);
    printList(list);

    list = genList();
    list.removeEverySecondFrom(11);
    printList(list);
}

The output is

0   1   2   3   4   5   6   7   8   9   10  
1   3   5   7   9   
0   2   4   6   8   10  
0   1   2   3   4   5   6   7   8   10  
0   1   2   3   4   5   6   7   8   9   
0   1   2   3   4   5   6   7   8   9   10

Tested here http://cpp.sh/2egub

Segmentation fault errors when implementing functions for a single linked list

1 Answers1