Java Array Based Set Tutorial

Introduction

Set is a linear data structure. A Set is a special data structure that maintains a collection of unique elements. All these elements are of the same data type. Sequential and uniqueness are special features of Set data structure. The search is performed sequentially within the Set Data Structure because there is no order maintained while storing Set elements. The Set data structure can be implemented using an Array with fixed or dynamic memory. The Set Data structure can also be implemented using a Linked List in that case the memory will be dynamically allocated according to the needs and no memory will waste as it can be while implementing it using an Array. The set data structure requires some special functions besides Add, Remove, Find, Size, Print, etc. These special functions are based on Set Operations for Union, Intersection, Difference, Disjoint, Proper subset, and compliment. These operations are based on Set Mathematical Theory.

Underlying Data Structure

Array-based Set implementation can be done by using fixed-size arrays or dynamically growing arrays. The dynamically growing array can be implemented by increasing the size of the array and preserving the previous elements within the set so that no data loss happens while resizing the array. Whether we use a fixed-size or growing array approach still there is a chance of unutilized memory. Linked List-based implementation requires O(N) memory where N is the number of elements stored within the Linked-List Based Set. No memory is wasted in this case because we only need as many nodes as we have the number of elements to store within the Set.

Operations

Union (All unique elements in both Sets):

Set A = {1, 3, 5, 6}
Set B = {2, 4, 6, 7}
Union S = {1, 3, 5, 6, 2, 4, 7}

Intersection (Common elements):

Set A = {1, 2, 5, 9}
Set B = {2, 3, 5, 8}
Intersection S = {2, 5}

Difference of Sets

Set A = {1, 2, 5, 9}
Set B = {2, 3, 5, 8}
A – B = {1, 9}

Compliment of a Set

U = {1, 2, 3, 4, 5, 6}
A = {2, 3, 6}
Complement of A` = {1, 4, 5}

Disjoint Set

A = {1, 3, 5}
B = {2, 4, 6}
A and B are Disjoint Sets

Proper Subset

A = {1, 2, 3, 4, 5, 6}
B = {2, 4, 6}
B is the Proper Subset of A

Time Complexity of Set Data Structure.

Insertion: Array-based implementation O(1) best, average and worst case scenarios. Linked List-based set, O(1) when the set is empty, O(N) when the insertion is carried out at the end of the Set. We can achieve O(1) runtime for Insertion at the end if we add another instance field to keep track of the tail node. In case of Insertion into a Sorted Set, the time complexity will be O(N^2) in average and Worst Cases.
Deletion: Array-based Implementation O(1) if there is only one element in the Set or removed from the end of the array. O(N) for average and worst-case scenarios because we have to shift elements to fill the hole created by removing the element from the underlying array. In the case of Linked List-based Implementation, the runtime is O(1) removed from the front of the set. In average and worst-case scenarios runtime will be O(N). In the case of using the additional field “tail” in the linked list, we can achieve O(1) for the removal of an element from the end of the set.
Search is sequential for unsorted sets no matter whether we use Array or Linked List. So runtime O(1) if it is the first element, otherwise O(N) in case of average and worst case scenarios. In Sorted Array-based Set Implementation we can utilize Binary Search, which is way faster than O(N) as it is O(LogN).
Size: O(1) In all cases.
Print: O(1) if there is one element, O(N) otherwise in best and worst cases. N is the number of elements within the Set.

ArraySet.java

/**
* The <code>ArraySet</code> class will implement the Array Based Set
* Data Structure including Set Operations.
*
* @author CodingHelpLine
* Website: https://codinghelpline.org
*/
public class ArraySet {

// Now Capacity for the array
private final int CAPACITY = 100;

// Array to hold values
private int data [];

// Index
private int index;

/**
* Default constructor to setup array memory.
*/
public ArraySet() {
this.data = new int[CAPACITY];
this.index = 0;
}

////////////////////////////////////////////////////////////////////////
// SET THEORY FUNCTIONS //
////////////////////////////////////////////////////////////////////////

/**
* This function create a new set that is the union of two sets.
*
* @param other set
* @return union
*/
public ArraySet union(ArraySet other) {

ArraySet union = new ArraySet();

// insert all the elements from current set
// insert all the elements from other set
// The set maintains uniqueness due to this condition in Add function
for(int i=0; i<index; i++) {
union.add(data[i]);
}

for(int i=0; i<other.index; i++) {
union.add(other.data[i]);
}

return union;
}

/**
* Create a new Set that has elements common in both sets.
*
* @param other set
* @return intersection of two sets
*/
public ArraySet intersect(ArraySet other) {
ArraySet intersection = new ArraySet();

// insert only common elements from both sets
// The set maintains uniqueness due to this condition in Add function
for(int i=0; i<index; i++) {

if(other.find(data[i])) {
intersection.add(data[i]);
}
}

return intersection;
}

/**
* Function to create new Set that is the different of elements
* from A to B
*
* All the elements from A that are not in B
*
* @param other
* @return
*/
public ArraySet difference(ArraySet other) {
ArraySet difference = new ArraySet();

// insert elements from A that are not in B
// The set maintains uniqueness due to this condition in Add function
for(int i=0; i<index; i++) {
// D = A - B
if(!other.find(data[i])) {
difference.add(data[i]);
}
}

return difference;
}

/**
* Function to create a new Set that is the Complement of A
*
* U = {1, 2, 3, 4, 5, 6}
* other = {2, 3, 4, 5}
*
* Complement: {1, 6}
*
* @param other is the set whose complement will be created
* @return the complement
*/
public ArraySet complement(ArraySet other) {
ArraySet complementSet = new ArraySet();

// insert elements from U that are not in A
// The set maintains uniqueness due to this condition in Add function
for(int i=0; i<index; i++) {
// A` = {}
if(!other.find(data[i])) {
complementSet.add(data[i]);
}
}

return complementSet;
}

/**
* check whether two sets are disjoint.
*
* A disjoint set are two sets that have no common element
*
* A = {1, 3, 5}
* B = {2, 4, 6}
*
* Disjoint sets
*
* @param other set
* @return indicate disjoint or not
*/
public boolean isDisjoint(ArraySet other) {

for(int i = 0; i < index; i++) {
if(other.find(data[i])) {
return false;
}
}

return true;

}

/**
* Check one set is the subset of other set.
*
* @param other set
* @return indicate if it is proper subset
*/
public boolean isProperSubset(ArraySet other) {

for(int i=0; i<other.index; i++) {
if(!find(other.data[i])) {
return false;
}
}

return true; // means other is subset of current set.
}

/**
* function to add an element to the set.
*
* // condition:
* 1. capacity
* 2. uniqueness
*
* @param value
* @return
*/
public boolean add(int value) {

// case - set is full
if(this.isFull()) {
// grow the array
this.grow();
}

// check if the value already exist within the Set
// to maintain uniqueness of its elements
if(find(value)) {
// System.out.println("The Value already exist");
return false;
}
// assign or store the value
this.data[index++] = value;
return true;
}

/**
* remove an element from the Set.
*
* @param value to remove
* @return true if removed, false otherwise
*/
public boolean remove(int value) {

// find index
int index = -1;

for(int i=0; i<index; i++) {
if(data[i] == value) {
index = i;
break;
}
}

// element doesn't exist
if(index == -1) {
return false;
}

// shift the elements to fill the gap
for(int i=index; i < data.length-1; i++) {
data[i] = data[i+1]; // overwrite previous element
}

// update index
index--;

return true;
}

/**
* Get the number of elements.
*
* @return number of elements.
*/
public int size() {
return index;
}

/**
* Print the Set
*/
public void print() {

if(this.isEmpty()) {
System.out.println("The Set is empty");
return;
}

System.out.printf("[%d", data[0]);

for(int i=1; i<index; i++) {
System.out.printf(", %d", data[i]);
}

System.out.println("]");
}

/**
* Function to check whether a value exists
*
* @param value to check
* @return indicate exist or not
*/
public boolean find(int value) {

for(int i=0; i<index; i++) {
if(data[i] == value) {
return true;
}
}

return false;
}

/**
* Check if the set is full.
*
* @return indicate set is full
*/
public boolean isFull() {
return index == data.length;
}

/**
* if set is empty.
*
* @return indicate set is empty
*/
public boolean isEmpty() {
return index == 0;
}

/**
* grow the array size and keep the existing elements
*/
private void grow() {
// new array
int copy [] = new int[data.length];

// copy the elements
for(int i=0; i<index; i++) {
copy[i] = data[i];
}

// reassign data
data = new int[index * 2]; // double the size

// now copy back
for(int i=0; i<index; i++) {
data[i] = copy[i];
}
}

}

ArrayBasedSetTest.java

/**
* The <code>ArrayBasedSetTest</code> class will test the functionality
* of the ArraySet Class.
*
* @author CodingHelpLine
* Website: https://codinghelpline.org
*/
public class ArrayBasedSetTest {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {

ArraySet A = new ArraySet();
ArraySet B = new ArraySet();
ArraySet C = new ArraySet();

// [1, 3, 5, 7]
// [2, 4, 6, 8]
// [1, 2, 3, 5, 7, 8]

// add elements
A.add(1);
A.add(3);
A.add(5);
A.add(7);

B.add(2);
B.add(4);
B.add(6);
B.add(8);

C.add(1);
C.add(2);
C.add(3);
C.add(5);
C.add(7);
C.add(8);

// Lets check Set functions
ArraySet set = A.union(B);
A.print();
B.print();
set.print();

// intersection
set = A.intersect(C);
set.print();

// difference
set = B.difference(C);
set.print();

// complement
set = C.complement(A);
set.print();

// Disjoing
System.out.println("Is A & B are disjoint? " + A.isDisjoint(B));
System.out.println("Is A & C are disjoint? " + A.isDisjoint(C));
System.out.println("Is B & C are disjoint? " + B.isDisjoint(C));

// Proper subset
System.out.println("Is A proper subset of C? " + C.isProperSubset(A));
System.out.println("Is B proper subset of C? " + C.isProperSubset(B));
}
}