Skip to content

Instantly share code, notes, and snippets.

@ruskotron
Created February 3, 2017 17:07
Show Gist options
  • Save ruskotron/04c99ea046d464181cf2e1282cd47d0d to your computer and use it in GitHub Desktop.
Save ruskotron/04c99ea046d464181cf2e1282cd47d0d to your computer and use it in GitHub Desktop.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment