Data Structures in Java

Yes, these structures exist as built-in Java objects. The purpose of this project is to practice by implementing them.

Set

• View my source file.

• View my unit tests.

The set is backed by a Map that stores elements as keys and sets all values to be false. This is actually how the Java HashSet works! As with the hash-map, all three set operations (insert , contains, delete) have runtime O(1) by design.

Map

• View my source file.

• View my unit tests.

The map is implemented as a hash-map. All four map operations (insert, delete, get, hasKey) have runtime O(1) by design.

⚠️ Since resizing the map takes O(n) time, some insertions are O(n). On average, this happens only 1/n times, so the average runtime of insert is O(1).

Queue

• View my source file.

• View my unit tests.

The queue is implemented as a subclass of DoublyLinkedList. All five queue operations (offer , remove, poll, element, peek) have runtime O(1) by design.

Stack

• View my source file.

• View my unit tests.

The stack is implemented as a subclass of DoublyLinkedList. All four stack operations (push , pop, peek, empty) have runtime O(1) by design.

Doubly-linked list

• View my source file.

• View my unit tests.

Unlike singly-linked nodes, doubly-linked nodes keep track of their predecessor (in addition to their successor). This makes reverse traversal an operation that runs in O(1) time. It also allows for much more concise code because it eliminates the need to keep track of the preceding node while iterating over the list (once the target is found, it stores a pointer to the previous node). Searching for an element or indexing is still O(n).

Singly-linked list

• View my source file.

• View my unit tests.

Singly-linked nodes only keep track of their successor so there is no easy way to iterate backward. Certain operations are O(n) instead of O(1) because to find a preceding node one must iterate from the start of the list.

License

MIT license.