Code Listings for An Intuitive Guide to Data Structures, Version 2
Listings for several of the classes in the book are here.
The entire dynamic array class
public class AList {
private int[] data;
private int numElements;
private int capacity;
public AList() {
numElements = 0;
capacity = 10;
data = new int[capacity];
}
public void add(int item) {
if (numElements >= capacity)
enlarge();
data[numElements] = item;
numElements++;
}
private void enlarge() {
int[] copy = new int[capacity*2];
for (int i=0; i<capacity; i++)
copy[i] = data[i];
capacity *= 2;
data = copy;
}
@Override
public String toString() {
if (numElements == 0)
return "[]";
String s = "[";
for (int i=0; i<numElements-1; i++)
s += data[i] + ", ";
s += data[numElements-1] + "]";
return s;
}
public int get(int index) {
return data[index];
}
public void set(int index, int value) {
data[index] = value;
}
public int size() {
return numElements;
}
public boolean isEmpty() {
return numElements == 0;
}
public boolean contains(int value) {
for (int i=0; i<numElements; i++)
if (data[i] == value)
return true;
return false;
}
public void reverse() {
int[] rev = new int[capacity];
int j = 0;
for (int i=numElements-1; i>=0; i--) {
rev[j] = data[i];
j++;
}
data = rev;
}
public void reverse2() {
for (int i=0; i<numElements/2; i++) {
int hold = data[i];
data[i] = data[numElements-1-i];
data[numElements-1-i] = hold;
}
}
public void delete(int index) {
for (int i=index; i<numElements; i++)
data[i] = data[i+1];
numElements--;
}
public void insert(int index, int value) {
if (numElements >= capacity)
enlarge();
for (int i=numElements-1; i>=index; i--)
data[i+1] = data[i];
data[index] = value;
numElements++;
}
public static void main(String[] args) {
AList list = new AList();
list.add(2);
list.add(4);
System.out.println(list);
for (int i=0; i<10; i++)
list.add(i);
System.out.println(list);
}
}
The entire linked list class
public class LList {
private class Node {
public int value;
public Node next;
public Node(int value, Node next) {
this.value = value;
this.next = next;
}
}
private Node front;
public LList() {
front = null;
}
public void add(int value) {
if (front == null)
front = new Node(value, null);
else {
Node newNode = new Node(value, null);
Node node = front;
while (node.next != null)
node = node.next;
node.next = newNode;
}
}
@Override
public String toString() {
if (front == null)
return "[]";
String s = "[";
Node node = front;
while (node.next != null) {
s += node.value + ", ";
node = node.next;
}
s += node.value + "]";
return s;
}
public void addToFront(int value) {
front = new Node(value, front);
}
public boolean isEmpty() {
return front == null;
}
public int size() {
int count = 0;
Node node = front;
while (node != null) {
count++;
node = node.next;
}
return count;
}
public int get(int index) {
int count = 0;
Node node = front;
while (count < index) {
count++;
node = node.next;
}
return node.value;
}
public void set(int index, int value) {
int count = 0;
Node node = front;
while (count < index) {
count++;
node = node.next;
}
node.value = value;
}
public void insert(int index, int value) {
if (index == 0)
addToFront(value);
else {
int count = 0;
Node node = front;
while (count < index-1) {
count++;
node = node.next;
}
node.next = new Node(value, node.next);
}
}
public void delete(int index) {
if (index == 0)
front = front.next;
else {
int count = 0;
Node node = front;
while (count < index-1) {
count++;
node = node.next;
}
node.next = node.next.next;
}
}
public void doubler() {
Node node = front;
while (node != null) {
node.next = new Node(node.value, node.next);
node = node.next.next;
}
}
public void removeZeros() {
while (front != null && front.value == 0)
front = front.next;
Node node = front;
while (node != null && node.next != null) {
while (node.next != null && node.next.value == 0)
node.next = node.next.next;
node = node.next;
}
}
public static void main(String[] args) {
LList list = new LList();
list.add(1);
list.add(2);
System.out.println(list);
}
}
The entire generic linked list class
public class GLList<T> {
private class Node {
public T value;
public Node next;
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
}
private Node front;
public GLList() {
front = null;
}
public void add(T value) {
if (front == null)
front = new Node(value, null);
else {
Node newNode = new Node(value, null);
Node node = front;
while (node.next != null)
node = node.next;
node.next = newNode;
}
}
@Override
public String toString() {
if (front == null)
return "[]";
String s = "[";
Node node = front;
while (node.next != null) {
s += node.value + ", ";
node = node.next;
}
s += node.value + "]";
return s;
}
public void addToFront(T value) {
front = new Node(value, front);
}
public boolean isEmpty() {
return front == null;
}
public int size() {
int count = 0;
Node node = front;
while (node != null) {
count++;
node = node.next;
}
return count;
}
public T get(int index) {
int count = 0;
Node node = front;
while (count < index) {
count++;
node = node.next;
}
return node.value;
}
public void set(int index, T value) {
int count = 0;
Node node = front;
while (count < index) {
count++;
node = node.next;
}
node.value = value;
}
public static void main(String[] args){
GLList<Integer> list = new GLList<Integer>();
list.add(2);
list.add(3);
System.out.println(list);
GLList<String> list2 = new GLList<String>();
list2.add("hello");
list2.add("world");
System.out.println(list2);
GLList<GLList<String>> list3 = new GLList<GLList<String>>();
list3.add(list2);
list3.add(list2);
System.out.println(list3);
}
}
Stack class
public class LLStack<T> {
public class Node {
public T value;
public Node next;
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
}
private Node top;
public LLStack() {
top = null;
}
public void push(T value) {
top = new Node(value, top);
}
public T pop() {
T returnValue = top.value;
top = top.next;
return returnValue;
}
}
Queue class
public class LLQueue<T> {
private class Node {
public T value;
public Node next;
public Node(T value, Node next) {
this.value = value;
this.next = next;
}
}
Node front;
Node back;
public LLQueue() {
front = back = null;
}
public void add(T value) {
Node newNode = new Node(value, null);
if (back != null)
back = back.next = newNode;
else
front = back = newNode;
}
public T remove() {
T save = front.value;
front = front.next;
return save;
}
}
The entire binary tree class
public class BinaryTree<T>
{
private class Node {
public T value;
public Node left;
public Node right;
public Node(T value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
private Node root;
public BinaryTree() {
root = null;
}
public void add(T value, String location)
{
if (location.equals("")) {
root = new Node(value, null, null);
return;
}
Node node = root;
for (char c : location.substring(0, location.length()-1).toCharArray()) {
if (c == 'L')
node = node.left;
else
node = node.right;
}
if (location.charAt(location.length()-1) == 'L')
node.left = new Node(value, null, null);
else
node.right = new Node(value, null, null);
}
public int size() {
return sizeHelper(root);
}
private int sizeHelper(Node node) {
if (node == null)
return 0;
return sizeHelper(node.left) + sizeHelper(node.right) + 1;
}
public boolean contains(T value) {
return containsHelper(value, root);
}
private boolean containsHelper(T value, Node node) {
if (node == null)
return false;
if (node.value.equals(value) || containsHelper(value, node.left) ||
containsHelper(value, node.right))
return true;
else
return false;
}
public int height() {
return heightHelper(root);
}
private int heightHelper(Node node) {
if (node == null)
return 0;
int left = heightHelper(node.left);
int right = heightHelper(node.right);
if (left > right)
return left + 1;
else
return right + 1;
// return Math.max(heightHelper(node.left), heightHelper(node.right))+1;
}
public int countLeaves() {
return countLeavesHelper(root);
}
public int countLeavesHelper(Node node) {
if (node == null)
return 0;
if (node.left == null && node.right == null)
return 1;
return countLeavesHelper(node.left)+ countLeavesHelper(node.right);
}
@Override
public String toString() {
return toStringHelper(root);
}
private String toStringHelper(Node node) {
if (node == null)
return "";
else
return toStringHelper(node.left) + node.value + " " + toStringHelper(node.right);
}
private String toStringHelper(Node n, String location) {
if (n == null)
return "";
if (n == root)
return toStringHelper(n.left, location+"L") + " " + "root: " + n.value + "" + toStringHelper(n.right, location+"R");
return toStringHelper(n.left, location+"L") + " " + location + ": " + n.value + "" + toStringHelper(n.right, location+"R");
}
public String stuffAtEvenLevels() {
return stuffAtEvenLevelsHelper(root, 0);
}
public String stuffAtEvenLevelsHelper(Node node, int level) {
if (node == null)
return "";
if (level % 2 == 0)
return stuffAtEvenLevelsHelper(node.left, level+1) + node.value + " " +
stuffAtEvenLevelsHelper(node.right, level+1);
else
return stuffAtEvenLevelsHelper(node.left, level+1) +
stuffAtEvenLevelsHelper(node.right, level+1);
}
public static void main(String[] args) {
BinaryTree<Integer> tree = new BinaryTree<Integer>();
tree.add(3, "");
tree.add(4, "L");
tree.add(9, "R");
tree.add(12, "LL");
tree.add(15, "LR");
tree.add(0, "LRL");
tree.add(19, "RL");
tree.add(6, "RR");
tree.add(4, "RLR");
System.out.println(tree);
}
}
The entire binary search tree class
public class BinarySearchTree {
private class Node {
public int value;
public Node left;
public Node right;
public Node(int value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
private Node root;
public BinarySearchTree() {
root = null;
}
@Override
public String toString() {
return toStringHelper(root);
}
public String toStringHelper(Node node) {
if (node == null)
return "";
else
return toStringHelper(node.left) + node.value + " "
+ toStringHelper(node.right);
}
public void add(int value) {
if (root == null) {
root = new Node(value, null, null);
return;
}
Node node = root;
Node parent = null;
while (node != null) {
parent = node;
if (value <= node.value)
node = node.left;
else
node = node.right;
}
if (value <= parent.value)
parent.left = new Node(value, null, null);
else
parent.right = new Node(value, null, null);
}
public boolean contains(int value) {
Node node = root;
while (node != null) {
if (node.value == value)
return true;
else if (value < node.value)
node = node.left;
else
node = node.right;
}
return false;
}
public void delete(int value) {
// Special case if removing root and root doesn't have 2 children
if (root.value == value && root.left == null) {
root = root.right;
return;
}
if (root.value == value && root.right == null) {
root = root.left;
return;
}
// Get to the node being deleted
Node node = root;
Node parent = null;
while (node.value != value) {
parent = node;
if (value < node.value)
node = node.left;
else
node = node.right;
}
// Case 1: Deleting a leaf
if (node.right == null && node.left == null) {
if (node == parent.left)
parent.left = null;
else
parent.right = null;
}
// Case 2a: Deleting a node with only a left child
else if (node.right == null) {
if (node == parent.left)
parent.left = node.left;
else
parent.right = node.left;
}
// Case 2b: Deleting a node with only a right child
else if (node.left == null) {
if (node == parent.left)
parent.left = node.right;
else
parent.right = node.right;
}
// Case 3: Deleting a node with 2 children
else {
Node largest = node.left;
Node parentOfLargest = node;
while (largest.right != null) {
parentOfLargest = largest;
largest = largest.right;
}
node.value = largest.value;
if (parentOfLargest == node)
parentOfLargest.left = largest.left;
else
parentOfLargest.right = largest.left;
}
}
}
The generic binary search tree class
public class GBinarySearchTree<T extends Comparable<T>> {
private class Node {
public T value;
public Node left;
public Node right;
public Node(T value, Node left, Node right) {
this.value = value;
this.left = left;
this.right = right;
}
}
private Node root;
public GBinarySearchTree() {
root = null;
}
@Override
public String toString() {
return toStringHelper(root);
}
public String toStringHelper(Node node) {
if (node == null)
return "";
else
return toStringHelper(node.left) + node.value + " "
+ toStringHelper(node.right);
}
public void add(T value) {
if (root == null) {
root = new Node(value, null, null);
return;
}
Node node = root;
Node parent = null;
while (node != null) {
parent = node;
if (value.compareTo(node.value) <= 0)
node = node.left;
else
node = node.right;
}
if (value.compareTo(parent.value) <= 0)
parent.left = new Node(value, null, null);
else
parent.right = new Node(value, null, null);
}
public boolean contains(T value) {
Node node = root;
while (node != null) {
if (node.value.compareTo(value) == 0)
return true;
else if (value.compareTo(node.value) < 0)
node = node.left;
else
node = node.right;
}
return false;
}
public void delete(T value) {
// Special case if removing root and root doesn't have 2 children
if (root.value.compareTo(value) == 0 && root.left == null) {
root = root.right;
return;
}
if (root.value.compareTo(value) == 0 && root.right == null) {
root = root.left;
return;
}
// Get to the node being deleted
Node node = root;
Node parent = null;
while (node.value != value) {
parent = node;
if (value.compareTo(node.value) < 0)
node = node.left;
else
node = node.right;
}
// Case 1: Deleting a leaf
if (node.right == null && node.left == null) {
if (node == parent.left)
parent.left = null;
else
parent.right = null;
}
// Case 2a: Deleting a node with only a left child
else if (node.right == null) {
if (node == parent.left)
parent.left = node.left;
else
parent.right = node.left;
}
// Case 2b: Deleting a node with only a right child
else if (node.left == null) {
if (node == parent.left)
parent.left = node.right;
else
parent.right = node.right;
}
// Case 3: Deleting a node with 2 children
else {
Node largest = node.left;
Node parentOfLargest = node;
while (largest.right != null) {
parentOfLargest = largest;
largest = largest.right;
}
node.value = largest.value;
if (parentOfLargest == node)
parentOfLargest.left = largest.left;
else
parentOfLargest.right = largest.left;
}
}
}
The entire heap class
public class Heap {
private List<Integer> data;
public Heap() {
data = new ArrayList<Integer>();
}
public int peek() {
return data.get(0);
}
public void add(int value) {
data.add(value);
int c = data.size() - 1;
int p = (c-1) / 2;
while (p >= 0 && data.get(c) < data.get(p)) {
int temp = data.get(p);
data.set(p, data.get(c));
data.set(c, temp);
c = p;
p = (c-1)/2;
}
}
public int pop() {
int returnValue = data.get(0);
data.set(0, data.get(data.size()-1));
data.remove(data.size()-1);
int p = 0;
int c1 = 2*p + 1;
int c2 = 2*p + 2;
while(c1 < data.size() && c2 < data.size() &&
(data.get(c1) < data.get(p) || data.get(c2) < data.get(p))) {
if (data.get(c1) < data.get(c2)) {
int temp = data.get(p);
data.set(p, data.get(c1));
data.set(c1, temp);
p = c1;
}
else {
int temp = data.get(p);
data.set(p, data.get(c2));
data.set(c2, temp);
p = c2;
}
c1 = 2*p + 1;
c2 = 2*p + 2;
}
if (c2 >= data.size() && c1 < data.size() &&
data.get(c1) < data.get(p)) {
int temp = data.get(p);
data.set(p, data.get(c1));
data.set(c1, temp);
}
return returnValue;
}
}
The entire hash set class
public class HSet {
private final int A = 7927;
private final int B = 17393;
private List<List<Integer>> buckets;
public int h(int x) {
return A*x % B;
}
public HSet() {
buckets = new ArrayList<List<Integer>>();
for (int i=0; i<B; i++)
buckets.add(new ArrayList<Integer>());
}
public void add(int x) {
int bucket = h(x);
if (!buckets.get(bucket).contains(x))
buckets.get(bucket).add(x);
}
public void remove(int x) {
int bucket = h(x);
if (buckets.get(bucket).contains(x))
buckets.get(bucket).remove((Integer) x);
}
public boolean contains(int x) {
int bucket = h(x);
return buckets.get(bucket).contains(x);
}
@Override
public String toString() {
String s = "{";
for (List<Integer> list : buckets)
for (int x : list)
s += x + ", ";
if (s.equals("{"))
return "{}";
else
return s.substring(0, s.length()-2) + "}";
}
}
Graph class
public class Graph<T> implements Iterable<T> {
protected Map<T, List<T>> neighbors;
public Graph() {
neighbors = new LinkedHashMap<T, List<T>>();
}
public void add(T v) {
if (!neighbors.containsKey(v))
neighbors.put(v, new ArrayList<T>());
}
public void addEdge(T u, T v) {
neighbors.get(u).add(v);
neighbors.get(v).add(u);
}
public List<T> getNeighbors(T v) {
return new ArrayList<T>(neighbors.get(v));
}
@Override
public Iterator<T> iterator() {
return neighbors.keySet().iterator();
}
}
Digraph class
public class Digraph<T> extends Graph<T> {
@Override
public void addEdge(T u, T v) {
neighbors.get(u).add(v);
}
}
BFS and DFS
public class Search {
public static <T> Set<T> bfs(Graph<T> graph, T start) {
Set<T> found = new LinkedHashSet<T>();
Deque<T> waiting = new ArrayDeque<T>();
found.add(start);
waiting.add(start);
while (!waiting.isEmpty()) {
T v = waiting.remove();
for (T u : graph.getNeighbors(v)) {
if (!found.contains(u)) {
found.add(u);
waiting.add(u);
}
}
}
return found;
}
public static <T> Set<T> dfs(Graph<T> graph, T start) {
Set<T> found = new LinkedHashSet<T>();
Deque<T> waiting = new ArrayDeque<T>();
found.add(start);
waiting.add(start);
while (!waiting.isEmpty()) {
T v = waiting.removeLast();
for (T u : graph.getNeighbors(v)) {
if (!found.contains(u)) {
found.add(u);
waiting.add(u);
}
}
}
return found;
}
public static <T> List<T> bfsPath(Graph<T> graph, T start, T end) {
Set<T> found = new LinkedHashSet<T>();
Deque<T> waiting = new ArrayDeque<T>();
Map<T, T> parent = new LinkedHashMap<T, T>();
found.add(start);
waiting.add(start);
parent.put(start, null);
while (!waiting.isEmpty()) {
T v = waiting.remove();
for (T u : graph.getNeighbors(v)) {
if (!found.contains(u)) {
found.add(u);
waiting.add(u);
parent.put(u, v);
}
if (u.equals(end)) {
List<T> path = new ArrayList<T>();
while (u != null) {
path.add(u);
u = parent.get(u);
}
Collections.reverse(path);
return path;
}
}
}
return new ArrayList<T>();
}
public static <T> List<T> dfsPath(Graph<T> graph, T start, T end) {
Set<T> found = new LinkedHashSet<T>();
Deque<T> waiting = new ArrayDeque<T>();
Map<T, T> parent = new LinkedHashMap<T, T>();
found.add(start);
waiting.add(start);
parent.put(start, null);
while (!waiting.isEmpty()) {
T v = waiting.removeLast();
for (T u : graph.getNeighbors(v)) {
if (!found.contains(u)) {
found.add(u);
waiting.add(u);
parent.put(u, v);
}
if (u.equals(end)) {
List<T> path = new ArrayList<T>();
while (u != null) {
path.add(u);
u = parent.get(u);
}
Collections.reverse(path);
return path;
}
}
}
return new ArrayList<T>();
}
}