
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
A   set  is a collection of elements, without duplicates and without order.



Task

Show each of these set operations:

 Set creation
 Test m ∈ S -- "m is an element in set S"
 A ∪ B -- union; a set of all elements either in set A or in set B.
 A ∩ B -- intersection; a set of all elements in both set A and set B.
 A ∖ B -- difference; a set of all elements in set A, except those in set B.
 A ⊆ B -- subset; true if every element in set A is also in set B.
 A = B -- equality; true if every element of set A is in set B and vice versa.


As an option, show some other set operations.

(If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.)

As another option, show how to modify a mutable set.



One might implement a set using an associative array (with set elements as array keys and some dummy value as the values).

One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators).

The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


import java.util.Arrays;
import java.util.Collections;
import java.util.Set;
import java.util.TreeSet;
 
public class Sets {
    public static void main(String[] args){
        Set<Integer> a = new TreeSet<>();
        //TreeSet sorts on natural ordering (or an optional comparator)
        //other options: HashSet (hashcode)
        //               LinkedHashSet (insertion order)
        //               EnumSet (optimized for enum values)
        //others at: http://download.oracle.com/javase/7/docs/api/java/util/Set.html
        Set<Integer> b = new TreeSet<>();
        Set<Integer> c = new TreeSet<>();
        Set<Integer> d = new TreeSet<>();
 
        a.addAll(Arrays.asList(1, 2, 3, 4, 5));
        b.addAll(Arrays.asList(2, 3, 4, 5, 6, 8));
        c.addAll(Arrays.asList(2, 3, 4));
        d.addAll(Arrays.asList(2, 3, 4));
        System.out.println("a: " + a);
        System.out.println("b: " + b);
        System.out.println("c: " + c);
        System.out.println("d: " + d);
 
        System.out.println("2 in a: " + a.contains(2));
        System.out.println("6 in a: " + a.contains(6));
 
        Set<Integer> ab = new TreeSet<>();
        ab.addAll(a);
        ab.addAll(b);
        System.out.println("a union b: " + ab);
 
        Set<Integer> a_b = new TreeSet<>();
        a_b.addAll(a);
        a_b.removeAll(b);
        System.out.println("a - b: " + a_b);
 
        System.out.println("c subset of a: " + a.containsAll(c));
        //use a.conatins() for single elements
 
        System.out.println("c = d: " + c.equals(d));
        System.out.println("d = c: " + d.equals(c));
 
        Set<Integer> aib = new TreeSet<>();
        aib.addAll(a);
        aib.retainAll(b);
        System.out.println("a intersect b: " + aib);
 
        System.out.println("add 7 to a: " + a.add(7));
        System.out.println("add 2 to a again: " + a.add(2));
 
        //other noteworthy things related to sets:
        Set<Integer> empty = Collections.EMPTY_SET; //immutable empty set
        //empty.add(2);  would fail
        empty.isEmpty(); //test if a set is empty
        empty.size();
        Collections.disjoint(a, b); //returns true if the sets have no common elems (based on their .equals() methods)
        Collections.unmodifiableSet(a); //returns an immutable copy of a
    }
}