HW08

README

Overview

• Let's implement some fundamental linked list functions!
  • They're like little puzzles :)
• ✨Drawing pictures will be very, very helpful for this lab
  • Without a picture, you'll basically just be guessing at the code 🙈

Coding Tips

Iterating through a linked list

• A while loop can be a good way to iterate through a linked list
  • Here is just one example; there are many variations, for example (curr.next != null) vs. (curr != null)

     Node curr = head; // The "current node" (node we are currently considering)
     while (curr != null) {
        ...
        curr = curr.next; // Update the current node to be the next node
    }

  • While iterating, it can be useful to keep track of additional nodes (previous node; next node)
    • NOTE: Make sure you update the references carefully at the bottom of the while loop; should feel kind of like a "swap"

    Node prev = null; // The previous node
    Node curr = head; // The current node
    while (...) {
    
       ...
    
       // Update the prev and curr references
       // NOTE: the order of these lines matters!
       prev = curr;
       curr = curr.next;
    }

The empty list

• A linked list is empty if the reference head is null
  • Sometimes, it makes sense to treat the empty list as a special case in your code

    void doThingToList() {
         // Special case if list is empty (do thing and then return)
         if (head == null) {
             ...
             return;
        }
    
        // Typical case
        ...
    }

NOTE's

• NOTE: For the A, do NOT add a size/length variable or function to the Starter Code (even though it might be very helpful) 🙅
• NOTE: You can assume lists do NOT have cycles for all functions except hasCycle()
• NOTE: For the runtime question, assume the list is length n, where n is a large number. Best-case and worst-case don't have anything to do with the list being small/big; for linked lists they are about where in the list you are doing the thing (inserting a new element, removing an element, etc.)

TODO's

• A

  • Implement all functions marked with TODO's, one at a time, in order, making sure to test as you go.
    • NOTE: ✨ main() currently calls runAutograder(), which runs a basic grading script 🙂👍
  • Take time to "clean up your code." If anything is still tricky/unclear, add a comment!
  • Add the worst-case and best-case big O runtime to each functions comment
    • Example:

      // Get the number of elements in the list.
      // If the list is empty, this function returns 0.
      // Worst-case Big O Runtime: O(n)
      // Best-case Big O Runtime: O(n)
      int size() {
          int result = 0;
          Node curr = head;
          while (curr != null) {
              ++result;
              curr = curr.next;
          }
          return result;
      }

• A+

  • Extend toString() to work for circular lists. (Do something similar to what Python does when you print a list that contains a reference to itself. Document your decisions in the comment above toString().)

    • HINT: For this problem it is okay to use O(n) space, as long as your solution is still O(n) time. (I recommend...a Map<Node, Whatever>!)
    • NOTE: You MUST write a couple simple test cases to prove your code actually works (printing a circular list is fine; see comment in Starter Code). 🙂👍

  • In a new file, repeat the entire homework except for hasCycle() for a doubly-linked list with a size instance variable

    • Each LinkedList2 should have a Node2 tail in addition to a Node2 head
    • Each Node2 should have a Node2 prev in addition to a Node2 next
    • add(value) should be replaced with addFront(value) and addBack(value)
    • Your implementation should be efficient (though first, just make it work)
      • For example, add(index, value) should start from either head or tail depending on which is closer to index.
        • ✨ To make this work efficiently, each LinkedList2 will need an int size; that says how many elements are in the list. Functions that change the size of the list will also be responsible for updating size.
    • NOTE: You MUST write test cases that prove your code actually works 🙂👍
      • ✨ Perhaps test walking forward from the head AND walking backward from the tail?

Submission Instructions

• Put the output of runAutograder() in a comment at the top of your code file.

Starter Code

class HW08 extends Cow {

	static void runAutograder() {
		PRINT("RUNNING AUTOGRADER");
		PRINT("==================");

		LinkedList list = new LinkedList("Abe -> Ben");

		PRINT();
		PRINT("get");
		PRINT("---");

		LinkedList._grade(list.get(0), "Abe");
		LinkedList._grade(list.get(1), "Ben");

		PRINT();
		PRINT("append + remove");
		PRINT("---------------");

		list.add("Cam");    list._grade("Abe -> Ben -> Cam");
		list.add("Dan");    list._grade("Abe -> Ben -> Cam -> Dan");
		list.remove("Cam"); list._grade("Abe -> Ben -> Dan");
		list.remove("Dan"); list._grade("Abe -> Ben");
		list.remove("Abe"); list._grade("Ben");
		list.remove("Ben"); list._grade(null);

		PRINT();
		PRINT("insert");
		PRINT("------");

		list = new LinkedList("Gus -> Ivy");
		list.add(1, "Hal"); list._grade("Gus -> Hal -> Ivy");
		list.add(3, "Jax"); list._grade("Gus -> Hal -> Ivy -> Jax");
		list.add(0, "Fid"); list._grade("Fid -> Gus -> Hal -> Ivy -> Jax");

		PRINT();
		PRINT("reverse");
		PRINT("-------");

		list.reverse();     list._grade("Jax -> Ivy -> Hal -> Gus -> Fid");

		list.head = null;
		list.reverse();     list._grade(null); // Reversing an empty list does nothing.
		list.add("Zeb");    list._grade("Zeb");

		PRINT();
		PRINT("hasCycle");
		PRINT("--------");

		list = new LinkedList("Abe");                      LinkedList._grade(list.hasCycle(), false);
		list = new LinkedList("Abe -> Ben -> Cam -> Dan"); LinkedList._grade(list.hasCycle(), false);
		list.head.next.next.next.next = list.head.next;    LinkedList._grade(list.hasCycle(), true);

		// PRINT(list); // TODO (A+)

		list = new LinkedList("Carl");
		list.head.next = list.head;    LinkedList._grade(list.hasCycle(), true);

	}

	////////////////////////////////////////////////////////////////////////
	//  YOUR CODE STARTS HERE //////////////////////////////////////////////
	////////////////////////////////////////////////////////////////////////

	public static void main(String[] arguments) {
		// NOTE: Feel free to write your own little tests in main!
		//       Just make sure you pass the autograder before you submit.

		// LinkedList list = new LinkedList("Abe -> Ben");
		// PRINT(list);

		runAutograder();
	}

	static class Node {
		String value; // The actual data stored on the node
		Node next; // A reference (link) to the next node in the list (chain)

		// A simple constructor that sets the node's value
		Node(String value) {
			this.value = value;
			this.next = null; // NOTE: This line is optional (this.next is cleared to null by default)
		}

		public String toString() {
			return value;
		}
	}


	static class LinkedList {
		// The head of the list.
		// If head is null, then the list is empty.
		Node head;

		// Get the value of the node with this index.
		//
		// Worst-case Big O Runtime: O(?)
		// Best-case Big O Runtime: O(?)
		String get(int index) {
			// TODO

			return null;
		}

		// Add a new node with the given value to the end of the list.
		// If list is empty (head is null), the new node becomes the head.
		//
		// Worst-case Big O Runtime: O(?)
		// Best-case Big O Runtime: O(?)
		void add(String value) {
			// TODO

		}

		// Remove the first node in the list with this value.
		//
		// Worst-case Big O Runtime: O(?)
		// Best-case Big O Runtime: O(?)
		void remove(String value) {
			Node prev = null;
			Node curr = head;
			// TODO
			// HINT: Make sure you use stringA.equals(stringB) to compare String's.
			//       for example, curr.value.equals(value)

		}

		// Insert a new node (with given value) into the list so that it has this index.
		//
		// Worst-case Big O Runtime: O(?)
		// Best-case Big O Runtime: O(?)
		void add(int index, String value) {
			// TODO

		}

		// Reverse the list in place.
		// The old tail becomes the new head.
		// If list is empty or has only one element, this function does nothing.
		//
		// Worst-case Big O Runtime: O(?)
		// Best-case Big O Runtime: O(?)
		void reverse() {
			// TODO

		}

		// Get whether the list has a cycle (the list contains a loop)
		// 
		// EXAMPLE: This list has a cycle.
		// A -> B -> C -> D -> E
		//           ^         |
		//           |         |
		//            --------- 
		//
		// EXAMPLE: This list does NOT have a cycle.
		// A -> B -> C -> D
		//
		// Worst-case Big O Runtime: O(?)
		// Best-case Big O Runtime: O(?)
                //
                // Worst-case Big O Space: O(1)
		boolean hasCycle() {
			// TODO

			// HINT: This one is actually pretty tricky :)
			//       If you can't figure out, you can google "Floyd's Tortoise and Hare Algorithm"

			return false;
		}

		////////////////////////////////////////////////////////////////////////
		// YOUR CODE STOPS HERE ////////////////////////////////////////////////
		////////////////////////////////////////////////////////////////////////

		// Construct a list from a String of the form "Abe -> Ben -> Cam".
		// For this example input, constructor is equivalent to:
		//    head = new Token("Abe");
		//    head.next = new Token("Ben");
		//    head.next.next = new Token("Cam");
		LinkedList(String _string) {
			String[] array = _tokenize(_string);
			head = null;
			if (array.length > 0) {
				head = new Node(array[0]);
				Node curr = head;
				for (int i = 1; i < array.length; ++i) {
					curr.next = new Node(array[i]);
					curr = curr.next;
				}
			}
		}

		// Get the list as a String of the form "Abe -> Ben -> Cam".
		public String toString() {
			if (head == null) return "null";
			String result = head.toString();
			Node curr = head;
			while (curr.next != null) {
				result += " -> ";
				result += curr.next;
				curr = curr.next;
			}
			return result;
		}

		// Compare the list to a String of the form "Abe -> Ben -> Cam".
		void _grade(String _string) {
			String[] array = _tokenize(_string);
			boolean isCorrect;
			if (array == null) {
				isCorrect = (head == null);
			} else {
				isCorrect = true;
				int currIndex = 0;
				Node prev = null;
				Node curr = head;
				while (curr != null) {
					if (currIndex >= array.length) break;
					isCorrect &= (array[currIndex++].equals(curr.value));
					curr = curr.next;
				}
				isCorrect &= (currIndex == array.length);
			}
			_gradeHelper(isCorrect, this.toString(), _string);
		}

		static void _grade(String studentAnswer, String correctAnswer) {
			_gradeHelper(correctAnswer.equals(studentAnswer), studentAnswer, correctAnswer);
		}

		static void _grade(boolean studentAnswer, boolean correctAnswer) {
			_gradeHelper(studentAnswer == correctAnswer, "" + studentAnswer, "" + correctAnswer);
		}

		static void _gradeHelper(boolean isCorrect, String studentAnswer, String correctAnswer) {
			System.out.print(isCorrect ? "[+] " : "[-] ");
			System.out.print(studentAnswer);
			if (!isCorrect) System.out.print(" (EXPECTED: " + correctAnswer + ")");
			PRINT();
		}

		// Converts "Abe -> Ben -> Cam" to ["Abe", "Ben", "Cam"].
		static String[] _tokenize(String _string) {
			if (_string == null) return null;
			String[] result = _string.split("->");
			for (int i = 0; i < result.length; ++i) result[i] = result[i].trim();
			return result;
		}
	}

}

HINT's

• Reminder: Drawing ✍️ pictures will be very, very helpful for this lab