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

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.

public class MyClass<T> {
}

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

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> class will represent a Node to build the Linked List
* Based Set.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Node<T> {

// class fields
private T data;

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

/**
* Create a Node Object with data stored in it and
* next reference will be null.
*
* @param data
*/
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;
}
}

Set.java

/**
* The <code>Set</code> class to implement Generic Linked List Based Set
* Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Set<T> {

// Hold the head of linked list
private Node<T> head;

// count the elements
private int count;

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

///////////////////////////////////////////////////////////////////////
// Data Structure basic Functions //
///////////////////////////////////////////////////////////////////////

/**
* Add a new element to this Set if it is not already there in the set.
*
* @param data new element
* @return true if added, false otherwise
*/
public boolean add(T data) {

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

// case 1: empty set
if(this.isEmpty()) {
head = node;
count++;
return true;
}

// Case 2: Check if already exist
if(find(data)) {
return false;
}

// otherwise move to end of the set and store it
Node<T> current = head;

// Reach to the last node
while(current.getNext() != null) {
current = current.getNext();
}

// end of set reached, insert here
current.setNext(node);
count++;
return true;
}

/**
* Function to remove an element from the set if it exists.
*
* @param data to be removed
* @return indicate successful removal or failure
*/
public boolean remove(T data) {

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

// Case 2: exist at the head of set
if(head.getData().equals(data)) {
head = head.getNext();
count--;
return true;
}

Node<T> current = head, pre = null;

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

if(current.getData().equals(data)) {
pre.setNext(current.getNext());
count--;
return true;
}

pre = current;
current = current.getNext();
}

// if we reach here, means element does not exist
return false;
}

/**
* Function to check if an element exist within the Set.
*
* @param data to search
* @return indicate exists or no
*/
public boolean find(T data) {

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

Node<T> current = head;

while(current != null) {

if(current.getData().equals(data)) {
return true;
}

current = current.getNext();
}

// reach here, doesn't exist
return false;
}

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

/**
* Check if the set is empty.
*
* @return indicate set is empty
*/
public boolean isEmpty() {
return this.head == null;
}

/**
* Display contents of the Set
*/
public void print() {

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

// print something like
// [one, two, three, four]

Node<T> current = head;

System.out.printf("[%s", current.getData().toString());
current = current.getNext();

while(current != null) {

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

current = current.getNext();
}

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

///////////////////////////////////////////////////////////////////////
// Set Data Structure Special Functions //
///////////////////////////////////////////////////////////////////////

/**
* Function to create a new Set that is union of two existing sets.
*
* @param other set
* @return union of two sets
*/
public Set<T> union(Set<T> other) {

// Create new Set
Set<T> set = new Set<>();

// now we take all the elements form current set and add to the
// new set
Node<T> current = head;
while(current != null) {
set.add(current.getData());
current = current.getNext();
}

// Repeat same setp with the "other" set
current = other.head;
while(current != null) {
set.add(current.getData());
current = current.getNext();
}

return set;
}

/**
* Create a new set that is the Intersection set of the current and
* other set.
*
* @param other set
* @return intersection
*/
public Set<T> intersection(Set<T> other) {

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

// now loop every element from current set, If it exists in the other
// set also, it is a common element, store it
Node<T> current = head;
while(current != null) {

// if found in other set too, add it
if(other.find(current.getData())) {
set.add(current.getData());
}

current = current.getNext();
}

// now return the new set
return set;
}

/**
* Create a new set that is the result of A-B Sets
*
* A [1, 2, 4, 5]
* B [3, 4, 5, 6]
* A - B = [1, 2]
*
* @param other set to subtract
* @return different of two sets
*/
public Set<T> difference(Set<T> other) {

// Create Set
Set<T> set = new Set<>();

// Loop every element of current set and if it does not exist
// within the other set, we add it to new set
Node<T> current = head;

while(current != null) {

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

current = current.getNext(); // important

}

// difference of A-B
return set;
}

/**
* Create the Complement set, how it works
*
* U = {1, 2, 3, 4, 5, 6}
* A = {3, 4, 6}
*
* A` = {1, 2, 5}
*
* @param other set whose complement we are creating
* @return complement of other set
*/
public Set<T> complement(Set<T> other) {

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

// Loop every element of Universal Set
// if it is not in other, it is added to new set
Node<T> current = head;

while(current != null) {

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

current = current.getNext();
}

// return the complement set
return set;
}

/**
* Return true, if both the sets have no common element.
*
* A = {1, 3, 5}
* B = {2, 4, 6}
*
* disjoint? True
*
* @param other set
* @return indicate whether two sets are disjoint.
*/
public boolean isDisjoint(Set<T> other) {

// we iterate current set
Node<T> current = head;

while(current != null) {

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

current = current.getNext();
}

// reach here - it meas they are disjoint
return true;
}

/**
* Check if all the elements of current set exists within the elements
* of the other set. Current set is the proper subset of other.
*
* @param other set
* @return check if current set is proper subset
*/
public boolean isProperSubset(Set<T> other) {

Node<T> current = head;

while(current != null) {

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

current = current.getNext();
}

// current set is proper subset of other set
return true;
}
}

GenericLinkedListSetTest.java

/**
* The <code>GenericLinkedListSetTest</code> Class is a client code to test the
* functionality of the Generic Linked List Based Set Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class GenericLinkedListSetTest {

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

// Creaet Sets
Set<String> U = new Set<>();
Set<String> A = new Set<>();
Set<String> B = new Set<>();

// add some elements
U.add("John");
U.add("Marry");
U.add("Jacob");
U.add("Peter");
U.add("Smith");
U.add("Sarah");

// Set A
A.add("John");
A.add("David");
A.add("Tina");

// Set B
B.add("Peter");
B.add("John");
B.add("Sarah");

// print sets
U.print();
A.print();
B.print();

// Union of sets
Set<String> set = A.union(B);
System.out.println("Union of A and B");
set.print();

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

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

// Compliment of B
set = U.complement(B);
System.out.println("Complement of B");
set.print();

// Disjoint sets
System.out.println("Is Set A & B are disjoint? " + A.isDisjoint(B));
System.out.println("Is Set U & B are disjoint? " + U.isDisjoint(B));
System.out.println("Is Set U & A are disjoint? " + U.isDisjoint(A));

// Proper Subset
System.out.println("is Set A proper Subset of U? " + A.isProperSubset(U));
System.out.println("is Set B proper Subset of U? " + B.isProperSubset(U));
System.out.println("is Set U proper Subset of U? " + U.isProperSubset(U));
}

}