-1

I am trying to make a way to take two Linked List objects (doubly-linked), say LL1 and LL2, and remove the 'overlapping' elements within LL1 which also appear in LL2. So for example if:

LL1 = {1,2,3};
LL2 = {9,2,8};

I want an output of:

LL1 = {1,3};

I am trying to do this via overloading the '-=' operator to work with two linked list objects. It compiles fine, but I'm getting a 'segmentation fault (core dumped)' error during runtime at the '-=' operator call. Not sure why. Below is my code. Any help would be appreciated, thankyou kindly.

Node.h:

// Node.h
/*******************************/
// Last Updated: Tues Aug 31 2021
// Program Description: Header file for Node

#ifndef NODE_H
#define NODE_H
#include <iostream>
#include <cstdlib>
#include "EToll.h"

using namespace std;

class Node {
    
    public:
        typedef EToll value_type; //typedef - now value_type is synonym for EToll object
        
        //Constructors:
        Node(); //default
        Node(value_type&); //constructor with 1 arg - data item
        Node(const value_type& i, Node* n, Node* p); //specific constructor with 3 arguments
        
        //Destructor:
        ~Node();
        
        //mutators (setters):
        void set_next(Node*);
        void set_prev(Node*);
        void set_data(const value_type&);
        
        //accessors (getters):
        Node* get_next() const;
        Node* get_prev() const;
        value_type& get_data();
        
    private:
        Node* next; //ptr to next (or NULL)
        Node* prev; //ptr to prev (or NULL)
        value_type data; //the payload

};

#endif

Node.cpp:

// Node.cpp
/*******************************/
// Last Updated: Tues Aug 31 2021
// Program Description: Implementation of Node

#include "Node.h"
#include <cstdlib>

//Constructors:
Node::Node() //default constructor
{
    data = value_type(); //creates an empty EToll object, since value_type is a synonym for EToll
    next = NULL;
    prev = NULL;
}

Node::Node(value_type& item) //constructor with 1 argument - a data item
{
    data = item;
    next = NULL;
    prev = NULL;
}

Node::Node(const value_type& i, Node* n, Node* p) //constructor with 3 arguments
{
    data = i;
    next = n;
    prev = p;
}

//Empty destructor:
Node::~Node(){}

//Mutators (setters):
void Node::set_next(Node* next_ptr) {next = next_ptr;}
void Node::set_prev(Node* prev_ptr) {prev = prev_ptr;}
void Node::set_data(const value_type& new_data) {data = new_data;}

//Accessors (getters):
Node* Node::get_next() const {return next;}
Node* Node::get_prev() const {return prev;}
/* Note that get_data() has Node::value_type& instead of value_type& as it's return type as the 
compiler doesn't check if the return type of a function is part of a member function, and thus
it doesn't look in Node for a value_type. A more detailed explanation can be found at: https://stackoverflow.com/questions/68991650/error-value-type-does-not-name-a-type-in-c */
Node::value_type& Node::get_data() {return data;}

LinkedList.h:

// LinkedList.h
/*******************************/
// Last Updated: Tues Aug 31 2021
// Program Description: Header file for LinkedList

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.h"
#include <iostream>
#include <cstdlib>
#include <string>

class LinkedList 
{
public:
    typedef Node::value_type value_type;

    //Constructor:
    LinkedList();
    
    //Destructor:
    ~LinkedList();
    
    //Insert function:
    //void insert(value_type& item);
    
    //length function:
    int length();
    
    //count function:
    int count(string);
    
    //totalIncome function:
    double totalIncome();
    
    //addTo functions:
    void addToHead(value_type&);
    void addToTail(value_type&);
    
    //accessors (getters):
    value_type& getHead();
    Node* getHeadAdd();
    value_type& getTail();
    
    //remove functions:
    void removeFromHead();
    void removeFromTail();
    void remove(string);
    void removeByNode(Node* c); //remove a particular node
    
    //search funciton:
    //Preconditions: None
    //Postconditions: Current points to the first Node storing the target, and true is returned. If not present, current is NULL and false is returned
    bool search(const value_type& target);
    
    //concatenation operator (+=) overload:
    //Preconditions: LL1 and LL2 are instances of LinkedList
    //Postconditions: Each Node of LL2 is traversed. At each individual Node, itis appended to LL1
    LinkedList operator += (const LinkedList& LL2);
    
    //remove overlap operator (-=) overload:
    //Preconditions: LL1 and LL2 are instances of LinkedList
    //Postconditions: Each Node of LL2 is traversed. At each individual Node, it's match is searched for within LL1. If a match is found, the matching Node in LL1 is deleted and the next node in LL2 is traversed
    LinkedList operator -= (const LinkedList& LL2);
    
    //NEED A .COUNT FUNCTION!!
    
        
private:
    Node* head;
    Node* tail;
    Node* current;
};

//stream insertion operator (<<) overload:
    //Preconditions: LinkedList obj "LL" exists and we wish to output it
    //Postconditions: LL exists without change
    ostream& operator << (ostream& out, LinkedList& LL);

#endif

LinkedList.cpp:

// LinkedList.cpp
/*******************************/
// Last Updated: Wed Aug 31 2021
// Program Description: Implementation of LinkedList

#include "LinkedList.h"
#include <cstdlib>

//Constructors:
LinkedList::LinkedList() //default constructor
{
    head = NULL;
    tail = NULL;
    current = NULL;
}

//Empty destructor:
LinkedList::~LinkedList(){}

//length() function:
//Preconditions: None
//Postconditions: A count of the nodes is returned (ie no of nodes in the LinkedList)
int LinkedList::length() 
{
    int answer = 0;
    for (current = head; current != NULL; current = current->get_next()) 
    {
        answer++;
    }
    return answer;
}

//count function:
int LinkedList::count(string type) 
{
    int returnCount = 0;
    
    //cycle through LinkedList:
    for (current = head; current != NULL; current = current->get_next()) 
    {
        //check for match:
        if (type == current->get_data().get_type())
        {
            //increment the counter
            returnCount++;
        }
    }
    
    return returnCount;
}

//totalIncome function:
double LinkedList::totalIncome() 
{
    double returnTotal = 0;
    
    //cycle through LinkedList:
    for (current = head; current != NULL; current = current->get_next()) 
    {
        returnTotal = returnTotal + current->get_data().get_charge();
    }
    
    return returnTotal;
}

//addToHead function:
//Preconditions: None
//Postconditions: A new node storing the supplied item is created and linked in to be list's new head
void LinkedList::addToHead(Node::value_type& item) 
{
    Node* newNode = new Node(item);
    
    //Check if the list is empty:
    if (length() == 0) 
    { //list is empty, so:
        head = newNode;
        tail = newNode;
    } else 
    { //list is not empty, so:
        head->set_prev(newNode);
        newNode->set_next(head);
        head = newNode;
    }
    
    /*
    head = new Node(item, head, NULL);
    //In case the list is empty:
    if (tail == NULL) 
    {
        tail = head;
    }
    */
}

//addToTail function:
//Preconditions: None
//Postconditions: A new node storing the supplied item is created and linked in to be list's new tail
void LinkedList::addToTail(Node::value_type& item) 
{
    Node* newNode = new Node(item);
    
    //Check if the list is empty:
    if (length() == 0) 
    { //list is empty, so:
        head = newNode;
        tail = newNode;
    } else 
    { //list is not empty, so:
        tail->set_next(newNode);
        newNode->set_prev(tail);
        tail = newNode;
    }
}

//getHead function:
Node::value_type& LinkedList::getHead() 
{
    return head->get_data();
}

//getHeadAdd function:
Node* LinkedList::getHeadAdd() 
{
    return head->get_next()->get_prev();
}

//getTail function:
Node::value_type& LinkedList::getTail() 
{
    return tail->get_data();
}

//removeFromHead function:
void LinkedList::removeFromHead() 
{
    Node* temp;
    temp = head->get_next();
    if (head != NULL) 
    {
        temp->set_prev(NULL);
        head = temp;
    } else 
    { //list is empty, so update the tail
        tail = NULL;
    }
}

//removeFromTail function:
void LinkedList::removeFromTail() 
{
    Node* temp;
    temp = tail->get_prev();
    if (head != NULL) 
    {
        temp->set_next(NULL);
        tail = temp;
    } else 
    { //list is empty, so update the head
        head = NULL;
    }
}

//remove function: removes a Node by a string input
void LinkedList::remove(string l) 
{
    //cycle through LinkedList:
    for (current = head; current != NULL; current = current->get_next()) 
    {
        //check for match:
        if (l == current->get_data().get_licence() && current == head) 
        {
            removeFromHead();
        } else if (l == current->get_data().get_licence() && current == tail) 
        {
            removeFromTail();
        } else if (l == current->get_data().get_licence()) 
        {
            //delete the node
            removeByNode(current);
        } else
        {
            //do nothing, move on to next iteration of for loop
        }
    }
}

//removeByNode function:
//Preconditions: input c points to a node to be removed
//Postconditions: the node pointed to by c before is now gone. current now points to head
void LinkedList::removeByNode(Node* c)
{
    current = c;
    current->get_prev()->set_next(current->get_next());
    current->get_next()->set_prev(current->get_prev());
    delete current;
    current = head;
}

//search function:
bool LinkedList::search(const Node::value_type& target)
{
    for (current = head; current != NULL; current = current->get_next()) 
    {
        if (target == current->get_data())
        {
            return true;
        }
    }
    //else:
    return false;
}

// += operator   overload (new):
LinkedList LinkedList::operator += (const LinkedList& LL2) 
{
    LinkedList* t = this;
    Node* temp = LL2.head;
    
    while (temp != NULL) 
    {
        t->addToTail(temp->get_data());
        temp = temp->get_next();
    }
    
    return *t;
}

// -= operator overload:
LinkedList LinkedList::operator -= (const LinkedList& LL2) 
{
    LinkedList* t = this;
    Node* temp1;
    Node* temp2;
    
    //Cycle through LL2:
    for (temp2 = LL2.head; temp2 != NULL; temp2 = temp2->get_next()) 
    {
        //Cycle through LL1:
        for (temp1 = t->head; temp1 != NULL; temp1 = temp1->get_next()) 
        {
            //Check if current of LL1 has a match in LL2:
            if (temp1->get_data() == temp2->get_data()) 
            {
                t->removeByNode(temp1);
            }
        }
    }
    
    return *t;
}

-= operator overload (within LinkedList.cpp, just putting it here under new heading for easy location):

// -= operator overload:
LinkedList LinkedList::operator -= (const LinkedList& LL2) 
{
    LinkedList* t = this;
    Node* temp1;
    Node* temp2;
    
    //Cycle through LL2:
    for (temp2 = LL2.head; temp2 != NULL; temp2 = temp2->get_next()) 
    {
        //Cycle through LL1:
        for (temp1 = t->head; temp1 != NULL; temp1 = temp1->get_next()) 
        {
            //Check if current of LL1 has a match in LL2:
            if (temp1->get_data() == temp2->get_data()) 
            {
                t->removeByNode(temp1);
            }
        }
    }
    
    return *t;
}

-= operator call within another 'main()' program:

LinkedList tollBooth1;
LinkedList tollBooth2;
LinkedList dailyReport;

//(add data to tollBooth 1 and 2, merge these 2 objects into dailyReport)

//removing the contents of both booths from daily report:
dailyReport -= tollBooth1;
dailyReport -= tollBooth2;
Daniel Dinosaur
  • 19
  • 2
  • 1
    Why don't you use standard [C++ containers](https://en.cppreference.com/w/cpp/container) ? – Basile Starynkevitch Sep 03 '21 at 05:39
  • Have you tried to catch the crash in a debugger to locate *exactly* where it happens? – Some programmer dude Sep 03 '21 at 05:41
  • Or possibly used the debugger to step through the code statement by statement while monitoring variables and their values? At the same time draw out all operations using pen and paper, with boxes for the nodes and arrows for all pointers. Draw and redraw arrows as you modify the pointers. Does it all make sense in your drawing? Does all arrows point to something valid? – Some programmer dude Sep 03 '21 at 05:42
  • Looks like `removeByNode` deletes `temp1` then `temp1 = temp1->get_next()` uses it after that. – Retired Ninja Sep 03 '21 at 05:47
  • *t compiles fine* -- If all that was required is for programs to compile fine, there would be no such thing as bugs. Compiling fine only means that there are no syntax errors -- it has no bearing on whether the program is logically correct. Also [what is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). – PaulMcKenzie Sep 03 '21 at 05:48
  • As to your issue -- you are returning `LinkedList` by value in those overloaded operator functions, for example: `LinkedList LinkedList::operator -=`. Your `LinkedList` class has incorrect copy semantics, since it violates the [rule of 3](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three). So you should first work on making your class safely copyable before even thinking about writing other functions that return by value. – PaulMcKenzie Sep 03 '21 at 05:52
  • To give you a simple case `LinkedList l1; LinkedList l2;` fill in either of those lists with values, and if you tried to simply do this `l1 = l2;`, you're in trouble. You also have an empty `LinkedList` destructor, which adds further to the problem. In short, you need to implement a user-defined copy constructor, assignment operator, and destructor for any of your attempts of writing `-=` operators to work. – PaulMcKenzie Sep 03 '21 at 05:57
  • `//Empty destructor: Node::~Node(){}` -- Do not write empty destructors unless the destructor is `virtual`. Second, it seems you left the destructors out as an afterthought. Never write empty or incomplete stubs of functions that are integral in how your classes will operate at runtime. This includes copy constructors, assignment operators, move operations, and destructors. Maybe for compilation purposes you can do this, but never actually run such a program with these incomplete functions, as those functions *will* be called, either implicitly or excplicitly. – PaulMcKenzie Sep 03 '21 at 06:05

1 Answers1

0

You've included way too much code. The general ask on this site is to provide a minimal reproducible example.

Problems

  1. I have no idea why you have a member variable named current. It often points to deleted memory.

  2. You need to implement the "rule of three" or the "rule of five" on your LinkedList class. If you copy the LinkedList, and then modify it, you will have dangling pointers.

    LinkedList a;
LinkedList b = a;
a.RemoveHead();
// b.head is now pointing to deleted memory.

  3. LinkedList::removeByNode(Node* c) does not update the head and tail member variables if the removed node was the head or tail respectively.

  4. Your operator-= uses temp1 after it has been deleted.

There are likely more issues.

user4581301
  • 33,082
  • 7
  • 33
  • 54
Bill Lynch
  • 80,138
  • 16
  • 128
  • 173