Java Linked List 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.

Node.java

/**
* The <code>Node</code> will represents a Node within the Linked List Set.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Node {

// Data field
private int data;

// Reference to next node
private Node next;

/**
* Constructor to setup the node with data to hold.
*
* @param data
*/
public Node(int data) {
this.data = data;
this.next = null;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

}

Set.java

/**
* The <code>Set</code> class implements Linked List based Set Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Set {

// add head of the Sent
private Node head;

// count of elements
private int count;

/**
* Initialize Empty Set
*/
public Set() {
this.head = null;
count = 0;
}

/////////////////////////////////////////////////////////////////////
//// Basic Function ////
/////////////////////////////////////////////////////////////////////

// Add Function
public boolean add(int value) {

// create node
Node node = new Node(value);

// Case 1: Empty Set
if(this.isEmpty()) {
head = node;
count++;
return true;
}

// Case 2: Data exist, don't add
// Manage the uniqueness of elements
if(find(value)) {
return false;
}

// insert at the end of set
Node current = head;
while(current.getNext() != null) {
current = current.getNext();
}

current.setNext(node);
count++;
return true;
}

// Remove Function
public boolean remove(int value) {

// If empty, return false - nothing to remove
if(this.isEmpty()) {
return false;
}

// If it is head node
if(head.getData() == value) {
head = head.getNext();
count--;
return true;
}

// somewhere between the set
Node current = head, pre = null;

while(current != null) {

// Find the node
if(current.getData() == value) {

// pre's next will become current's next
pre.setNext(current.getNext());
count--;
return true;
}

// update pointers
pre = current;
current = current.getNext();
}

// end of function, value doesn't exist
return false;
}

// Size function
public int size() {
return count;
}

// Find Function
public boolean find(int value) {

// if empty, return false
if(this.isEmpty()) {
return false;
}

Node current = head;

// move till the end of set
while(current != null) {

// if exist
if(current.getData() == value) {
return true;
}

current = current.getNext();
}

// reach here - value not found
return false;
}

// isEmpty function
public boolean isEmpty() {
return head == null;
}

// Print function
public void print() {

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

// print set like [1, 2, 3, 4]

Node current = head;

System.out.printf("[%d", current.getData());

current = current.getNext();

while(current != null) {
System.out.printf(", %d", current.getData());
current = current.getNext();
}

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

/////////////////////////////////////////////////////////////////////
//// Set Function ////
/////////////////////////////////////////////////////////////////////

// Union of two sets
public Set union(Set B) {

// Create new Set
Set newSet = new Set();

// Iterate and insert all elements of current set
// into new set
Node current = head;
while(current != null) {
newSet.add(current.getData());
current = current.getNext();
}

// Insert all the elements from Set B
// No need to check for duplicate because Add function
// handles it already.
current = B.head;
while(current != null) {
newSet.add(current.getData()); // it will add only if not already there
current = current.getNext();
}

return newSet;

}

// Intersection of two sets
public Set intersection(Set B) {

// Create new set
Set newSet = new Set();

// loop all the elements of first set
// if that element exist in Set B, take it to add into new set
Node current = head;
while(current != null) {

// check it is in B also
if(B.find(current.getData())) {
newSet.add(current.getData());
}

current = current.getNext();
}

return newSet; //

}

// difference of two sets
// Return A-B
// A = {1, 2, 3}
// B = {3, 5, 7}
// A - B = {1, 2}
public Set difference(Set B) {

// Declare new set
Set newSet = new Set();

// loop for the Set a elements
Node current = head;
while(current != null) {
// if element doesn't exist in B, take it and add to new set
if(!B.find(current.getData())) {
newSet.add(current.getData());
}

current = current.getNext();
}

return newSet;
}

// Complement of a Set
// How it works
// Current set is Universal Set: {1, 2, 3, 4, 5, 6}
// Set A = {1, 2, 5}
// Complement A will be: {3, 4, 6}
public Set complement(Set A) {

// create new set
Set newSet = new Set();

// Loop elements from the set A
Node current = head;
while(current != null) {

// element doesn't exist in A, add it to Complement set
if(!A.find(current.getData())) {
newSet.add(current.getData());
}
current = current.getNext();
}

return newSet;
}

// are two sets disjoint?
// Check if current set and Set B are disjoint
// DisJoint are the sets, that have no common element
// A = {1, 3, 5}
// B = {2, 4, 6}
// They disjoint - no common element
public boolean isDisjoint(Set B) {

Node current = head;

while(current != null) {

// if element exist in B, they are not disjoint
if(B.find(current.getData())) {
return false;
}

current = current.getNext();
}

// Reach here, these sets are disjoint.
return true;
}

// If Set B is proper subset of of B
// A proper subset is a set whose all the elements exist within
// other set
public boolean isProperSubset(Set B) {

Node current = B.head;
while(current != null) {
if(!find(current.getData())) {
return false; // indicate not a subset
}
current = current.getNext();
}

// The Set B is proper subset of A.
return true;
}
}

LinkedListSetApp.java

/**
* Test the Linked List Based Set Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class LinkedListSetApp {

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

// Create sets
Set U = new Set();
Set A = new Set();
Set B = new Set();

// U is universal set [1, 2, 3, 4, 5, 6}
U.add(1);
U.add(2);
U.add(3);
U.add(4);
U.add(5);
U.add(6);

// A { 1, 2, 6}
A.add(1);
A.add(2);
A.add(6);

// B { 2, 3, 4, 5, 6}
B.add(2);
B.add(3);
B.add(4);
B.add(5);
B.add(6);

// Lets print them
System.out.println("Set U: ");
U.print();
System.out.println("Set A: ");
A.print();
System.out.println("Set B: ");
B.print();

// Union:
Set r = A.union(B);
System.out.println("Union of A & B");
r.print();

// Intersection
r = A.intersection(B);
System.out.println("Intersection of A & B");
r.print();

// Difference
r = A.difference(B);
System.out.println("Difference of A and B");
r.print();

// Complement of A
r = U.complement(A);
System.out.println("Complement of A");
r.print();

// disjoint
System.out.println("Is A and B are disjoint sets? " + A.isDisjoint(B));

// Proper Subset
System.out.println("A is Proper Subset of U - " + U.isProperSubset(B));
System.out.println("A is Proper Subset of B - " + B.isProperSubset(A));

}

}