Java Sorted 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. The Sorted Linked-List Based Set maintains the Ascending order of its unique elements. This is an added feature of an ordinary Set. 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.

Video Tutorial

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.

Methods

Union (All unique elements in both Sets):

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

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> class will represent a Node in the Linked List. It
* contains a Data element and a reference to the Next Node.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Node {

// Data Field
private int data;

// Reference to next Node
private Node next;

/**
* Default Constructor to initialize the Objects of Node class with
* default values.
*
* @param data to store
*/
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;
}
}

SortedSet.java

/**
* The <code>SortedSet</code> class will consist of a chain of Node class
* objects and construct a Sorted Set based on the Linked List.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class SortedSet {

// Head of the Set
private Node head;

// count elements
private int count;

/**
* Default Constructor to initialize the Objects of SortedSet class with
* default values.
*/
public SortedSet() {
this.head = null;
this.count = 0;
}

// ------------- Data Structure Basic Functions ---------------------//

/**
* Function to add new element to the Sorted Set.
*
* conditions:
*
* 1. Uniqueness - no duplication allowed
* 2. Maintain the Ascending order of the Sorted Set.
*
* @param data to add
* @return return true if added otherwise false.
*/
public boolean add(int data) {

// check two conditions
// if empty, or if data is smaller than the head node data
// we insert at the front of the Sorted Set.
if(this.isEmpty() || data < head.getData()) {
return this.addFront(data);
}

// reach here, insert the new data element at a correct location
// Create new node
Node node = new Node(data);

// Check if data already exist
if(!find(data)) {

// Find the location
Node current = head;

// traverse the Sorted set to find the location.
while(current.getNext() != null && current.getNext().getData() <= data) {
current = current.getNext();
}

// There two cases
// 1. We reached end of the Sorted Set
// 2. We have to insert somewhere between two nodes.

if(current.getNext() == null) { // Case 1 - End of List
current.setNext(node);
} else { // Case 2. Somewhere between the nodes

// update next reference of new node to current's next reference
node.setNext(current.getNext());

// update reference of current node to new node
current.setNext(node);
}

// update count
count++;
return true;
}

// already exist, return false
return false;

}

/**
* Linear search, find the element, if found remove it.
* Return true, or false based on success or failure.
*
* @param data to be removed
* @return indicate success or failure
*/
public boolean remove(int data) {

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

// We have non-empty Set
// Case 1. Check the element stored at head node
if(head.getData() == data) {
head = head.getNext();
count--;
return true;
}

// Remove somewhere between the Sorted Set nodes
Node current = head, pre = null;

// iterate till the end of Sorted Set
while(current != null) {

// Check if current node data match
if(current.getData() == data) {
pre.setNext(current.getNext());
count--;
return true;
}

// update the navigation references
pre = current;
current = current.getNext();
}

// return true - means data doesn't exist
return false;
}

/**
* This function will add new data element at the beginning of the Set.
*
* @param data to add
* @return true if added, false otherwise
*/
private boolean addFront(int data) {

// First Check the existence
if(!find(data)) { // avoid duplicate element

// Create node
Node node = new Node(data);

// We check if empty
if(this.isEmpty()) {
head = node;
} else {

node.setNext(head);
head = node;
}

count++;
return true;
}

return false; // means it already exist in the Sorted Set
}

/**
* Retrieve number of elements in the Set.
*
* n(A) => return number of elements
*
* @return number of elements
*/
public int size() {
return count;
}

/**
* Function to check the existence of an element within the Set.
*
* @param value to check
* @return indicate exist or not
*/
public boolean find(int value) {

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

Node current = head;

// loop till we find the element or reach end of the Set
while(current != null) {

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

// move to next node
current = current.getNext(); // important step
}

return false; // not found
}

/**
* Check if the Set is empty or not.
*
* @return true if not empty, otherwise false.
*/
public boolean isEmpty() {
return head == null;
}

/**
* Function to Print the Sorted Set.
*/
public void print() {

// If it is empty, output a message
if(this.isEmpty()) {
System.out.println("This Sorted Set is Empty");
return;
}

// Print like
// [1, 2, 3, 4, 5]

Node current = head;

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

//move to next node
current = current.getNext();

// Loop till the end Sorted Set
while(current != null) {
System.out.printf(", %d", current.getData());

// move to next node
current = current.getNext();
}

// close square bracket
System.out.println("]");
}

// ------------- Set Specific Functions ----------------------------//

/**
* Union of Two Sets A and B
*
* A = {1, 2, 3, 5, 7}
* B = {2, 4, 6}
*
* A U B = {1, 2, 3, 4, 5, 6, 7} // Because this is a Sorted Set
*
* @param other set
* @return Union of Two Sets
*/
public SortedSet union(SortedSet other) {

// Create new set
SortedSet set = new SortedSet();

// Loop every element from current set and add to new set
Node current = head;

while(current != null) {
set.add(current.getData());
current = current.getNext();
}

// Iterate Other set, and add all the elements to new set
current = other.head;

while(current != null) {
set.add(current.getData());
current = current.getNext();
}

return set; // Union of two Sets
}

/**
* Create the Intersection of two given Sets.
*
* Example:
* A = {1, 2, 3, 5}
* B = {2, 4, 5, 7}
*
* Intersection = {2, 5}
*
* @param other set
* @return intersection of two sets.
*/
public SortedSet intersection(SortedSet other) {

// Create new set
SortedSet set = new SortedSet();

// Start from the beginning of current set
Node current = head;

// loop till end of Current set
while(current != null) {

if(other.find(current.getData())) {
set.add(current.getData());
}

// move to next node
current = current.getNext();
}

return set; // Intersection of 2 Sets
}

/**
* Function to create the Difference of Two given Sets.
*
* A = {1, 2, 3, 4, 5}
* B = {2, 4}
* A - B = {1, 3, 5}
*
* @param other set
* @return difference of two sets
*/
public SortedSet difference(SortedSet other) {

// Create new set
SortedSet set = new SortedSet();

// Start from the beginning of current set
Node current = head;

// loop till end of Current set
while(current != null) {

if(!other.find(current.getData())) {
set.add(current.getData());
}

// move to next node
current = current.getNext();
}

return set; // different A - B
}

/**
* Compute the complement set of A => A`
*
* U = {1, 2, 3, 4, 5, 6, 7}
* A = {2, 3, 6}
* A` = {1, 4, 5, 7}
*
* n(A) + n(A`) = n(U)
*
* @param other set
* @return complement of A => A`
*/
public SortedSet complement(SortedSet other) {

// Create new set
SortedSet set = new SortedSet();

// Start first node of current set that Universal
Node current = head;

// loop till end of Universal Set
while(current != null) {

// check if element in other set
if(!other.find(current.getData())) {
set.add(current.getData());
}

current = current.getNext();
}

return set; // its complement a Set other.
}

/**
* This function will check if the two given sets are disjoint.
*
* Disjoint Property: Two sets are disjoint if there is not common element
* exist within those two sets.
*
* Example
* A = {1, 3, 5}
* B = {2, 4, 6}
* These are disjoint Sets
*
* @param other set
* @return true if both are disjoint otherwise false
*/
public boolean isDisjoint(SortedSet other) {

// loop current set
Node current = head;

while(current != null) {

if(other.find(current.getData())) {
return false;
}
current = current.getNext();
}

// they are disjoint sets
return true;
}

/**
* Function to check the two sets, if one set is proper subset of other set.
*
* Example:
*
* A = {1, 2, 3, 4, 5}
* B = {2, 4}
*
* B is a proper subset of A
*
* @param other
* @return
*/
public boolean isProperSubset(SortedSet other) {

// start with first node
Node current = other.head;

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

// check if element exist, if not return false
if(!find(current.getData())) {
return false;
}

current = current.getNext();
}

return true;

}
}

SortedLinkedListSetTest.java

/**
* The <code>SortedLinkedListSetTest</code> is a Main class that tests the
* functionality of of the Sorted Linked List Based Set Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class SortedLinkedListSetTest {

/**
* Main Method - Entry Point of the Program.
*
* @param args the command line arguments
*/
public static void main(String[] args) {

// Create couple of Sets

SortedSet U = new SortedSet();
SortedSet A = new SortedSet();
SortedSet B = new SortedSet();
SortedSet C = new SortedSet();

U.add(1);
U.add(2);
U.add(3);
U.add(4);
U.add(5);
U.add(6);
U.add(7);

A.add(1);
A.add(3);
A.add(4);
A.add(6);

B.add(2);
B.add(3);
B.add(5);
B.add(6);

C.add(9);
C.add(11);

// Print to check the State of sets
U.print();
A.print();
B.print();

// Test Union
SortedSet set = A.union(B);
System.out.println("Union of A & B:");
set.print();

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

// Test Difference
set = A.difference(B);
System.out.println("Difference of A & B: A-B");
set.print();

// Test Complement
set = U.difference(A);
System.out.println("Complement of A => A`");
set.print();

set = U.difference(B);
System.out.println("Complement of B => B`");
set.print();

// Test Disjoint
System.out.println("Is Set A & B disjoint? " + A.isDisjoint(B));
System.out.println("Is Set A & C disjoint? " + A.isDisjoint(C));
System.out.println("Is Set B & C disjoint? " + B.isDisjoint(C));

// Test Proper Subset
System.out.println("Is Set A Proper Subset of U: " + U.isProperSubset(A));
System.out.println("Is Set B Proper Subset of U: " + U.isProperSubset(B));
System.out.println("Is Set A Proper Subset of B: " + B.isProperSubset(A));
System.out.println("Is Set B Proper Subset of A: " + A.isProperSubset(B));
}

}