HW08 - james-bern/CS136 GitHub Wiki
README
Drawing Pictures
- ✨ Drawing pictures will be very helpful for this lab. Give it a shot! Especially if you can't figure out why your code doesn't work. :)
Overview
- Let's implement some fundamental linked list functions!
- They're like little puzzles :)
- Goal: Get you comfortable working with linked lists and get warmed up for trees next week. 🌞🌴
Coding Tips
- 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; }
- It can also be useful to keep track of other nodes (previous node; next node).
Node prev = null; // the previous node Node curr = head; // the current node while (...) { ... prev = curr; curr = curr.next; }
- Here is just one example; there are many variations, for example
- Our linked list is empty (has zero elements) if its head is null.
- Sometimes, it makes sense to treat the empty list as a special case at the very top of a function.
... foo(...) { if (head == null) { ... return ...; } ... }
- Sometimes, it makes sense to treat the empty list as a special case at the very top of a function.
Specification
-
To get a A:
- ✅ Implement all functions marked with TODO's, one at a time, in order, testing as you go.
- ✨
main()
currently callsrunAutograder()
, which runs a basic grading script. - 🚨 Do NOT try to implement all the functions at once. Build and run early; build and run often. 🙂👍
- 🚨 Don't move on until you are confident the function you are currently implementing works perfectly. 🙂👍
- ✨
- ✅ Handle obviously invalid input using assert's.
- ✨ For example, what if the user calls
get(7)
on a list with only 5 elements?- 🚨 You should NOT need to call a
size()
function or store asize
instance variable to handle this.
- 🚨 You should NOT need to call a
- 🚨 The grading script doesn't check whether you've handled invalid input, but you still have to do it. 💪
- ✨ For example, what if the user calls
- ✅ Take time to "clean up your code." Your implementations should make sense to programmers who aren't you!
- ✅ If anything is still (even a little bit) unclear, add a comment!
- ✅ Add additional documentation to the comments above the functions you implement. Other programmers should be able to use your functions without having to read the implementation.
- ✅ Note the big O runtime.
- ✅ Explain any ambiguity/edge-cases that the user of the function should be aware of.
- ✅ Be concise and clear. (What would YOU want to read?)
- ✨ Here is an example of documentation that would get an A.
// Get the number of elements in the list. // If the list is empty, this function returns 0. // Runtime: O(n) int size() { int result = 0; Node curr = head; while (curr != null) { ++result; curr = curr.next; } return result; }
- ✅ Implement all functions marked with TODO's, one at a time, in order, testing as you go.
-
To get an S:
-
✅ 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 abovetoString()
.)- 🚨 Do NOT call
isCircular()
inside oftoString()
.- ✅🚨 You MUST write a simple test case to prove your code actually works (printing a circular list is fine; see comment in Starter Code). 🙂👍
- 🚨 Do NOT call
-
✅ In a new file, repeat the entire homework for a doubly-linked list.
- ✅ Each
LinkedList2
should have aNode2 tail
in addition to aNode2 head
. - ✅ Each
Node2
should have aNode2 prev
in addition to aNode2 next
. - ✅
add(value)
should be replaced withaddFront(value)
andaddBack(value)
- ✅ Your implementation should be efficient (though first, just make it work).
- ✅ For example,
add(index, value)
should start from eitherhead
ortail
depending on which is closer toindex
.- ✨ To make this work efficiently, each
LinkedList2
will need anint size;
that says how many elements are in the list. Functions that change the size of the list will also be responsible for updatingsize
.
- ✨ To make this work efficiently, each
- ✅ For example,
- ✅🚨 You MUST write test cases that prove your code actually works. 🙂👍
- ✨ Perhaps test walking forward from the head AND walking backward from the tail?
- ✅ Each
-
Submission Instructions
- Put the output of
runAutograder()
in a comment at the top of your code file. - Above the output of grade (at the very top), self-grade your homework and according to this scale.
- an A is all functions working and documented perfectly
- a B is 1 function not working or documented perfectly
- a C is >=2 functions not working or documented perfectly)
- Notes
- 🚨 You must follow these instructions this in order to receive points.
- This is a block comment:
/* lorem ipsum dolor */
- Upload your code file to GradeScope by the due date.
- Go over your code with Jim or a Grading TA in Lab.
Starter Code
class HW08 {
static void runAutograder() {
System.out.println("\n-- RUNNING AUTOGRADER --\n");
LinkedList list = new LinkedList("Abe -> Ben");
LinkedList._grade(list.get(0), "Abe");
LinkedList._grade(list.get(1), "Ben");
System.out.println();
/**/ list._grade("Abe -> Ben");
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);
System.out.println();
list = new LinkedList("Gus -> Ivy");
/**/ list._grade("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");
list.reverse(); list._grade("Jax -> Ivy -> Hal -> Gus -> Fid");
System.out.println();
list.head = null;
/**/ list._grade(null);
list.reverse(); list._grade(null); // Reversing an empty list does nothing.
list.add("Zeb"); list._grade("Zeb");
System.out.println();
list = new LinkedList("Abe"); LinkedList._grade(list.isCircular(), false);
list = new LinkedList("Abe -> Ben -> Cam"); LinkedList._grade(list.isCircular(), false);
list.head.next.next.next = list.head; LinkedList._grade(list.isCircular(), true);
// System.out.println(list);
}
////////////////////////////////////////////////////////////////////////
// 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");
// System.out.println(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)
Node(String value) {
this.value = value;
this.next = null;
}
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.
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.
void add(String value) {
// TODO
}
// Remove the first node in the list with this value.
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(target)
}
// Insert a new node (with given value) into the list so that it has this index.
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.
void reverse() {
// TODO
}
// Get whether the list is circular (references form a loop).
boolean isCircular() {
// TODO
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.err.print(" (EXPECTED: " + correctAnswer + ")");
System.out.println();
}
// 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;
}
}
}