Core Java Coding Questions: Creating a custom hierarchical List in Java -- Part 1

Core Java Coding Questions and Answers for beginner to intermediate level

Q1

Q2

Q3

Q4

Q5

Q6

Q. Can you write a custom list class that supports the following features?

1. Allows you to maintain a parent/child hierarchy of sub lists.
2. Allows you to create sublists from a given list and a predicate (i.e a condition)
3. If you add an item or element to a list, the addition must be propagated to its parent and child lists.
4. If you remove an element from a list, the removal must be propagated to its parent and child lists.

For example:

If you have a list of numbers say 1,2,3,4,5,6,7,8,9,10 in a list

1. the customList.subList(oddNumberPredicate) should create a subList of 1,3,5,7,9 and the parent being the numbers 1 to 10.
2. the customList.subList(factorOf5) should create a subList of 5,10 and the parent being the numbers 1 to 10.
3. the oddNumberSubList.subList(factorOf3) should create a subList of 3,9 and the parent being 1,3,5,7,9 

A. To make it easier, I will build it up step by step. This post concentrates on getting the subList(...) function working and expand on this to build the add(...) and remove(...) functions.

Step 1: Define the interface for the predicates. Refer to filtering a list with a predicate to get some background.

package test;

public interface Predicate<E> {
 boolean evaluate(E object);
}

Step 2: Define different implementations of the predicate

OddNumberPredicate:

package test;

public class OddNumberPredicate<E> implements Predicate<Integer> {

 @Override
 public boolean evaluate(Integer number) {
  return (number != null && number % 2 > 0) ? true : false;
 }

}

FactorOf5Predicate:

package test;

public class FactorOf5Predicate<E> implements Predicate<Integer> {

 @Override
 public boolean evaluate(Integer number) {
  return (number != null && number % 5 == 0) ? true : false;
 }
}

FactorOf3Predicate:

package test;

public class FactorOf3Predicate<E> implements Predicate<Integer> {

 @Override
 public boolean evaluate(Integer number) {
  return (number != null && number % 3 == 0) ? true : false;
 }
}

Step 3: Create the CustomList class with proper generics (i.e. E to denote Elements). The class implements the interface List from the Java Collection, hence the CustomList class needs to implement the relevant methods. If you don't want to support a particular method, throw an exception named UnsupportedOperationException. The following code only shows the class to get subList method going with the relevant constructors. Refer to the comments in the code for further explanation. Also pay attention to things like

1. Declaring the variables as private so that cannot be accessed from outside the class.
2. Declaring the constructors as protected to be used within the same package or sub classes of other packages
3. Declaring the Generics so that the CustomList can support different data types like Number, String, User, Person, Employee, etc.
4. Throwing UnsupportedOperationException from the addAll(int index, Collection c), addAll(Collection c), etc. We will these methods later on as we see fit
5. In an entry to a public method that takes parameters, perform pre condition check and fail fast by throwing exceptions early.
6. toString(  method is added to print the items when the CustomList class is referenced in a System.out.println(...);

package test;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class CustomList<E> implements List<E> {

 private CustomList<E> parent = null; //parent
 protected List<E> list = null; //initial list
 private List<CustomList<E>> sublists = new ArrayList<CustomList<E>>(); //children
 private Predicate<E> predicate; //used to create sublists based on the
               //predicate

 /**
  * DEFINE THE CONSTRUCTORS
  */

 public CustomList(List<E> sourceList) {
  this.list = sourceList;
 }

 // default constructor with an empty list
 public CustomList() {
  this(new ArrayList<E>()); // invokes the above constructor by supplying
                // an empty list
 }

 /**
  * access modifier is protected to only invoke from within the package and
  * subclasses from the other packages. This protected constructor creates
  * sub lists from the source or parent lists based on the supplied predicate
  * 
  * @param sourceList
  * @param predicate
  */
 protected CustomList(List<E> sourceList, Predicate<E> predicate) {
  if (predicate == null) {
   throw new IllegalArgumentException("Expected to receive a non-null predicate on which to base the sublist!");
  }

  this.predicate = predicate;

  // Each CustomList decorates a concrete List...
  this.list = new ArrayList<E>(sourceList.size());

  // Evaluate each item in the source to create the sublist
  // not using for each loop as we have not defined the iterator method
  // currently iterator() is throwing UnSupportedOperationException
  for (int i = 0; i < sourceList.size(); i++) {
   E item = sourceList.get(i);
   if (predicate.evaluate(item)) {
    this.list.add(item);
   }
  }

 }

 /**
  * access modifier is protected to only invoke from within the package and
  * subclasses from the other packages
  * 
  * @param sourceList
  * @param predicate
  */
 protected CustomList(CustomList<E> parent, Predicate<E> predicate) {
  this((List<E>) parent, predicate); // creates the sublist
  this.parent = parent;
  // Add ourselves (i.e. the new sublist created by this predicate)
  // to the parent subList
  parent.sublists.add(this);
 }

 /**
  * CREATING SUB LISTS
  */

 public CustomList<E> subList(Predicate<E> subListPredicate) {
  return new CustomList<E>(this, subListPredicate);
 }

 /**
  * Methods that need to be implemented for the List<E> interface to satisfy
  * the List interface contract
  */

 @Override
 public int size() {
  return this.list.size();
 }

 @Override
 public boolean isEmpty() {
  return this.list.isEmpty();
 }

 @Override
 public boolean contains(Object o) {
  return this.list.contains(o);
 }

 @Override
 public Iterator<E> iterator() {
  throw new UnsupportedOperationException();
 }

 @Override
 public Object[] toArray() {
  return this.list.toArray();
 }

 @Override
 public <T> T[] toArray(T[] a) {
  return this.list.toArray(a);
 }

 @Override
 public boolean add(E e) {
  throw new UnsupportedOperationException();
 }

 @SuppressWarnings("unchecked")
 @Override
 public boolean remove(Object o) {
  throw new UnsupportedOperationException();
 }

 @Override
 public boolean containsAll(Collection<?> c) {
  return this.list.containsAll(c);
 }

 @Override
 public boolean addAll(Collection<? extends E> c) {
  throw new UnsupportedOperationException();
 }

 @Override
 public boolean addAll(int index, Collection<? extends E> c) {
  throw new UnsupportedOperationException();
 }

 @Override
 public boolean removeAll(Collection<?> c) {
  throw new UnsupportedOperationException();
 }

 @Override
 public boolean retainAll(Collection<?> c) {
  throw new UnsupportedOperationException();
 }

 @Override
 public void clear() {
  // TODO Auto-generated method stub

 }

 @Override
 public E get(int index) {
  return this.list.get(index);
 }

 @Override
 public E set(int index, E element) {
  throw new UnsupportedOperationException();
 }

 @Override
 public void add(int index, E element) {
  throw new UnsupportedOperationException();
 }

 @Override
 public E remove(int index) {
  throw new UnsupportedOperationException();
 }

 @Override
 public int indexOf(Object o) {
  return this.list.indexOf(o);
 }

 @Override
 public int lastIndexOf(Object o) {
  return this.list.lastIndexOf(o);
 }

 @Override
 public ListIterator<E> listIterator() {
  throw new UnsupportedOperationException();
 }

 @Override
 public ListIterator<E> listIterator(int index) {
  throw new UnsupportedOperationException();
 }

 @Override
 public List<E> subList(int fromIndex, int toIndex) {
  throw new UnsupportedOperationException();
 }

 /**
  * very basic toString() method
  */
 @Override
 public String toString() {
  return list.toString();
 }

}

Step 4: Finally, the test class with the main method to demonstrate how to use the CustomList and invoke subList method to create derived sub list classes.

package test;

import java.util.Arrays;
import java.util.List;

public class CustomListTest {
 
 
 public static void main(String[] args) {
  List<Integer> initialList = Arrays.asList(1,2,3,4,5,6,7,8,9,10);
 
  CustomList<Integer> customList = new CustomList<Integer>(initialList);
  System.out.println("customList: " + customList);
  
  Predicate<Integer> oddNumberPredicate = new OddNumberPredicate<Integer>();
  CustomList<Integer> oddNumbersSubList = customList.subList(oddNumberPredicate);
  System.out.println("oddNumbersSubList: " + oddNumbersSubList);
  
  Predicate<Integer> factorOf5Predicate = new FactorOf5Predicate<Integer>();
  CustomList<Integer> factorOf5SubList = customList.subList(factorOf5Predicate);
  System.out.println("factorOf5SubList: " + factorOf5SubList);
  
  
  Predicate<Integer> factorOf3Predicate = new FactorOf3Predicate<Integer>();
  CustomList<Integer> factorOf3SubList = oddNumbersSubList.subList(factorOf3Predicate);
  System.out.println("factorOf3SubList : " + factorOf3SubList);
  
  
  System.out.println("Demonstrate printing customList again");
  System.out.println("customList : " + customList);
  
 }

}

The output of the above test run

customList: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

oddNumbersSubList: [1, 3, 5, 7, 9]

factorOf5SubList: [5, 10]

factorOf3SubList : [3, 9]

Demonstrate printing customList again

customList : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Stay tuned, in the next part I will expand the toString( ) method to print the tree hierarchy iteratively, which can be a bit tricky for some to understand. Practice these Java coding questions by coding.




In part 2, flattening the hierarchy iteratively in the toString( ) method to output the tree details.