We often use TreeSet or HashSet from the Java standard library, whose underlying implementations are red-black trees and hash tables, respectively. In this paper, we define our own Set interface, using our previous implementation of the data structure linked list, binary search tree, AVL tree to achieve this Set interface;

1. Set interface

The Set interface is shown as follows, and the function of the method is described in the annotation.

Public interface Set<E> {// Add (E E); Void remove(E E); Boolean contains(E E); Int getSize(); // return whether the set isEmpty Boolean isEmpty(); }Copy the code

2, linked list implementation of the Set Set

The list implementation’s Set is shown below, which is essentially a wrapper around our own list Api. Our own list implementation is shown in Data Structures 02.

Note that the Set we define does not allow duplicate elements, so the add method needs to check if it exists;

public class LinkedListSet<E> implements Set<E> {

    private LinkedList<E> list;

    public LinkedListSet(){
        list = new LinkedList<>();
    }

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

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

    @Override
    public boolean contains(E e){
        return list.contains(e);
    }

    @Override
    public void add(E e){
        if(!list.contains(e))
            list.addFirst(e);
    }

    @Override
    public void remove(E e){
        list.removeElement(e);
    }
}
Copy the code

3, binary search tree implementation of the Set Set

The Set of binary search tree implementation is shown below, which is actually a layer of encapsulation of our binary search tree API. The binary search tree implementation is shown in Data Structure 05.

Why does the list add method need to be checked for existence, but not now? Because the binary search tree we implemented couldn’t hold repeating elements;

public class BSTSet<E extends Comparable<E>> implements Set<E> { private BST<E> bst; public BSTSet(){ bst = new BST<>(); } @Override public int getSize(){ return bst.size(); } @Override public boolean isEmpty(){ return bst.isEmpty(); } @Override public void add(E e){ bst.add(e); } @Override public boolean contains(E e){ return bst.contains(e); } @Override public void remove(E e){ bst.remove(e); }}Copy the code

4, AVL tree implementation of the Set

The AVL tree implementation Set is shown below, which is actually a layer of encapsulation of the AVL tree API we implemented. The AVL tree we implemented is shown in Data Structure 07.

The AVL tree we implemented defines two types of generics for the purpose of mapping Map. However, when we implement Set, we only need K as a generic. We can define V as Object and Set it to null when used.

Similarly, the add function does not need to be checked for existence, because our AVL tree does not support storing duplicate elements.

public class AVLSet<E extends Comparable<E>> implements Set<E> { private AVLTree<E, Object> avl; public AVLSet(){ avl = new AVLTree<>(); } @Override public int getSize(){ return avl.getSize(); } @Override public boolean isEmpty(){ return avl.isEmpty(); } @Override public void add(E e){ avl.add(e, null); } @Override public boolean contains(E e){ return avl.contains(e); } @Override public void remove(E e){ avl.remove(e); }}Copy the code