Data Structures and Algorithms

From-scratch attempts at implementing some common data structures and algorithms.

Currently, this repo contains (both bug-free and buggy) versions of code I've written to try to get a better understanding of the under-the-hood inner workings of various data structures.

As of this writing (23 July 2022), most of the code is in Python3, though some Java and C++ updates have started to creep in as well. Future iterations will include more Java and C++ code, and perhaps some other languages as well. Update: Due to some changes in circumstance, C++ may become the main focal point of my contributions; we shall see.

As of 3 July 2022, a study guide has also made its way into the repo. This study guide is LaTeX'ed and is intended to help guide my studies + document the journey so far. Update: Later, I removed the TeX source code from the repo so that the code percentages would better reflect my real contributions rather than showing a repo with 80% TeX code!

TODO:

• Consider returning pointer-type variables in data structures where "actual return" of a variable is impossible (see stack in CPP).
• Use this link to concert Concatenate(...) functionality into operator overloading in LinkedList.cpp file.
• Incorporate more headers for new LinkedList.cpp file.
• Work on porting the old C++ singly linked list + doubly linked list algorithms to the new LinkedList.cpp implementation.
• Make sure C++ files adhere to best practices re: Rule of Three/Five/Zero and RAII.
• Continue adding to SparseMatrixStruct.cpp and SparseMatrix.cpp (include subtraction; possibly multiplication?).
• Get all the Python code translated in to C++ (!!!) and Java (as time permits).
• Translate Array ADT from C++ to Python and Java.
• Get study guide source re-added so I can work on it elsewhere.
• Keep working on the study guide.

Changelog

5 Jul 2023

1. Reorganization of Trees, Tries, and Hybrid Trees in the study guide.
2. Later, more fleshing out of study guide subsections on trees and substructures.

26 Jun 2023

1. Edited the study guide to include more information about queues and related structures.
2. Made several other study guide changes/commits throughout the day.

23 Jun 2023

1. Edited the study guide to include more information about queues + to better delineate the subsections of the stack and queue topics.

21 Jun 2023

1. In array-based stack.cpp: Made changes to Peek().
2. Later, made initial commits of Node.h, LinkedList.h, and stack.cpp for LinkedList-based stack.
3. Made changes to Display() functions in both LinkedList.h and LinkedList-based stack.cpp.
4. Later, made changes to Peek(int index) in LinkedList-based stack.cpp to ensure that "Invalid Position!" prints whenever index is greater than top+1.

21 Jun 2023

1. Initial commit of array-based stack.cpp in CPP.
2. Added Pop() functionality to stack.
3. After some time weighing how to handle the Stack underflow! situation, changed Pop() to return pointer type variable.
4. After learning that Stack underflow! resulted in seg fault in VSCode, I decided to undo the above change for the time being.
5. Later, Added Peek(...), IsEmpty(), and IsFull().

14 Jun 2023

1. Updated the study guide some restructuring re: Stacks, Queues, etc.

13 Jun 2023

1. Added Middle() support to LinkedList.cpp.
2. Later, updated the study guide with details related to linked lists, variants of linked lists, and linked lists versus arrays.

9 Jun 2023

1. In LinkedList.cpp: Added Append(...) functionality, which should have been here a long time ago.
2. After much back-and-forth, added Concatenate(...) functionality. Later, this will come in the form of an overloaded operator.
3. Later, refactored (old) Concatenate(...) into (renamed) Join(...) and (new) (void) Concatenate(...).

8 Jun 2023

1. In LinkedList.cpp: Added new example + SortedQ().
2. Later, added DeleteDuplicates() in LinkedList.cpp.
3. Eventually, swapped order of parameters for Insert(...) to better match what happens in the Array ADT.
4. Added Reverse() functionality to LinkedList.cpp.
5. From home: Renamed /Okay/ to /Working/.

7 Jun 2023

1. Added Display() to LinkedList.cpp.
2. Later, added Length(), Sum(), Min(), and Max() to LinkedList.cpp.
3. Added Insert(...) to LinkedList.cpp.
4. Later, added Delete(...) to LinkedList.cpp, and later, made a small edit to Delete(...).
5. At home, moved CPP/SinglyLinkedList/ and CPP/DoublyLinkedList to /Obsolete/CPP/ per inclusion of new /LinkedList/ files.

6 Jun 2023

1. Changed LinkedList.cpp to have head as a pointer + percolated the associated method changes throughout.
2. Changed the name of old-LinkedList.cpp file to LinkedListLegacy.cpp.

31 May 2023

1. Initial commit of Node.h and LinkedList.cpp; the particulars of this were written last week but uncommitted.

26 May 2023

1. Updated the study guide.

24 May 2023

1. Initial commit of SparseMatrix.h and SparseMatrixNew, featuring hard-coded int-type data Element.x. I'm still trying to figure out the intricacies of the templating for non-integer types.
2. Later, deleted those two files to try to figure out stuff.
3. After much work + help on Stack Overflow: Got SparseMatrix.cpp to work with generics / templating. I'm an idiot for not considering forward-declaration as a solution sooner; forward-declaration literally solved one of my Array.h problems the other day!
4. Split SparseMatrix.cpp into Element.h and SparseMatrix.h.

23 May 2023

1. Initial commit of SparseMatrixStruct.cpp.
2. Later, added Add() functionality to SparseMatrixStruct.cpp.
3. Uploaded initial commit of SparseMatrix.cpp, which uses classes instead of structs.
4. Later: Swapped Read() and Display() for overloaded cin and cout.
5. Even later: Implemented old Add() as custom SparseMatrix::operator+ operator.

22 May 2023

1. In LowerTriangularMatrix.cpp: Revamped loops to start at i=1 and j=1.
2. Later, initial commit of UpperTriangularMatrix.h and UpperTriangularMatrix.cpp using row-major mapping.
3. Used LowerTriangularMatrix* to build initial commit of SymmetricMatrix*---and later, TridiagonalMatrix*---files.
4. Fixed bug in ShortPrint() for SymmetricMatrix.cpp.
5. Later, fixed indexing bug in TridiagonalMatrix.cpp and fixed typo in README.
6. Even later: Initial commit of ToeplitzMatrix.h and ToeplitzMatrix.cpp.

18 May 2023

1. Added destructor to Array ADT in C++.
2. Created CPP/Matrices directory + added initial commit of DiagonalMatrix files (.cpp and .h).
3. Later, created C++ files LowerTriangularMatrix.h and LowerTriangularMatrix.cpp using row-major mapping.
4. Improved commenting in Array.h, DiagonalMatrix.cpp, and LowerTriangularMatrix.cpp.
5. Added a driver to LowerTriangularMatrix.cpp to allow for entering a whole matrix all at once.

16 May 2023

1. In C++ Array ADT: Added Setters, in part to allow the public T* A to become private.
2. Later, declared Union2 as a friend function to allow access to private member variables.
3. Added better commenting to show the breakdown of functions throughout code.
4. Later, moved legacy functions to ArrayLegacy.cpp and renamed Union2 and Union3 both as Union.
5. Also: Implemented friend versions of Intersection and Complement.
6. Later still: Changed a number of dereferencing operations to ->s.
7. Also, added Intersection, Complement member functions.

15 May 2023

1. In C++ Array ADT: Added functionality for Intersection and Complement.
2. Later, simplified Intersection algorithm and changed the existing algorithm to LegacyIntersection for posterity.
3. Eventually figured out a non-Void version of Union in C++ Array ADT. This will be fleshed out more soon.
4. Mimicked non-member Union2 code into member function Union3.

12 May 2023

1. Made some small code tweaks to the Array ADT in C++, and later, added support for Contains and (Unsorted) Union.

11 May 2023

1. To Array ADT in C++: Added Get, Set, Sum, Avg, Max, and Min.
2. Later, rewrote some code in a clearer manner + deleted some commented-out code in C++ Array ADT.
3. In Array ADT C++ files: Added Reverse, LeftShift, LeftRotate, RightShift, RightRotate.
4. Added functionality in Array ADT for SortedInsert, IsSorted, and PosNegSwap.
5. Later, improved incapsulation in Array ADT by making member vars private + adding getters.

10 May 2023

1. Committed initial version of Array ADT in C++ (both .cpp and .h files).
2. Later, fixed up some pointer-related things in Array ADT.

19 Aug 2022

1. Made some small edits to linked list in C++
2. Completed doubly linked list in C++ with generics.

14 Aug 2022

1. Completed singly linked list in C++ with generics.
2. Learned more about pointers, but still need additional refresher.

12 Aug 2022

1. Started working on singly linked lists in C++.
2. In so doing, realized I have a lot to (re-)learn (for the 17th time) about pointers.

10 Aug 2022

1. Got a 0^th draft of hash sets working in C++. To get this working, I had to abandon my aspirations for generic types and just stick with integers. Generic types will come soon! ::crosses fingers::
2. Later, added working(!!!) generics to C++ hash sets.
3. Also, removed references to this->*, as that doesn't appear to be very C++-like? 🤷

23 Jul 2022

1. Decided to try my hand at hash sets in C++ after having not written C++ code in 15 years. It did not go well!
2. Made some small tweaks to the Java Hash Map file.
3. Edited the README and the .gitignore files.
4. Later, removed some of the Python test code so the GitHub calculator thing gets the language percentages more accurate.

16 Jul 2022

1. Filled in the Stacks and Queues section of the study guide.
2. Also, added in the Stack and Queue rows of the first-page complexity table.

12 Jul 2022

1. Made a few small edits to the study guide.
2. Also, added a section for Stacks and Queues + filled in the subsections a bit before bedtime.

9 Jul 2022

1. Made some complexity-related edits to the study guide.

8 Jul 2022

1. Renamed the repo to include common algorithms. Will ultimately restructure the directories as well.
2. Later, restructured all subdirectories.
3. Much later, wrote + uploaded initial versions of SelectionSort for both Python3 and Java.

   Both versions include the algorithm, as well as a SelectionSortAnalysis method/function which shows how the number of steps grows as the size of the input array doubles.

   What I reallllllly want to show is how time increases, not code count. I'll do some digging into that soon and try to implement ASAP.

4. Much later still, updated the study guide pretty heavily, including uses of newly-included images and a new .gitignore file.

7 Jul 2022

1. Big changes to the study guide, including:
   • Data Structures and Search Algorithms main sections.
   • A full-populated and linked search algorithm complexity table.
   • A fully-written section on Selection Sort (plus a lot of dummy text for other sort algorithms).

6 Jul 2022

1. First upload of a Java version (HashSet) plus a general restructuring of directory structure + a revamped .gitignore file.

4 Jul 2022

1. I added some details to the study guide, and implemented BFS to the BST.py file. Next up, I plan to implement some deletion methods, and possibly to adapt some BST-implemented methods to code a less-specific brand of tree.

3 Jul 2022

1. I'm keeping a study guide to go along with my explorations into these data structures/algorithms. I decided it was a good idea to upload the related .tex, .sty, and .pdf files.
2. Later, added BST information to both Okay directory (in Python3) and study guide.

27 Jun 2022

1. Used some snippets from this answer to prototype a redo of SinglyLinkedList. This code + the code in the accepted comment contained >= 2 very serious bugs and needed quite a bit of plussing up, so I did that plus thoroughly documented everything before **finally** reaching the level of "accepted LeetCode answer."

26 Jun 2022

1. Initial upload.
2. Later, updated the README.md file to its current state.
3. Approximately 22 hours later, attempted to use the GeeksForGeeks solution as an inspiration for a new implementation of SinglyLinkedList, only to find that this one times out on LeetCode. I think my best plan of action moving forward will be to try a whole new implementation; I have some ideas!