List that contains only the elements of the one of the two given lists

[evinda]

Hi! (Smile)

Given two sorted lists $M_1, M_2$, I want to write an algorithm, that creates a new list $M_3$, that contains the elements of $M_1$, that do not exist in $M_2$.

That's what I have tried:

Algorithm(M1,M2){
    pointer q=M1, p=M2, M3;
    int same=0;
    if (M1==NULL) return error;
    else if (M2==NULL) return M1;

    while (q!=NULL){
            while (p!=NULL){
                    if (p->data==q->data){
                       same=1;
                    }
                    p=p->next;
            }
            if (same==0){
                M3=q;
                M3=M3->next;
            }
            q=q->next;
    }   
    return M3;

Could you tell me if it is right or if I have done something wrong? (Thinking)
Is there also a better way to do this?

 

[Evgeny.Makarov]

This is wrong. First, you never create a new list M3; you only assign to M3 some tail of (tail of tail of...) M1. Second, you never use comparison and therefore ignore the fact that the lists are sorted.

P.S. Don't put a comma before "that". See http://www.grammarly.com/handbook/punctuation/comma/28/comma-setting-off-restrictive-clauses/.

 

[evinda]

This is wrong.

So, is it totally wrong? (Worried)

First, you never create a new list M3; you only assign to M3 some tail of (tail of tail of...) M1. Second, you never use comparison and therefore ignore the fact that the lists are sorted.

How can we create then a new list? (Thinking)

Is it possible that we write an algorithm with time complexity $O(n+m)$, where $n$ is the number of elements of $M_1$ and $m$ is the number of elements of $M_2$?

P.S. Don't put a comma before "that". See http://www.grammarly.com/handbook/punctuation/comma/28/comma-setting-off-restrictive-clauses/.

Ok... (Nod)

 

[Evgeny.Makarov]

So, is it totally wrong?

I am afraid so.

How can we create then a new list?

For this you need to create a new record with fields [m]data[/m] and [m]next[/m]. I have not been following your other threads, so I am not sure how this is done in your programming language.

Is it possible that we write an algorithm with time complexity $O(n+m)$, where $n$ is the number of elements of $M_1$ and $m$ is the number of elements of $M_2$?

That's the idea. To do this, you need to use the fact that the lists are sorted.

I recommend considering several example lists and figuring out how the algorithm should work in those examples. Then formulate the general algorithm.

 

[evinda]

I tried this:

Algorithm(M1,M2){
  pointer p=M1, q=NULL, M3=NULL;
  while (p!=NULL){
           q=M2;
           while (q->data<p->data and q!=NULL){
                    q=q->next;
            }
            if (q->data!=p->data){
               if (M3==NULL) M3->data=p->data;
               else{
                      M3= M3->next
                      M3->data=p->data;
               }
            }
            p=p->next;
   }
}

But now the time complexity is $O(n \cdot m)$ instead of $O(n+m)$, right?
What could I change? (Thinking)

 

[johng1]

Evinda,
I'm afraid you're doomed to continue making errors until you're willing to let the computer help you by implementing your ideas with a real programming language.

1. while (q->data < p->data and q != null): If q is null, this won't work in any programming language that I know. If the language has "shortcut" evaluation (C++ or Java), you need to change the order of the conditions.

2. if (M3 == null) M3->data=p->data:
This fails period.

3. M3=M3->next;
M3->data=p->data; :
Even if somehow this would make sense, at the end of your algorithm, you have no way of accessing the created difference.

Following is a complete solution in C++. Notice to test the solution, you need to have sorted lists. The testing of all possible situations is an art; I think you ought to become familiar with this testing problem.

#include <cstdlib>
#include <cstddef>
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

/* class Node is as specified.  The linked lists are singly linked with no
 * header node.
 */

class Node {
public:
  int data;
  Node* next;
  Node():data(0),next(0){};
  Node(int x):data(x),next(0){};
};

/*  Makes a sorted linked list of nodes with "random" data fields.  This list
 * represents a multiset; i.e. not all data fields need be different.  The list
 * is created (for n != 0) by first creating a node with random data and then 
 * inserting a new node with random data into its proper position.
 */
Node* makeSortedList(int n) {
  if (n == 0) {
    return(NULL);
  }
  Node *first, *p, *q, *r;
  int x = rand() % 100, i;
  first = new Node(x);
  for (i = 1; i < n; i++) {
    x = rand() % 100;
    r = new Node(x);
    q = NULL;
    p = first;
    while (p != NULL && p->data < x) {
      q = p;
      p = p->next;
    }
    if (q == NULL) {
      r->next = first;
      first = r;
    } else {
      r->next = q->next;
      q->next = r;
    }
  }
  return (first);
}

/*  Just displays a list for debugging purposes.
 */
void printList(Node* first) {
  cout << "{";
  while (first != NULL) {
    cout << first->data << ", ";
    first = first->next;
  }
  cout << "}" << endl;
}

/* Upon entry A and B point to sorted "multiset" lists of size m and n, 
 * respectively.  This computes and returns a new list, the "multiset"
 *  difference A - B. The algorithm is "obviously" of order  m + n.
 */
Node* AminusB(Node* A, Node* B) {
  Node *first, *p = A, *q, *pB = B;
  first = NULL;
  if (A == NULL) {
    return (first);
  }
  while (pB != NULL) {
    while (p != NULL && p->data < pB->data) {
      if (first == NULL) {
        first = new Node(p->data);
        q = first;
      } else {
        q->next = new Node(p->data);
        q = q->next;
      }
      p = p->next;
    }
    if (p == NULL) {
      return (first);
    }
    if (p->data == pB->data) {
      p = p->next;
    }
    pB = pB->next;
  }
  if (first == NULL) {
    first = new Node(p->data);
    q = first;
    p = p->next;
  }
  while (p != NULL) {
    q->next = new Node(p->data);
    q = q->next;
    p = p->next;
  }
  return (first);
}

int main(int argc, char** argv) {
  Node *M1, *M2, *M3;
  M1 = makeSortedList(10);
  printList(M1);
  M2 = makeSortedList(15);
  printList(M2);
  M3 = AminusB(M1, M2);
  printList(M3);
  return 0;
}

 

[evinda]

1. while (q->data < p->data and q != null): If q is null, this won't work in any programming language that I know. If the language has "shortcut" evaluation (C++ or Java), you need to change the order of the conditions.

So we could also just change the order of the conditions at a pseudocode, or not?

3. M3=M3->next;
M3->data=p->data; :
Even if somehow this would make sense, at the end of your algorithm, you have no way of accessing the created difference.

So should the algorithm look like that?

Algorithm(M1,M2){
  pointer p=M1, q=NULL, M3=NULL, k=NULL;
  while (p!=NULL){
           q=M2;
           while (q->data<p->data and q!=NULL){
                    q=q->next;
            }
            if (q->data!=p->data){
               if (k==NULL) k->data=p->data;
               else{
                      k= k->next;
                      k->data=p->data;
               }
            }
            p=p->next;
   }
   M3=k;
   return M3;
}

Following is a complete solution in C++. Notice to test the solution, you need to have sorted lists. The testing of all possible situations is an art; I think you ought to become familiar with this testing problem.

#include <cstdlib>
#include <cstddef>
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

/* class Node is as specified.  The linked lists are singly linked with no
 * header node.
 */

class Node {
public:
  int data;
  Node* next;
  Node():data(0),next(0){};
  Node(int x):data(x),next(0){};
};

/*  Makes a sorted linked list of nodes with "random" data fields.  This list
 * represents a multiset; i.e. not all data fields need be different.  The list
 * is created (for n != 0) by first creating a node with random data and then 
 * inserting a new node with random data into its proper position.
 */
Node* makeSortedList(int n) {
  if (n == 0) {
    return(NULL);
  }
  Node *first, *p, *q, *r;
  int x = rand() % 100, i;
  first = new Node(x);
  for (i = 1; i < n; i++) {
    x = rand() % 100;
    r = new Node(x);
    q = NULL;
    p = first;
    while (p != NULL && p->data < x) {
      q = p;
      p = p->next;
    }
    if (q == NULL) {
      r->next = first;
      first = r;
    } else {
      r->next = q->next;
      q->next = r;
    }
  }
  return (first);
}

/*  Just displays a list for debugging purposes.
 */
void printList(Node* first) {
  cout << "{";
  while (first != NULL) {
    cout << first->data << ", ";
    first = first->next;
  }
  cout << "}" << endl;
}

/* Upon entry A and B point to sorted "multiset" lists of size m and n, 
 * respectively.  This computes and returns a new list, the "multiset"
 *  difference A - B. The algorithm is "obviously" of order  m + n.
 */
Node* AminusB(Node* A, Node* B) {
  Node *first, *p = A, *q, *pB = B;
  first = NULL;
  if (A == NULL) {
    return (first);
  }
  while (pB != NULL) {
    while (p != NULL && p->data < pB->data) {
      if (first == NULL) {
        first = new Node(p->data);
        q = first;
      } else {
        q->next = new Node(p->data);
        q = q->next;
      }
      p = p->next;
    }
    if (p == NULL) {
      return (first);
    }
    if (p->data == pB->data) {
      p = p->next;
    }
    pB = pB->next;
  }
  if (first == NULL) {
    first = new Node(p->data);
    q = first;
    p = p->next;
  }
  while (p != NULL) {
    q->next = new Node(p->data);
    q = q->next;
    p = p->next;
  }
  return (first);
}

int main(int argc, char** argv) {
  Node *M1, *M2, *M3;
  M1 = makeSortedList(10);
  printList(M1);
  M2 = makeSortedList(15);
  printList(M2);
  M3 = AminusB(M1, M2);
  printList(M3);
  return 0;
}

I will take a look at it..