Java: Object Oriented Design; LinkedList and Stack

Question

I am writing a BFS and DFS in Java. What I was hoping to do was create one class like this:

/** Preforms BFS and DFS on ...
*/
public class Search{


  private XXX toSearch;
  // where XXX is an interface of Stack and LinkedList that has
  // remove() and add() methods.  

  public Search(boolean isBFS){
    if(isBFS)
      toSearch = new LinkedList();
    else
      toSearch = new Stack();
  }

  public void preformSearch(){
    while(toSearch.size() > 0){
      preformSearchOn(toSearch.remove());  // <----- KEY LINE
    }
  }

  private void preformSearchOn(...){...}

}

This class can perform BFS and DFS depending on how it is initialized. What is XXX? I don't think that it exists.

I thought that the entire point of object oriented programing is being able to do cool stuff like this.

What is the cleanest way to handle this?

Answer 1

With a Stack interface, you want to use the push() and pop() methods to interact with the stack. With a List interface, you use add() and remove(). The real problem here is the remove vs pop - not only are they named differently, they have different signatures, which for you means that you can't just call remove, you have to supply an argument.

That said, Stack extends Vector, which means that Stack objects also have Vector methods, like add and remove. So, you have two obvious options:

• Use a List<Foo> interface to your LinkedList and Stack (but then you can't use Stack methods)
• Or, write your own Searchable interface that has two implementations (one for Lists and one for Stacks) and let polymorphism do its thing.

---

Edit: the second bullet point above would be an application of the Strategy pattern, which is what @Mike's answer suggested (but using the key GoF term that I couldn't remember!).

Answer 2

I think you're looking for the Strategy pattern. The way to do this is not Java specific, or other "cool stuff" for this matter. These types of things transcend languages.

To be more concrete, develop two more classes named BfsStrategy and DfsStrategy. Require that each class implement a certain Strategy interface. Use the class you posted to perform operations on them transparently. (Change class/interface names to be more suitable if you need to.)

For example:

public final class Seeker<E, K> {

    private final E structure;
    private final SearchStrategy strategy;

    public Seeker(final E aStructure, final SearchStrategy aStrategy) {
        structure = aStructure;
        strategy = aStrategy;
    }

    public boolean search(K aKey) {
        return strategy.search(structure, key); //Pretty generic.
    }

}

Answer 3

XXX should be of type java.util.AbstractList as both LinkedList and Stack are derived from it.

But that will not solve you're problem, as the remove() method for each class will behave the same way. In order to get different behaviour you will actual need to call the different removale methods: remove() or pop(). And as method these remove() and pop() are both implemented on java.util.Linkedlist (see Queue interface) there is no need to use the java.util.Stack class either.

You could do call the different methods pop() and remove() with in an if statement, but that would be definitly be an OO anti pateern. An basic OO solution would be to implement 3 classes:

• Abstract parent named Search Class
• BfsSearch: works with remove() in it's search.
• DfsSearch: works with pop() in it's search.

This way, the user of this class can work with Search without needing to know if he is using BfsSearch or DfsSearch.

An even more advanced and flexible OO approach would be to use the Strategy pattern as described by mike. But for simple solutions that don't need this kind of flexibility it might be overkill.

BTW an excelent book on OO design that will explain all these kind of choices and patterns is Larman:

Applying UML and Patterns: An Introduction to Object-Oriented Analysis and Design and Iterative Development (3rd Edition)

Answer 4

The common interface is java.util.Queue.

As a first-in-first-out queue you can use (for instance) java.util.LinkedList or java.util.ArrayDeque.

As last-in-first-out queue, you can wrap any Deque using java.util.Collections.asLifoQueue.

Stack, together with is superclass Vector, is deprecated, because it synchronizes all method access, which is often unnecessary. I suspect that's why it doesn't implement Queue.

Answer 5

As far as breadth-first and depth-first searches go, one way to unify both would be to write java.util.Iterator implementations for each one. Let that be your unifying abstraction; it's already part of the JDK.