||5 years ago|
|guava||5 years ago|
|BinaryTree.java||5 years ago|
|Deque.java||5 years ago|
|LList1.java||5 years ago|
|LList2.java||5 years ago|
|LList3.java||5 years ago|
|README.md||5 years ago|
|TDeque.java||5 years ago|
|TList.java||5 years ago|
Java Data Structures
Java Linked List
Contains implementation(s?) of (a) linked list class(es?).
- List interface to provide generic iterable interface for list.
- 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:
- data (what type? define a type or use a template )
- next pointer (implicit Node type)
- 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
- Permissions, accessing components
- Dealing (or not dealing) with and raising exceptions
- 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
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:
- root - points to the root node of the tree
- initialize with a root node, or without a root node
Binary Tree Node class:
- data - stores the data for this node
- left - points to left child
- right - points to right child
- initialize with data (left and right are null pointers)
- initialize with data, left, and right
- 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 a node with one child
- Delete an internal node with multiple
- Depth first (recursive)
- Breadth first (queue)
- 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