Java Sorted Generic 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 – Java Sorted Generic Linked List Based Set Data Structure

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.

Generic Programming

Java included support for writing generic classes in J2SE 5.0 or JDK1.5 version. The generics framework allows us to define a class in terms of a set of parameters that can be used as the type of declared variables, parameters, and return types. Before Java SE 5, generic programming was heavily dependent upon the Java Object class that is the root of the hierarchy in Java Programming Language.

Example:

public class MyClass<T> {
T data; // T can be replaced with any Class Internal or External
}

This is a generic class that can be instantiated with any Class type such as Integer, String, Double, etc.

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.

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

Code

Node.java

/**
* The <code>Node</code> class represents a Generic Node in the Linked List and
* used to implement the Generic Sorted Set.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Node<T extends Comparable<T>> {

// some data field
private T data;

// reference to the next node
private Node<T> next;

/**
* Default Constructor to initialize the Objects of Node class with
* default values.
*/
public Node(T data) {
this.data = data;
this.next = null;
}

public T getData() {
return data;
}

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

public Node<T> getNext() {
return next;
}

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

SortedSet.java

/**
* The <code>SortedSet</code> class that will implement Generic Sorted Set
* Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class SortedSet<T extends Comparable<T>> {

// front of set
private Node<T> head;

// Count of elements
private int count;

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

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

/**
* This function will add new element into the Sorted Set.
*
* // Two conditions
* 1. Order of elements - Ascending
* 2. No Duplication - Uniqueness is a feature of set structure.
*
* @param data to add
* @return true if successful otherwise false.
*/
public boolean add(T data) {

// Add Function
// 2 Things:
// add to the front
// or add to somewhere between the set or at the end of the set

// 3: Uniqueness of the elements
if(find(data)) {
return false; // no duplicate allowed
}

if(this.isEmpty() || data.compareTo(head.getData()) <= 0) {
// add to the front
return this.addFront(data);
} else {

// Create new node
Node<T> node = new Node<>(data);

// navigate the set to locate position of new node
Node<T> current = head;

// move to find the correct location of new node.
while(current.getNext() != null && current.getNext().getData().compareTo(data) <= 0) {
current = current.getNext();
}

// two conditions
// 1. End of set
if(current.getNext() == null) {
current.setNext(node);
} else {
// update next reference of new node
node.setNext(current.getNext());

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

count++;
}

return true;
}

/**
* Function to add new element to the front of the Sorted Set.
*
* in both cases: empty set or value is smaller than head node.
*
* @param data to add to front
* @return true if successful, other false
*/
private boolean addFront(T data) {

// Create new node
Node<T> node = new Node<>(data);

// if empty, assigned to head
if(this.isEmpty()) {
head = node;
} else {

// update next pointer
node.setNext(head);

// update the head
head = node;
}

count++;
return true;
}

/**
* Function to remove an element from the Set if it exists otherwise
* return false.
*
* @param data to remove
* @return true if removed otherwise false.
*/
public boolean remove(T data) {

// if set is empty, we return false
if(this.isEmpty()) {
return false; // do nothing
}

// if it is head node,
if(this.head.getData().equals(data)) {
head = head.getNext();
count--;
return true;
} else {

// remove the node some somewhere between the sorted set.
Node<T> current = head, pre = null;

// traverse the set
while(current != null) {
if(current.getData().equals(data)) {
// update previuse node of current node next pointer
pre.setNext(current.getNext());
count--;
return true;
}

// keep track of previous and next nodes
pre = current;
current = current.getNext();
}
}

return false; // to indicate failure
}

/**
* Function to check an element exist in the Sorted Set.
*
* @param data to check
* @return true if exist otherwise false.
*/
public boolean find(T data) {

// Check if Set is empty
if(this.isEmpty()) {
return false;
}

// Navigate within the Set to find existence of element
Node<T> current = head;

while(current != null) {
if(current.getData().equals(data)) {
return true;
}
current = current.getNext();
}

return false; // does not exist
}

/**
* Get the number of elements in the Set
*
* @return number of elements
*/
public int size() {
return this.count;
}

/**
* Function to check that Sorted Set is Empty.
*
* @return indicate emptiness of set.
*/
public boolean isEmpty() {
return count == 0;
}

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

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

// Iterate the Set
Node<T> current = head;

// print it
System.out.printf("[%s", current.getData());

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

// Loop and traverse the Set
while(current != null) {
System.out.printf(", %s", current.getData());
current = current.getNext(); // don't forget to move to next node
}

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

// ----------------------- Set Speical Functions ------------------------//

/**
* Function to create new Set that is the Union of two sets.
*
* A = {"Jack", "John", "Marry", "Peter"}
* B = {"John", "Smith"}
*
* A U B = {"Jack", "John", "Marry", "Peter", "Smith"}
*
* @param other set for union
* @return union of two sets
*/
public SortedSet<T> union(SortedSet<T> other) {
// create new set
SortedSet<T> set = new SortedSet<>();

// we loop current set, if any common element return false
Node<T> current = head;

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

// Loop for the other set, add all the elements
current = other.head;
while(current != null) {
set.add(current.getData());
current = current.getNext();
}

return set;
}

/**
* Function to create a new Set that is the Intersection of two sets.
*
* A = {"Jack", "John", "Marry", "Peter"}
* B = {"John", "Marry", "Smith"}
*
* Intersection = {"John", "Marry"}
*
*
* @param other set for intersection
* @return Intersection of Two Sets
*/
public SortedSet<T> intersection(SortedSet<T> other) {

// create new set
SortedSet<T> set = new SortedSet<>();

// we loop current set, if any common element return false
Node<T> current = head;

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

return set;

}

/**
* Function to create new Set that is the Difference of Two Sets lets say
* A- B
*
* A = {"Jack", "John", "Marry", "Peter"}
* B = {"John", "Marry", "Smith"}
*
* A - B = {"Jack", "Peter"}
* B - A = {"Smith"}
*
* @param other
* @return
*/
public SortedSet<T> difference(SortedSet<T> other) {

// create new set
SortedSet<T> set = new SortedSet<>();

// we loop current set, if any common element return false
Node<T> current = head;

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

return set;
}

/**
* This function will create new Sorted Set that is the Complement of A
*
* U = {"Jack", "John", "Marry", "Peter", "Smith}
* A = {"John", "Marry", "Smith"}
*
* A` = {"Jack", "Peter"}
*
* // Another features of testing
* n(A) + n(A`) = n(U)
*
* @param other
* @return
*/
public SortedSet<T> complement(SortedSet<T> other) {

// create new set
SortedSet<T> set = new SortedSet<>();

// we loop current set, if any common element return false
Node<T> current = head;

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

return set;
}

/**
* Function to check that if two given sets are Disjoint.
*
* A = {1, 3, 5}
* B = {2, 4, 6}
*
* These two are disjoint because no element is common
*
* @param other set
* @return true if disjoint otherwise false
*/
public boolean isDisjoint(SortedSet<T> other) {

// we loop current set, if any common element return false
Node<T> current = head;

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

return true; // these are disjoint sets.
}

/**
* Function to check that a give set is a proper subset of other set.
*
* A = {1, 2, 3, 4, 5, 6} // A == C
* B = {2, 3, 4} /// Subset but also Proper Subset B != A
* C = {1, 2, 3, 4, 5, 6} // Subset but not Proper Subset C == A
*
* @param other set
* @return true if other set is proper subset
*/
public boolean isProperSubset(SortedSet<T> other) {

//loop other set and check all elements in current set
Node<T> current = other.head;

while(current != null) {

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

current = current.getNext();
}

// reach here - all elements of other set are in current set

// condition of equality
if(size() == other.size()) {
return false; // it is not proper subset because other == current
}

return true; // proper subset.
}

}

SortedGenericLinkedListSetTest.java

/**
* The <code>SortedGenericLinkedListSetTest</code> is a Main class that
* tests the functionality of Sorted Set class implemented using Java
* Generics.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class SortedGenericLinkedListSetTest {

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

SortedSet<String> U = new SortedSet<String>();
SortedSet<String> A = new SortedSet<String>();
SortedSet<String> B = new SortedSet<String>();
SortedSet<String> D = new SortedSet<>();

SortedSet<String> E = new SortedSet<>();

D.add("Tina");
D.add("Mira");

// insert elements
U.add("John");
U.add("Jack");
U.add("Peter");
U.add("Smith");
U.add("Marry");

// Set A
A.add("John");
A.add("Jack");
A.add("Peter");

E.add("John");
E.add("Jack");
E.add("Peter");

// Set B
B.add("John");
B.add("Marry");
B.add("Peter");
B.add("Smith");
B.add("Shawn");

// Print these
System.out.println("Unversal Set:");
U.print();
System.out.println("A Set:");
A.print();
System.out.println("B Set:");
B.print();

// Lets Test Set functions
SortedSet<String> set = A.union(B);
System.out.println("Union of A & B:");
set.print();

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

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

set = U.difference(A);
System.out.println("Difference of U & A:");
set.print();

// complement of sets
set = U.complement(A);
System.out.println("Complement A or A`:");
set.print();
set = U.complement(B);
System.out.println("Complement B or B`:");
set.print();

// Disjoint Sets
System.out.printf("Is A & B disjoint? %s%n", A.isDisjoint(B));
System.out.printf("Is A & D disjoint? %s%n", A.isDisjoint(D));
System.out.printf("Is B & D disjoint? %s%n", B.isDisjoint(D));

// Proper Set
System.out.printf("Is A proper Subset of U? %s%n", U.isProperSubset(A));
System.out.printf("Is B proper Subset of U? %s%n", U.isProperSubset(B));

A.print();
E.print();
System.out.printf("Is A proper Subset of E? %s%n", A.isProperSubset(E));
System.out.printf("Is E proper Subset of A? %s%n", E.isProperSubset(A));
}

}