Consider the java file Attached below and answer the questions right after the code.

class Node {

String value;

Node next;

public Node(String value, Node next) {

this.value = value;

this.next = next;

}

}

public class LinkedStringList implements StringList {

Node front;

int size;

// How will we construct it?

public LinkedStringList() {

this.front = new Node(null, null);

}

// How will we implement the methods?

public void prepend(String s) {

Node newFront = new Node(s, this.front.next);

this.front.next = newFront;

this.size += 1;

}

public String get(int index) {

Node current = this.front.next;

for(int i = 0; i < index; i += 1) {

current = current.next;

}

return current.value;

}

public void add(String s) {

// NOTE(joe): we start at this.front, because what we need

// for add() is a reference to a node to add to, which may

// be front itself if the list is empty.

// If we didn't have the dummy/sentinel node at the

// beginning, we would need to check if front was null,

// special case that behavior, and then have the loop

// below.

Node current = this.front;

while(current.next != null) {

current = current.next;

}

current.next = new Node(s, null);

this.size += 1;

}

public void remove(int index) {

Node current = this.front;

for(int i = 0; i < index; i += 1) {

current = current.next;

}

current.next = current.next.next;

}

public void insert(int index, String s) {

Node current = this.front;

for(int i = 0; i < index; i += 1) {

current = current.next;

}

current.next = new Node(s, current.next);

}

public int size() {

return this.size;

}

}

Answer the following questions, and justify them with one or two sentences each:

• Give a big- bound for the best case running time of prepend in LinkedStringList
• Give a big- bound for the worst case running time of prepend in LinkedStringList
• Give a big- bound for the best case running time of add in LinkedStringList
• Give a big- bound for the worst case running time of add in LinkedStringList

In all cases, give answers in terms of the current size of the list, and assume that the list has some non-empty size n. That is, you shouldnt consider the empty list as a best case; instead think about the best case based on other factors like size, capacity, and nodes.

Notable points to consider:

• Creating an array takes time proportional to the length of the array
• When considering the running time of a method, make sure to take into account any helpers methods it uses!

Example for get in the LinkedStringList class:

The get method is O(1) in the best case, when the index is 0. In this case

it will do constant work checking the index and immediately return the

first element, never entering the while loop.

The getAt method is O(n) in the worst case, because the index could be at

the end of the list (for example, index n - 1). In this case, the while

loop will run n times, spending constant time on each iteration, resulting

in overall O(n) number of steps taken.