Question Statement: Iteration based on data structures
Project Plan:
- Implement a custom Linked List in C++
- Implement a custom Binary Tree in C++
- Demonstrate iteration and traversal through those structures
- Create equivalent data structures in Ruby
- Explain differences between C++ and Ruby implementations
LINKED LIST
A linked list is a data structure with a variable size made up of nodes, each of which stores one value.
In a Singly-linked list, each node has one pointer to the next node in the list. The final node points to nothing (null).
The LinkedList should track at least two pointers to nodes: head and tail. The head pointer references the first node, while the tail pointer references the last node.
The LinkedList should also have a variable holding its size or length. A length of 0 means that the list is empty, and the head pointer is null.
The add method should take a value as a parameter, make a new Node with that value, and add it to the end of the list (and increment the length): [1, 2, 3] add(4) -> [1, 2, 3, 4]
The push method should take a value as a parameter, make a new Node with that value, and add it to the beginning of the list (and increment the length): [1, 2, 3] push(4) -> [4, 1, 2, 3]
The search method should take a value as a parameter, iterate through the list, and return the index of the first node with that value (where an index of 0 is the head node, an index of 1 is the next node, etc). Return -1 if not found. [1, 2, 3] search(2) -> 2
The get method should take an index as a parameter and return the value of the node at that index: [1, 2, 3] get(1) -> 2 [1, 2, 3] get(0) -> 1
If the language of choice allows for negative indexing relative to the end of the list, add that behavior as well: [1, 2, 3] get(-1) -> 3
The remove method should take a value as a parameter, use the search method to locate a node with that value, and then remove the node by setting the prior node's next pointor to the successor node: [1, 2, 3] remove(2) -> [1, 3]
The pop method should return the value of the fist node in the list, and remove that node by moving the head pointer to the next node. [1, 2, 3] pop() -> [2, 3]
The insert method should take an index and a value, and create a node with that value at the given index: [1, 2, 3] insert(4, 1) -> [1, 4, 2, 3] [1, 2, 3] insert(4, 3) -> [1, 2, 3, 4] Tip - the add or push method is the same as inserting to the end of the list.
If the language of choice allows for negative indexing relative to the end of the list, add that behavior as well: [1, 2, 3] insert(4, -1) -> [1, 2, 3, 4]
The toString (or to_s) method should create and return a string representation of the list similar to how the language of choice represents arrays or lists: {10, 20, 30} or [4, 2, 10] etc.
Iteration methods (which vary by language but may include start, next, end) should allow the regular iteration methods of the language of implementation to loop through the list. For-in, each, and of blocks are examples of iteration methods. Iterators should traverse the list from the first node to the last node in fixed order.
Implement a Singly-Linked-List using generics to allow a LinkedList of any type to be created. Demonstrate adding, removing, inserting, pushing, popping, and accessing values, printing the resulting list after each step. Then demonstrate an iteration method with the list performing some action on/with each entry (like summation, printing, or maximum).
BINARY TREE
A binary tree is a data structure in which one node serves as a root and has at most two child nodes.
A binary search tree (BST) adds the constraint that the right child of a node must have a smaller value than the root, while the left child must have a larger (or equal) value than the root.
Each node in the tree should hold a single (comparable) value, as well as two pointers to the left and right child nodes. If the left and right pointers are both null, the node is called a leaf node.
The BinarySearchTree should hold a pointer to the root node, and track the total number of nodes in the tree as its size.
The add method should take a (comparable) value and recursively search through the branches of the tree depending on the comparison between the passed value and the node's value. Once it locates a valid place for the value, it should create a new node with that value at that location.
The remove method should take a (comparable) value as a parameter, find a node with that value within the tree, remove the node, and move the nodes in the child branches of the removed node to their proper places in the tree.
The minimum (or leftmost) method should return the value of the leftmost leaf of the tree, which corresponds to the smallest value in the tree. Recursion is helpful.
The maximum (or rightmost) method should return the value of the rightmost leaf of the tree, which corresponds to the largest value in the tree. Recursion is helpful.
The toString method should return a string representation of the tree, where the first line is the value of the root node, the next line is the values of its child nodes, and so on. Because the tree may be incomplete (nodes missing), replace any null values with an underscore '_' to indicate missing branches.
Iteration methods (which vary by language but may include start, next, end) should allow the regular iteration methods of the language of implementation to loop through the list. For-in, each, and of blocks are examples of iteration methods. Iterators should traverse the tree from lowest value to highest value, using the leftmost leaf as the start value.
Implement a Binary Search Tree using generics to allow a BST of any (comparable) type to be created. Demonstrate adding and removing values, printing the resulting tree after each step. Then demonstrate an iteration method with the list performing some action on/with each entry (like summation, printing, or averaging).
Presentation (slides) in-class on April 29 or May 01.
To work on this project, you will need access to a C compiler/debugger like gcc, g++, and gdb. You will also need to set up Ruby on your machine. These links will be helpful. https://code.visualstudio.com/docs/languages/cpp https://code.visualstudio.com/docs/languages/ruby https://www.ruby-lang.org/en/documentation/installation/#rubyinstaller
Please ask someone for help if you are unable to work on the project!
Google doc report: https://docs.google.com/document/d/1C4JA5zZs1gJwENEYILEb7qrgsSHayElSIvCPepmcje0/edit?usp=sharing Google slides presentation: https://docs.google.com/presentation/d/1-u-SzKiUuGa1uYEFOFydHTsuFq2woK1J/edit?usp=sharing&ouid=110648894901286714538&rtpof=true&sd=true