daily pastebin goal
16%
SHARE
TWEET

Solution to Part 2 Final Test

kuhnerdm Dec 25th, 2018 116 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // This is the solution to the Final Test of part 2 of the DIY Guide for Learning to Code.
  2. // This will be a bit weird because it should technically span multiple files, but I want to keep everything in one Pastebin.
  3. // So, I'll delimit the files as such:
  4.  
  5. // ===== FILE: DIYList.java =====
  6.  
  7. public interface DIYList<T> {
  8.     // We use a generic type T here, which will allow us to make this a list of any object type
  9.    
  10.     // Declaring our methods here. Remember: It's an interface, so we only say that our classes
  11.     // have to have these methods. We don't implement them here.
  12.     public void add(T item);
  13.     public void remove(T item);
  14.     public T find(int index);
  15. }
  16.  
  17. // ===== FILE: DIYArrayList.java =====
  18.  
  19. public class DIYArrayList<T> implements DIYList<T> { // Need to specify that this is ALSO a generic type
  20.  
  21.     private T[] array;
  22.  
  23.     public DIYArrayList() {
  24.         // We'll start the size at 5, and make it grow later
  25.         // Note: See instructions for info on why we're "casting" here
  26.         this.array = (T[]) new Object[5];
  27.     }
  28.    
  29.     public void add(T item) {
  30.  
  31.         // Check to see if it's null
  32.         if(item == null) {
  33.             return;
  34.         }
  35.  
  36.         // First see if we can just put it in an empty spot
  37.         for(int i = 0; i < this.array.length; i++) {
  38.             if(this.array[i] == null) {
  39.                 this.array[i] = item;
  40.                 return;
  41.             }
  42.         }
  43.  
  44.         // If we made it to this point, then all the spots are filled.
  45.         // We need to make a new array that's bigger.
  46.         int newLength = this.array.length + 1;
  47.         T[] newArray = (T[]) new Object[newLength]; // Casting again, see instructions for info
  48.  
  49.         // Copy all the items in the old array to the new one
  50.         for(int i = 0; i < this.array.length; i++) {
  51.             newArray[i] = this.array[i];
  52.         }
  53.        
  54.         // We know that the last spot in this new array is where the item needs to go
  55.         newArray[newArray.length - 1] = item;
  56.  
  57.         // Finally, make this the array for our list
  58.         this.array = newArray;
  59.     }
  60.  
  61.     public void remove(T item) {
  62.         // Actually finding the item in the list to remove will be easy, but
  63.         // keeping the structure of the array will be a bit harder.
  64.  
  65.         for(int i = 0; i < this.array.length; i++) {
  66.             if(item == this.array[i]) {
  67.                 // We use the == sign to check equality here, but it would actually
  68.                 // be better to use the .equals() method, because in Java, == only
  69.                 // checks if it is LITERALLY the same object, and not two objects that
  70.                 // are equivalent. However, this makes the code trickier, so I'll be leaving
  71.                 // that out.
  72.  
  73.                 this.array[i] = null;
  74.                
  75.                 // Now, we need to slide everything back one index, so we don't have
  76.                 // a hole in the list.
  77.  
  78.                 for(int j = i + 1; j < this.array.length; j++) { // Loops from the next element to the end
  79.                     this.array[j - 1] = this.array[j];
  80.                 }
  81.                 this.array[this.array.length - 1] = null; // The above loop won't change the last one
  82.  
  83.                 return;
  84.             }
  85.         }
  86.     }
  87.  
  88.     public T find(int index) {
  89.         // This should be pretty simple, but we need to be a little careful to
  90.         // make sure that you get null if the index doesn't exist
  91.  
  92.         if(index >= this.array.length) {
  93.             return null;
  94.         }
  95.  
  96.         return this.array[index];
  97.  
  98.     }
  99.  
  100. }
  101.  
  102. // ===== FILE: DIYLinkedList.java =====
  103.  
  104. public class DIYLinkedList<T> implements DIYList<T> {
  105.  
  106.     private T head; // The "head" or "first item in the list"
  107.     private DIYLinkedList<T> tail; // The "tail" or "rest of the list". If there are no more items, this is null.
  108.  
  109.     public DIYLinkedList() {
  110.         this.head = null;
  111.         this.tail = null;
  112.     }
  113.  
  114.     // I'm going to actually add a second constructor here to make some stuff easier.
  115.     // In Java, you can make multiple constructors that take different arguments.
  116.     // This one takes a single element and makes a one-item-long list.
  117.  
  118.     public DIYLinkedList(T item) {
  119.         this.head = item;
  120.         this.tail = null;
  121.     }
  122.  
  123.     // Some "getter" and "setter" functions for convenience
  124.  
  125.     public T getHead() {
  126.         return this.head;
  127.     }
  128.    
  129.     public DIYLinkedList<T> getTail() {
  130.         return this.tail;
  131.     }
  132.  
  133.     public void add(T item) {
  134.  
  135.         // Easy case first - If the list is fully empty
  136.         if(this.head == null) {
  137.             this.head = item;
  138.             return;
  139.         }
  140.  
  141.         // Another easy case - If this list is one item long
  142.         if(this.tail == null) {
  143.             this.tail = new DIYLinkedList<T>(item);
  144.             return;
  145.         }
  146.  
  147.         // And now for the recursive case: If there are more items, then we'll
  148.         // just call add on the tail, which in itself is a list. It'll eventually
  149.         // get to the case above where the tail is null.
  150.         this.tail.add(item);
  151.     }
  152.  
  153.     public void remove(T item) {
  154.  
  155.         // Note: I could simplify this code, but I want to make the cases very distinct.
  156.  
  157.         // Easy case first - If the list is fully empty
  158.         if(this.head == null) {
  159.             return;
  160.         }
  161.  
  162.         // Another easy case - If the list is one item long, and it's the item to be removed
  163.         if(this.tail == null && this.head == item) {
  164.             // See above for explanation about using == here
  165.             this.head = null;
  166.             return;
  167.         }
  168.  
  169.         // If it's one item long and NOT the item, then do nothing
  170.         if(this.tail == null && this.head != item) {
  171.             return;
  172.         }
  173.  
  174.         // Recursive case: If there are items after this, then check if the head is the item,
  175.         // and remove it if it is. If it's not, then call remove on the rest of the list.
  176.         if(this.head == item) {
  177.             // We'll "remove" it by making this node equal to the next node.
  178.             this.head = this.tail.getHead();
  179.             this.tail = this.tail.getTail();
  180.             // We don't have a duplicate anymore because the previous tail is now lost.
  181.             return;
  182.         }
  183.  
  184.         this.tail.remove(item);
  185.     }
  186.  
  187.     public T find(int index) {
  188.         // We'll do some more recursion here.:
  189.  
  190.         if(index == 0) {
  191.             // Return this item
  192.             return this.head;
  193.         } else {
  194.             if(this.tail == null) {
  195.                 // Catch the case where the index is out of bounds
  196.                 return null;
  197.             } else {
  198.                 // This finds the item in the remaining items in the list
  199.                 return this.tail.find(index - 1);
  200.             }
  201.         }
  202.     }
  203.  
  204. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top