-2
\$\begingroup\$

A friend of mines needed some help. He wanted to build up two linked list and then compared them to see if they had the same data values. Finally a 3rd link list would contain the nodes with duplicated data. The linked list holds int data btw. I redid his code and I was aiming to be as simple and clean as possible but I have a shaky feeling. Below is my code and his code together. I feel there is something to learn from both of us so I posted both of our codes although my solution is fully finished. Is my code simple and clean? Is my friend's code formatted in such a way that my code is missing it? Does my look good on the eyes. Critique on both solution would help me grow a bit.

Laurent's code

#include <iostream>
#include <cstdlib>

using namespace std;

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

class LinkedList{
private:
    int length;
    Node* head;
public:
    LinkedList();
    ~LinkedList();
    Node* getHead();
    void appendToTail(int data);
    void appendExistingNodesToTail(Node* newtail, int data); //Takes a collection of node pointers. This is used to append existing nodes from other lists to it own list. 
    void insertToHead(int data);
    void print();
};
LinkedList::LinkedList(){
    this->length = 0;
    this->head = NULL;
}
LinkedList::~LinkedList(){  
    //avoid memory leaks.... give back what you take
    Node* next = head;
    Node* cur = NULL;
    while (next != NULL) {
        cur = next;
        next = next->next;
        delete cur;
    }
    cout << "LIST DELETED"<< endl;
}
Node* LinkedList::getHead(){
    return head;
}
void LinkedList::appendToTail(int data){
    Node *newtail = new Node;
    newtail->data = data;
    newtail->next = nullptr;

    if (this->head == nullptr) {
        head = newtail;
    } 
    else {
        Node *temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newtail;
        this->length++;
    }
}
void LinkedList::appendExistingNodesToTail(Node* newtail, int data){
    newtail = new Node;
    newtail->data = data;
    newtail->next = nullptr;

    if (this->head == nullptr) {
        head = newtail;
    } 
    else {
        Node *temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newtail;
        this->length++;
    }
}
void LinkedList::insertToHead(int data){
    Node* newhead = new Node;
    newhead->data = data; 
    newhead->next = this->head; 
    this->head = newhead;
    this->length++;
}
void LinkedList::print(){
    Node* head = this->head;
    int i = 1;
    while(head){
        std::cout << i << ": " << head->data << std::endl;
        head = head->next;
        i++;
    }
    cout << endl;
}
//-------------------------------------GENERAL PURPOSE FUNCTIONS------------------------------------------//
void generateDuplicateNodeDataFound(LinkedList* list_a, LinkedList* list_b, LinkedList* list_c){ //Find the duplicate values to build up list c from existing nodes from list a&b. Need two list to compare, one list to build
    Node* head1 = list_a->getHead();
    Node* head2 = list_b->getHead();

    while(head1){
        while(head2){
            if (head1->data == head2->data){
                list_c->appendExistingNodesToTail(head1, head1->data);
                break;
            }
            head2 = head2->next;        
        }
        head1 = head1->next;
        head2 = list_b->getHead(); // Reset
    }
}
int main(int argc, char const *argv[]){

    LinkedList* list1 = new LinkedList();
    LinkedList* list2 = new LinkedList();
    LinkedList* list_found_duplicates = new LinkedList(); 

    int arr1[] = {2,5,7,9,0,2};
    int arr2[] = {9,78,3,2,5,9};

    //https://stackoverflow.com/questions/37538/how-do-i-determine-the-size-of-my-array-in-c
    int lenght = sizeof(arr1) / sizeof(arr1[0]);
    for(int i=0; i<lenght; i++){
        list1->appendToTail(arr1[i]);
    }
    lenght = sizeof(arr2) / sizeof(arr2[0]);
    for(int i=0; i<lenght; i++){
        list2->appendToTail(arr2[i]);
    }

    list1->print();
    list2->print();

    generateDuplicateNodeDataFound(list1, list2, list_found_duplicates);
    list_found_duplicates->print();

    delete list1;
    delete list2;
    delete list_found_duplicates;

    cin>> arr1[0];

    return 0;
}

Laurent's Friend code

#include <iostream>
#include <cstdlib>
using namespace std;
class Node{
  public:
    Node(int value= 0, Node* nextNode= nullptr);
    void insertAfter(Node* newPtr);
    Node* getNext();
    int getValue();
  private:
    int val;
    Node* nextNodePtr;
};
Node::Node(int value, Node* nextNode){
  this->val= value;
  this->nextNodePtr= nextNode;
}
void Node::insertAfter(Node* newPtr){
  Node* tempPtr = nullptr;
  tempPtr= this->nextNodePtr;
  this->nextNodePtr = newPtr;
  newPtr->nextNodePtr =tempPtr;
}
Node* Node::getNext(){
  return nextNodePtr;
}
int Node::getValue(){
  return this->val;
}

bool search(int Key, Node* temp){
  bool found= false;
  if(temp!= nullptr){
    while(Key != temp->getValue()){
      temp= temp->getNext();
      cout<<Key<<" , "<<temp->getValue()<<endl;
      if(temp->getNext() == 0){
        found= false;
        break;
      }
    }
    if(Key==temp->getValue()){
      found=true;
    }
  }
  return found;
}
//tries to intersect
void intersect(Node* start1, Node* start2,Node* node){
  Node* node1 = start1;
  Node* node2 = start2;
  Node* temp= nullptr;
  cout<<"\n!i am here!\n";
  while(node1!=nullptr){
    cout<<"\n"<<node1->getValue()<<"\n";
    cout<<"\n!i am here now!\n";
    if (search(node1->getValue(), node2)){
      node->insertAfter(node1); 
      node=node->getNext();
    }
    node1= node1->getNext();

  }

}
// prints liked list
void printList(Node* start){

  while(start->getNext()!= nullptr){
    cout<<start->getValue()<<" ";
    start= start->getNext();
  }
  cout<<start->getValue();
  cout<<endl<<endl;
}
//merging algorithm 
void merge(Node* start,Node* end, Node* node){
  cout<<start->getValue()<<" ";
  while(start->getNext()!= nullptr){
    cout<<start->getValue()<<" ";
    node->insertAfter(start);
    node= node->getNext();
    start= start->getNext();
  }
  while(end->getNext()!=nullptr){
    cout<<start->getValue()<<" ";
    node->insertAfter(end);
    end= end->getNext();
  }
}


int main() {
  Node* new1= nullptr;
  Node* new2= nullptr;
  Node* new3= nullptr;
  int arr[]={2,5,7,9,0,2};
  new1 = new Node(arr[0]);
  new3= new1;
  for(int i=1; i<6;i++){
    new2 = new Node(arr[i]);
    new3->insertAfter(new2);
    new3=new2;
  }
  printList(new1);
  cout<<endl;
  Node* newst = nullptr;
  new2= nullptr;
  new3= nullptr;
  int arr1[]={9,78,3,2,5,9};
  newst = new Node(arr1[0]);
  new3= newst;
  for(int i=1; i<6;i++){
    new2 = new Node(arr1[i]);
    new3->insertAfter(new2);
    new3=new2;
  }

  cout<<endl;

  printList(newst);
  if(search(1,new1)){
    cout<<"ll\n";
  }
  cout<<"\nll\n";
  if(search(7,newst)){
    cout<<"lol\n";
  }
  Node* inter = new Node(0);
  intersect(new1, newst, inter);
  printList(inter);
}
\$\endgroup\$

closed as off-topic by hoffmale, Mast, Snowhawk, Quill, 200_success Nov 22 '18 at 23:28

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – hoffmale, Snowhawk, Quill, 200_success
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Is your friend aware that you posted their code and allowed you to post it under CC-BY-SA? By the way, you likely want to add the comparative-review tag. \$\endgroup\$ – Zeta Nov 22 '18 at 3:43
  • \$\begingroup\$ No, I didn't think it was a big deal because it was for an up coming school assignment. I will ask them and keep and remove the code by their wishes. Edit They don't care. \$\endgroup\$ – Laurent Nov 22 '18 at 4:06
  • \$\begingroup\$ Which version of C++ is this targeting? Any? C++98? Or a more modern version, like C++11/14/17? // If this was a solution to an exercise question, it might be helpful to include that question in its original wording. Small details matter! \$\endgroup\$ – hoffmale Nov 22 '18 at 5:03
  • 1
    \$\begingroup\$ Friend's code has two (identical?) mains. You may want to remove one. \$\endgroup\$ – vnp Nov 22 '18 at 5:57
  • 5
    \$\begingroup\$ The output of those 2 "solutions" are very different. Even if one ignores the rest, the output of the intersection is {2, 5, 9, 2} in your code and {0, 2} in your friends' code. // Is the repetition of 2 in the result set intended? Why do those two implementation give different results? To me, it seems like the code either isn't working as intended, or there is some context missing why both answers would be correct. \$\endgroup\$ – hoffmale Nov 22 '18 at 8:40
4
\$\begingroup\$
  • Avoid using namespace std;. This can easily lead to name clashes. While a recommendation in source files, absolutely no-go in header files(!).

  • It's a good idea to encapsulate the linked list into its own class. However, still anybody could modify the nodes in the list unsupervised, in worst case destroing the list or creating memory leaks. So nobody should be able to change the next pointer apart from LinkedList class. Solution: Make the pointer private and LinkedList a friend of Node; as then Node gets closely coupled to LinkedList, it would be more apprpriate to make the former a nested class of the latter.

  • Give Node class a constructor accepting the value and setting its successor node to nullptr - as your friend did. You don't need accessor functions, remember, you made LinkedList friend (see above). In contrast to your friend, use the constructors initialiser list, though:

    Node::Node(int data, Node* next)
    : data(data), next(next)
    { }

  • What did you intend with appendExistingNodesToTail? It does exactly the same as appendToTail, the first parameter is unused and gets overwritten immediately. If you intended to append multiple nodes (then second parameter is not needed): Better accept another LinkedList as const reference and copy the internal data from.

  • In both forementioned functions you forgot to set length to one if the list was empty before. Easiest fix: move length++ out of the else clause to the very end of the function.

  • You have appendToTail - for symmetry, I'd name the other function prependToHead.

  • You did not provide search/find function as your friend did; albeit it was just a helper function for your friend, it still would nicely fit into your linked list's interface.

  • You are re-inventing the wheel! While it might be a good exercise, once you're done with, switch over to std::list<int> (doubly linked) or std::forward_list<int> (singly linked).

  • Your friend's merge algorithm is broken:

So far for the linked list...

  • intersect is the better name (describing the same, but much shorter).

  • Intersection: Assuming you have lists { 7 } and { 7, 7 }, then your friend's algorithm will output { 7 } while yours will: { 7, 7 }. If you swap arguments, both algorithms will output { 7, 7 }, i. e. your friend's variant is not symmetric. Your variant, though, with { 7, 7 } and { 7, 7 } as arguments, will yield { 7, 7, 7, 7 }! To avoid, you'd have to check if the current head1 element has occured in the list before. But if you do so in the native approach, you'd get an O(n³) algorithm from one that already now is O(n²). So we should really look for better alternatives. If it is fine to modify the lists, you could sort both of them in advance, then finding duplicates is straight forward and O(n). If want to retain original order, you might operate on duplicates instead (possibly copy the data into arrays for faster access and saving memory).

  • ... in theory at least. Actually, your friend's intersect algorithm is broken: after node->insertAfter(node1);, node1's successor is whatever nodes was before, and the rest of the linked list gets lost (leaking). From a point of view of design, it's not a good idea to change the input lists anyway. Your friend would need to create new nodes as you did.

  • Your friend's merge algorithm is broken as well, suffers from same bad usage of insertAfter as intersect does already. Additionally: Why do we need three pointers? We'd pass two lists, merge them into one single list, and best: return pointer to new head. Your friend's algorithm seemd to try to merge as x[0], y[0], x[1], y[1], .... One could. But what's the benefit from? The lists are not sorted anyway, so one could just as well only append one to the other.

My personal assessment: Albeit there are yet a few issues left open, you already did quite a good job on improving the original interface of your friend...

One final issue about your main:

LinkedList* list1 = new LinkedList();
// ...
delete list1;

It is good that you delete what you newed. You can avoid explicit deletion by usage of a smart pointer:

std::unique_ptr<LinkedList> list1(new LinkedList());

but why new at all? Your class is not that big that you might risk to consume up too much of the stack, so just do:

LinkedList  list1;
//        ^ no pointer!

This will create a variable with scope local to main function and as soon as the scope is left, the object is destroyed automatically (just as with the smart pointer; actually, the smart pointer works exactly the same, deleteing the object it points to in its destructor).

\$\endgroup\$
  • \$\begingroup\$ Re "To avoid, you'd advance head1 as long as it is equal to its predecessor.": IIUC, that still wouldn't prevent {7, 2, 7} and {7} returning {7, 7}. A better way would be to check whether the current value is already in the result list. \$\endgroup\$ – hoffmale Nov 22 '18 at 7:47
  • \$\begingroup\$ @hoffmale Oh, you're absolutely right... Too much used to sorted input! Thanks for the hint! \$\endgroup\$ – Aconcagua Nov 22 '18 at 7:49
  • \$\begingroup\$ @ 'is already in the result list' - one option. { 7, 7 } and { 7, 7 } would yield { 7 } then, though. Possibly valid, unsuitable, if we wanted to get { 7, 7 } instead... Did not thing thoroughly enough about to be 100% sure, but I think this would give an O(n³) algorithm. \$\endgroup\$ – Aconcagua Nov 22 '18 at 8:05
  • \$\begingroup\$ Well, that's why I asked for clarification in my comments on the question. Too much hinges on what the expected output should be. // Making some assumptions: If the output order isn't important, one could just sort the input lists in \$\mathcal{O}(n \log n)\$ and then implement your original suggestion for a total complexity of \$\mathcal{O}(n \log n)\$. Still, in that case, there is a better linear algorithm: Insert all items from list1 into an std::unordered_set. Then do a pass over list2: For each item, if it is in the set, remove it from the set and add it to the output list. \$\endgroup\$ – hoffmale Nov 22 '18 at 8:31
  • \$\begingroup\$ @hoffmale The hashing approach is nice (std::unordered_multiset would allow for multiple values...). Initial try was to avoid additonal memory usage, so sorting the lists in place, but with proposition of the duplicates left that territory anyway. Finally, you are right, we are already too deep in the field of assumptions. Let's see what OP answers... \$\endgroup\$ – Aconcagua Nov 22 '18 at 9:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.