Some "hello world"-style data structure objects. Helps with inane tech interview questions and/or teaching computer science - whichever comes first.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
Charles Reid 9aff4bc305 Fixing traveling salesperson solution for clarity. 5 years ago
..
guava Fixing traveling salesperson solution for clarity. 5 years ago
BinaryTree.java Updating the way Java binary tree is created. 5 years ago
Deque.java Adding double-ended queue class in Java. 5 years ago
LList1.java updating java linked lists to print -> 5 years ago
LList2.java updating java linked lists to print -> 5 years ago
LList3.java updating java linked lists to print -> 5 years ago
README.md Adding deque and templated linked list information to Java readme. 5 years ago
TDeque.java Adding Java templated double-ended queue. 5 years ago
TList.java Expanding on Java LinkedList<T> generic class template 5 years ago

README.md

Java Data Structures

Java Linked List

Contains implementation(s?) of (a) linked list class(es?).

Interfaces:

  • List interface to provide generic iterable interface for list.

Classes:

  • List node that contains data and next (default const. points to null)
  • LinkedList class, that points to the front of the list (default const., tostring, add, remove, indexof, get)

Key Classes and Features

Linked List Node class:

  • Fields:
    • data (what type? define a type or use a template )
    • next pointer (implicit Node type)
  • constructors
    • what are the essential operations needed in a linked list?
    • basic is initial, default constructor, 0 and null and nothing
    • constructors may want to pass data, may want to pass a node, but whatever the case, they can always change the "next" pointer and the data value after initialization
  • iterable interface

Key features:

  • Permissions, accessing components
  • Operations
  • Dealing (or not dealing) with and raising exceptions

Key functionality:

  • add (at end)
  • add at index
  • remove index
  • indexOf value
  • get size
  • get node at location

Round 1: LList1

Round 1 is a basic implementation of functionality:

  • Linked list class
  • Node class
  • add and remove
  • indexOf
  • size

A few things we have to decide:

  • Don't worry about exceptions
  • Storing integer data, could make it more complicated later but keeping it simple for sake of situation.

Round 2: LList2

This adds two remove duplicates method:

  • Remove duplicates using a temporary buffer (Set object)
  • Remove duplicates without using a temporary buffer (using two pointers)

Round 3: LList3

This adds a recursive add method. If current.next is not null, we recursively call the method on itself.

Round 4: TList

Templated linked list and linked list node class. This does not implement comparators or equality checks for the template type T (a simple Cartesian point class).

Java Binary Tree

Implementations of a binary tree.

Binary Tree class:

  • Fields
    • root - points to the root node of the tree
  • Constructors
    • initialize with a root node, or without a root node

Binary Tree Node class:

  • Fields
    • data - stores the data for this node
    • left - points to left child
    • right - points to right child
  • Constructors
    • initialize with data (left and right are null pointers)
    • initialize with data, left, and right

Key functionality:

  • Insert
    • Add new node to a leaf node (specify which child it should be)
    • Add new node to an internal node (speicfy which child it should be)
  • Delete
    • Delete a node with one child
    • Delete an internal node with multiple
  • Traversal
    • Depth first (recursive)
    • Breadth first (queue)
  • Properties
    • Count number of nodes
    • Count levels in tree
    • Check if full or proper tree (each node has 0 or 2 children)
    • Check if perfect tree (proper tree, and all leaves have same depth or level)
    • Check if complete tree (every level, except possibly last, are full)

Java Binary Array Tree

Binary trees can be stored as linked lists, but they can also be implemented using arrays. This class contains an array implementation of a binary tree, in lieu of the Node and pointer concept.

This is analogous to the linked list implementation in Perl, where we keep track of array indices instead of pointers to object locations in memory.

Guava: Traveling Salesman Problem

The Traveling Salesman problem is implemented using a Network object from Google's Guava library in Java.

This class implements recursive backtracing to search for solutions.

To compile, need to specify the path to the Guava jar:

$ javac -cp '.:/Users/charles/codes/guava/jars/guava-21.0.jar' TSP.java

$ java -cp '.:/Users/charles/codes/guava/jars/guava-21.0.jar' TSP.java

Example output: the following example output was created for a network of five cities, each city named A, B C, D, E. The adjacency matrix is hard-coded. The printout shows that the shortest route found was A E D C B.

@@@@@@@@@@	NEW SOLUTION	Route: [A, B, C, D, E]	Distance: 41.0
XXXXXXXXXX	NO SOLUTION	Route: [A, B, C, E, D]	Distance > Min: 65.0 > 41.0
XXXXXXXXXX	NO SOLUTION	Route: [A, B, D, C, E]	Distance > Min: 76.0 > 41.0
XXXXXXXXXX	NO SOLUTION	Route: [A, B, D, E, C]	Distance > Min: 75.0 > 41.0
@@@@@@@@@@	NEW SOLUTION	Route: [A, C, B, D, E]	Distance: 38.0
XXXXXXXXXX	NO SOLUTION	Route: [A, C, E, D, B]	Distance > Min: 56.0 > 38.0
XXXXXXXXXX	NO SOLUTION	Route: [A, D, B, C, E]	Distance > Min: 78.0 > 38.0
XXXXXXXXXX	NO SOLUTION	Route: [A, D, E, C, B]	Distance > Min: 61.0 > 38.0
XXXXXXXXXX	NO SOLUTION	Route: [A, E, C, B, D]	Distance > Min: 76.0 > 38.0
XXXXXXXXXX	NO SOLUTION	Route: [A, E, C, D, B]	Distance > Min: 70.0 > 38.0
XXXXXXXXXX	NO SOLUTION	Route: [A, E, D, B, C]	Distance > Min: 51.0 > 38.0
@@@@@@@@@@	NEW SOLUTION	Route: [A, E, D, C, B]	Distance: 35.0

Java Double-Ended Queue (Deque)

Replicating the double-ended queue, or deque, implementation in the Python containers library. Link to deque documentation

This stores integers, is not very fancy, and there's some complicated dancing going on with pointers, but it's a simple implementation of a double-ended queue. It is easy to rewrite this as a generic, templated data container.

The Java Deque object follows the convention of the Python deque object in the convention that the right side is the front of the list, the left side is the back of the list, and implements the following methods:

  • append(): appends to the right (front) of the Deque object.
  • appendLeft(): appends to the left (end) of the Deque object.
  • pop(): pops from the right (front) of the Deque object.
  • popLeft(): pops from the left (end) of the Deque object.

To compile and run, just do:

$ javac Deque.java
$ java Deque