algorithms-java

A collection of fundamental data structures and algorithms implemented in Java. This project demonstrates classic computer science concepts including stacks, linked lists, hash tables, and binary search trees through practical examples.

Purpose

This repository serves as an educational resource for understanding core data structures and algorithms. Each laboratory module focuses on different concepts:

• Lab 1: Linear data structures (Stack and Linked List)
• Lab 2: Hash-based storage with collision resolution
• Lab 3: Hierarchical data structures (Binary Search Tree)

Project Structure

algorithms-java/
├── labw1-gradle/                    # Lab 1: Stack and Linked List
│   ├── build.gradle
│   └── src/main/java/nau/algorithms/
│       ├── Main.java                # Demo application
│       ├── IntegerStack.java        # Array-based stack implementation
│       ├── StringLinkedList.java    # Singly linked list implementation
│       └── LinkedListElement.java   # Linked list node element
│
├── labw2-gradle/                    # Lab 2: Hash Table
│   ├── build.gradle
│   └── src/main/java/nau/algorithms/
│       ├── Main.java                # Demo application
│       ├── HashTable.java           # Hash table with double hashing
│       ├── Trapeze.java             # Geometric trapezoid shape
│       └── Point.java               # 2D point representation
│
├── labw3-gradle/                    # Lab 3: Binary Search Tree
│   ├── build.gradle
│   └── src/main/java/nau/algorithms/
│       ├── Main.java                # Demo application
│       ├── Tree.java                # Binary search tree implementation
│       ├── TreeNode.java            # BST node wrapper
│       └── Student.java             # Student record data class
│
├── README.md
└── LICENSE

Requirements

• Java: JDK 8 or higher
• Build Tool: Gradle 2.5+
• Dependencies:
  • JUnit 4.11 (testing)
  • JavaFaker 0.7 (Lab 3 only - generates random student data)

Installation & Compilation

Clone the Repository

git clone https://github.com/maximillian2/algorithms-java.git
cd algorithms-java

Build Individual Labs

Each lab is a separate Gradle project. Navigate to the desired lab directory and build:

# Lab 1: Stack and Linked List
cd labw1-gradle
./gradlew build

# Lab 2: Hash Table
cd labw2-gradle
./gradlew build

# Lab 3: Binary Search Tree
cd labw3-gradle
./gradlew build

Run the Applications

# Run Lab 1
cd labw1-gradle
./gradlew run

# Run Lab 2
cd labw2-gradle
./gradlew run

# Run Lab 3
cd labw3-gradle
./gradlew run

Or run the compiled JAR files:

java -jar build/libs/labw1-gradle-all-1.0-release.jar

Usage Examples

Lab 1: Stack and Linked List

// Stack operations
IntegerStack stack = new IntegerStack(15);
stack.push(10);          // Add element to top
stack.push(20);
int value = stack.pop(); // Remove and return top element (20)
boolean empty = stack.isEmpty();
boolean full = stack.isFull();

// Linked List operations
StringLinkedList list = new StringLinkedList();
list.addToStart(5);      // Add to beginning (stored as hex: "5")
list.addToEnd(32);       // Add to end (stored as hex: "20")
list.deleteElement(new LinkedListElement(5));
list.inspect();          // Print: 20 ->

Sample Output:

1 LEVEL
Stack emptiness: true
Stack full: true
Overflow is returning false
Content: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Stack popped: 15
Content: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0

2 LEVEL
8 -> 5 -> 20 ->
Deleted item form list: 20
8 -> 5 ->

Lab 2: Hash Table with Trapezoids

// Create hash table and add geometric shapes
HashTable table = new HashTable(10);
table.addValue(new Trapeze());  // Trapeze with random coordinates
table.inspect();                // Display all elements

// Remove elements with area less than threshold
table.removeElementsLessThan(100.0);

Sample Input/Output:

Enter square value: 50
1: Point #1: x -> -5, y -> 12; Point #2: ... Perimeter: 45.2; Square: 78.5;
2: null
3: Point #1: x -> 8, y -> -3; Point #2: ... Perimeter: 62.1; Square: 125.0;
...

Lab 3: Binary Search Tree with Students

// Create BST and add student records
Tree tree = new Tree();
tree.addNode(new TreeNode(new Student()));  // Random student data
tree.inspect();  // In-order traversal

// Search for students by course and average mark
tree.search(3, 4.5);  // Find students in course 3 with avg mark 4.5

Sample Input/Output:

Student: Johnson; course #3; student's ticket: 456; avg. mark: 4.5; citizenShip: Germany
Enter course: 3
Enter average mark: 4.5
Found:
Student: Johnson; course #3; student's ticket: 456; avg. mark: 4.5; citizenShip: Germany

Algorithm Details

IntegerStack (Lab 1)

Array-based LIFO (Last-In-First-Out) data structure with fixed capacity.

• Time Complexity: O(1) for push, pop, isEmpty, isFull
• Space Complexity: O(n) where n is stack capacity

StringLinkedList (Lab 1)

Singly linked list storing values as hexadecimal strings.

• Time Complexity: O(1) for addToStart, O(n) for addToEnd and deleteElement
• Space Complexity: O(n) for n elements

HashTable (Lab 2)

Hash table using double hashing for collision resolution.

• Hash Function: key % tableSize
• Double Hash: (counter + (key % tableSize)) % tableSize
• Time Complexity: O(1) average, O(n) worst case

Binary Search Tree (Lab 3)

BST ordered by student ticket number with recursive operations.

• Time Complexity: O(log n) average, O(n) worst case for add/search
• Traversal: In-order (left → root → right)

Class Documentation

Lab 1 Classes

Class	Description	Key Methods
IntegerStack	Fixed-size array-based stack for integers	push(int), pop(), isEmpty(), isFull(), inspect()
StringLinkedList	Singly linked list with hex string values	addToStart(int), addToEnd(int), deleteElement(LinkedListElement), isEmpty(), inspect()
LinkedListElement	Node element for linked list	Constructor accepts int or String, auto-converts int to hex

Lab 2 Classes

Class	Description	Key Methods
HashTable	Hash table with double hashing collision resolution	addValue(Trapeze), removeElementsLessThan(double), inspect()
Trapeze	Geometric trapezoid with 4 points	getSquare(), getPerimeter(), validate(), toString()
Point	2D coordinate point	Public fields: x, y

Lab 3 Classes

Class	Description	Key Methods
Tree	Binary search tree implementation	addNode(TreeNode), inspect(), search(int course, double avgMark)
TreeNode	BST node wrapping Student data	getDataValue(), toString()
Student	Student record with fake data generation	getStudentsTicket(), getCourse(), getAverageMark(), getCitizenShip()

Contents

1. Laboratory work #1 ☕

2. Laboratory work #2 ☕

3. Laboratory work #3 ☕

License

This project is licensed under the MIT License - see the LICENSE file for details.