0

I need to add unique integer elements from 2 singly linked lists to a 3rd list (meaning I have to add elements that are met once in their own list, not both).

Yet, I either get EXC_BAD_ACCESS error, no output or only one element is in the 3rd list.

Here is my structure of Node in singly linked list and function to add elements to a list.

struct Node {
    int data;
    Node* next;
};

void addNode(Node** head_ref, int new_data) {
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

And function, that I use to add elements from one list to a list of unique elements:

void uniqueElements(Node* list1, Node* uniqueList) {
    int count = 1;
    for (Node *temp1=list1; temp1!=NULL; temp1=temp1->next){
        for(Node *temp2=list1; temp2!=NULL; temp2=temp2->next){
            if(temp1->data == temp2->data){
                count++;
            }
        }
        if(count == 1){
            addNode(&uniqueList, temp1->data);
        }
        count = 1;
    }
}

I fill the lists using for loop and addNode function, then I use uniqueElements function 2 times to fill the list of unique elements like this:

Node* listUnique = new Node;
uniqueElements(list1, listUnique);
uniqueElements(list2, listUnique);

I've tried lots of different methods, including using sets and maps, however they don't seem to fix the issue I have or add elements to a 3rd list. My only clue is that I reference to an empty list or null element of 3rd list.

I need to know how can I fix the code and output elements of 3rd list. How can I solve this problem?

Dharman
  • 30,962
  • 25
  • 85
  • 135
pineaapplepower
  • 11
  • 4
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – 463035818_is_not_an_ai Apr 24 '23 at 08:01
  • 1
    Why not to use std::forward_list ? Or if it is because of school then why the teachers teach how to write garbage code (world is full of) instead of standard library usage (important skill)? – Öö Tiib Apr 24 '23 at 08:07
  • You have to copy nodes, pr manage shared onwership (std::shared_ptr) or you might end up deleting one list and taking nodes still in other list with you. Anyway I recommend you just to use [std::list](https://en.cppreference.com/w/cpp/container/list) or at least learn from it. Nodes should be an internal design detail of a list and you should not be able to access from outside your list class directly (only access data in the list through function calls on the list) – Pepijn Kramer Apr 24 '23 at 08:28
  • 2
    And please give this to your teacher : https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines he seems to about 30 years out of date with C++ development. Almost nobody should be writing code with double pointers anymore and face the pain of manual memory management (unless you are in the very rare situation of having to write a new custom datastructure) – Pepijn Kramer Apr 24 '23 at 08:30
  • By the way: What if you introduce new duplicates because two nodes with equal value from two different lists are unique within their respective list? – Aconcagua Apr 24 '23 at 08:37
  • This is not C++, it's a C code, except new-expression. And I don't mean standard library avoidance or OOP. Never use double pointers unless absolutely necessary. Never, EVER use `NULL`. The `( )` in `(*head_ref)` expression look suspicious for C++ code. – Swift - Friday Pie Apr 24 '23 at 08:38
  • The only thing that stops me from using libraries is assignment to make our own singly linked list, which.. wasn't explained well to say the least. – pineaapplepower Apr 24 '23 at 09:06
  • 1
    Which part of the code is given to you and cannot be modified? Is there any requirement about the parameters and return type of the functions you are required to provide? It is not clear whether the given two lists are guaranteed to have unique values only. With which code have you tested your implementation that resulted in the error? How were list1 and list2 initialised? – trincot Apr 24 '23 at 09:53
  • I initialised list1 and list2 as Node* = nullptr. – pineaapplepower Apr 24 '23 at 09:58
  • So you've answered my last question. With what code are these lists populated? What about the other questions? – trincot Apr 24 '23 at 10:06
  • As said in question, I populated lists using for loop and cin integers. Basically the only part that can't be modified is struct Node, which was given to us. No requirement about values that should be returned, but it's best to use integers, since those are easier to test with. Error resulted due to using "cout << listUnique->data << endl;". Feel free to ask more, if something seems unclear. – pineaapplepower Apr 24 '23 at 10:13
  • So the `addNode` function was your work, and not part of the given material? – trincot Apr 24 '23 at 10:30
  • Can the `Node` struct be redefined so it has *methods*? – trincot Apr 24 '23 at 10:37
  • In other words, can we provide an answer where **all** code can be revamped, or is there something that really cannot be touched? – trincot Apr 24 '23 at 10:45
  • Yes, all code can be revamped. – pineaapplepower Apr 24 '23 at 10:48
  • And yes, addNode was my work and Node can be redefined. – pineaapplepower Apr 24 '23 at 10:54
  • Can we keep the list1 (and list2) sorted while elements are added to it? Or should we keep the elements in their insertion order? – trincot Apr 24 '23 at 11:08
  • Insertion order. – pineaapplepower Apr 24 '23 at 11:24
  • Is it guaranteed that list1 has no duplicates, or should the code verify this? (same for list2) – trincot Apr 24 '23 at 11:26
  • Is there any requirement for the order of the elements in the merged list, or can they be in any order? – trincot Apr 24 '23 at 11:29
  • It's not guaranteed that any of the lists have no duplicates. Elements can be in any order. – pineaapplepower Apr 24 '23 at 11:49
  • In that case it would make sense to sort the two input lists. Either in place (so the original order is lost), or by creating new lists from them that are sorted. Is either of these two acceptable? If not, the merge will have quadratic complexity. Is that time complexity acceptable? – trincot Apr 24 '23 at 12:09

1 Answers1

0

Your uniqueElements function has the wrong signature

It should be

void uniqueElements(Node* list1, Node** uniqueList) {
    ...
    if(count == 1){
        addNode(uniqueList, temp1->data);
    }
    ...
}

Just as you needed a double pointer for addNode you also need a double pointer for uniqueElements because it's adding nodes to uniqueList.

Then your calling code should look like this

Node* listUnique = nullptr;          // empty list
uniqueElements(list1, &listUnique);
uniqueElements(list2, &listUnique);

The next thing you should consider doing is writing a genuine list class. Node* is not a list, it's a pointer. You really need a class like this

class List
{
public:
    // list methods, e.g. addNode
private:
    Node* head_node;
};

But maybe that's not part of the assignment you have been given.

john
  • 85,011
  • 4
  • 57
  • 81
  • Agree on the list class – apart from I'd rather recommend *returning* the new list, this doesn't require providing a dummy node, such as: `Node* unique(Node* node) { Node* u = nullptr; for() { for() { ... } if(count == 1) { if(!u) { u = new Node(data); } else { addNode(...); } } } return u; }` – Aconcagua Apr 24 '23 at 08:33