LinkedSet.java

public class LinkedSet<Row> {

    /* "Empty" list, is first and last with null values - first & last are same */
    private Node first = null;
    private Node last = null;

    private Map<Row, Node> index = new HashMap<Row, Node>();

    /* Linked-list node */
    private final class Node {

        private Row value;

        private Node next = null;
        private Node prev = null;

        private Node(Row value) {
            this.value = value;
        }

        /* Node removes itself */
        private void remove() {

			      value = null;

            if (prev == null && next == null) {

                /* Removing final single entry in list (first=last) */

                if (!index.isEmpty()) {

                    /* Not expected to be possible */
                    index.clear();
                }

                /* No other nodes so just ensure links are back to initial "empty" state */
                first = null;
                last = null;
                return;
            }

            if (prev == null) {

                /* This is the eldest, so pass the crown on */
                first = next;
                next.prev = null;

            } else if (next == null) {

                /* This is the youngest */
                last = prev;
                prev.next = null;

            } else {

                /* Otherwise simply an intermediate node */
                next.prev = prev;
                prev.next = next;
            }

            prev = null;
            next = null;
        }
    }

    public Row add(Row f) {

        /* Only expect duplicate items exceptionally so happy to
           absorb overhead of redundant instance creation if that occurs */
        Node newNode = new Node(f);

        /* Create a new index entry */
        Node oldNode = index.put(f, newNode);

        /* Should only occur exceptionally */
        Row oldValue = null;
        if (oldNode != null) {

            oldValue = oldNode.value;
            oldNode.remove();
        }

        /* If list is "Empty" then just set the value */
        if (first == null) {

            first = newNode;
            last = newNode;

            return oldValue;
        }

        newNode.prev = last;
        last.next = newNode;
        last = newNode;

        return oldValue;
    }

    public Row remove(Row id) {

        /* If list is empty */
        if (isEmpty()) {

            return null;
        }

        /* remove node from index */
        Node node = index.remove(id);

        if (node == null) {

            return null;
        }

        Row value = node.value;

        /* Remove from the linked list */
        node.remove();

        return value;
    }

    public Row first() {

        if (isEmpty()) return null;

        return first.value;
    }

    Row last() {

        if (isEmpty()) return null;

        return last.value;
    }

    public Row popFirst() {

        if (isEmpty()) return null;

        Row value = first.value;

        first.remove();

        return value;
    }

    public Row popLast() {

        if (isEmpty()) return null;

        Row value = last.value;

        last.remove();

        return value;
    }

    int size() {

        return index.size();
    }

    public boolean isEmpty() {

        /* Only testing one of these should be necessary but
           the second one is free and gives peace of mind */
        return first == null && last == null;
    }

    void clear() {

        index.clear();

        /* Just clear our root references and GC will sort it out */
        first = null;
        last = null;
    }
}