/** * This class allows singly-linked lists to be constructed and manipulated */ public class LinkedIntList { // instance field front --> 2, 44, 77 null private ListNode front; public LinkedIntList() { front = null; } /** * Constructs a LinkedIntList and sets the front to the head ListNode * passed to it. Note: head may already be connected to other ListNodes * @param head ListNode to become the front of the linked list */ public LinkedIntList(ListNode head){ front = head; } /** * Constructs a singly linked list with one ListNode storing an integer * value new LinkedIntList(29) front --> 29, null * @param value data value to store in the ListNode */ public LinkedIntList(int value) { front = new ListNode(value, null); } /** * Adds a new list node to the front of the singly linked list * @param value * * Note: You need to change the front instance field reference * to point at this new node * * front --> null * * front --> 3 * * front --> 3, 5, 6 null * * addFront(7); * front --> 7 --> 3 null */ public void addFront(int value) { if (front == null){ front = new ListNode(value); } else { front = new ListNode(value, front); } } /** * Add a list node to the end of the singly linked list * @param value integer value to add */ public void addEnd(int value) { } /** * Removes the first node in the list and returns the data value * stored in the removed node * @return integer data value that was removed * * Note: if front is null, throw an IllegalStateException("No node to remove"); * * front --> null * * front --> 3 null * * front --> 3 --> 4 --> 5 --> 6 null */ public int removeFront() { return -1; } /** * Traverses to the NEXT to last node and removes the last list node * in the singly linked list by setting current.next to null. Make sure you * save the removed value before setting .next to null so you can return it. * @return integer data value that was removed * * Note: if front is null, throw an IllegalStateException("No node to remove"); */ public int removeEnd2() { if (front == null){ throw new IllegalStateException("No node to remove"); } int removed = front.data; // if only one ListNode if (front.next == null){ front = null; } else { // 2 or more nodes // create a reference/point to the first node ListNode curr = front; // traverse to the next to last node while (curr.next.next != null) { curr = curr.next; } // outside the while curr is on the next to last node removed = curr.next.data; // perform removal curr.next = null; } return removed; } public int removeEnd(){ if (front == null){ throw new IllegalStateException("No node to remove"); } // if only one ListNode if (front.next == null){ int removed = front.data; front = null; return removed; } else { // traverse the list of 2 or more nodes recursively return removeEnd(front); } } // recursive helper method private int removeEnd(ListNode curr){ // base case if (curr.next.next == null){ int removed = curr.next.data; curr.next = null; return removed; }else { // recursive case return removeEnd(curr.next); } } /** * Determines if the value is in a list node in the singly linked list * @param value integer data value to search for * @return true if value is found, false otherwise */ public boolean contains(int value) { // TODO return false; } /** * * @return the number of list nodes in the singly linked list */ public int size() { // TODO return -1; } /** * Creates and returns a string representation of the integer values in the * singly linked list by traversing through all of the nodes concatenating/appending * as you go * @return string of data values ex. [3, 5, 77, -1] * front ---> 3, 5, 77, -1 * curr * front ---> null * * front ---> 3 null * Note: Be careful not to lose the front of the list! * This means that you need another reference to the front of the list * that you manipulate rather than directly manipulating the front reference. */ public String toString() { if (front == null){ return "[ }"; } String result = "[" + front.data; // , data, data, data ListNode curr = front.next; // 3, 4, 5, 7 // c // 3 null // c // visiting every node in the list while (curr != null){ result += ", " + curr.data; curr = curr.next; } // curr is on null outside the loop return result + "]"; } }

Returns the count of the number of nodes in the list. Depending on how you implement this, you could write either: - an O(n) solution that traverses through the whole list and counts each node - an O(1) solution that already "knows" the size of the list and just returns it Which solution is better? Can you implement both? You don't need to for this assignment, but I do want you to include a comment above your implementation that states the big-o of whatever you write. Given an int parameter, - construct a new node for that data value - add the new node to the end of the list (or it might be the front, if front void addEnd(int value) is null., so then you can reuse addFront) Adding at the end of the list will usually require you to traverse to the end of the list and then set the last node's next to point at this new node. Be careful not to lose the front of the list! if front == null, throw an IllegalStateException("No node to remove"); int removeFront() Otherwise remove the front node in the list by - setting the front reference to point at the front's next Returns true if the LinkedlntList has a node with the given value; false boolean contains(int value) otherwise. Be careful not to lose the front of the list