Question

Add to the class DoublyLinkedList a method called isSubSet ( DoublyLinkedList <Character> s1, DoublyLinkedList <Character> s2) that receives 2 DoublLinked lists of characters. The method will return true if

s1 is subset of s2. Then don’t forget to test the method in the main method in Test class in Doubly package.

Answer 1

Program Plan:

1. In method isSubset(), check size of set s1 is greater than s2 then return false.
2. If "s1 size is less than s2", then iterate over s1.
3. If s2 doesn't contains the elements of s1, then return false.
4. As a final case return true, since failure cases are handled in step 1, 2 and 3.
5. In Driver class, create 2 list s1 and s2.
6. Invoke isSubset() method with input arguments s1 and s2.
7. Based the returned boolean value from isSubset() method, print the statements showing s1 is subset of s2 or not.
8. Sample output is added at the end.
9. Instead of "DoublyLinkedList" object "LinkedList" object is used due to non-availability of DoublyLinkedList implementation.
10. After copy/pasting program replace "LinkedList" with "DoublyLinkedList" in both the classes.

Program:

/*
* Driver class to test s1 is subset of s2
*/
import java.util.LinkedList;

public class DoublyLinkedListDriver {

   public static void main(String[] args) {

       LinkedList<Character> s1 = new LinkedList<>();// set s1
       LinkedList<Character> s2 = new LinkedList<>();// set s2
       // add elements to set s1
       s1.add('a');
       s1.add('b');
       s1.add('c');
       s1.add('d');
       // uncomment below line to make s1 is not subset of s2
       // s1.add('z');
       // add elements to set s2
       s2.add('a');
       s2.add('b');
       s2.add('c');
       s2.add('d');
       s2.add('e');
       s2.add('f');

       LinkedListSubset subSet = new LinkedListSubset();

       boolean isSubset = subSet.isSubSet(s1, s2);// invoke isSubSet() with s1 & s2

       if (isSubset)
           System.out.println("S1 is subset of S2.");
       else
           System.out.println("S1 is not subset of S2.");
   }
}

/*
* LinkedListSubset class implementing isSubSet() method
*/

import java.util.LinkedList;

public class LinkedListSubset {

   public boolean isSubSet(LinkedList<Character> s1, LinkedList<Character> s2) {
       // if elements of s1 is greater than s2, s1 is not subset
       if (s1.size() > s2.size()) {
           return false;
       } else {
           // iterate over s1
           for (int i = 0; i < s1.size(); i++)
               // check s2 contains elements of s1
               if (!s2.contains(s1.get(i)))
                   return false;
       }
       return true;
   }

}

Sample Output:

S1 is subset of S2.