## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

# 1. Graphs: Continued¶

Consider the following code:

public class LinkedList<T> {

public void append_front(T item) {
// appends to front of list:
Node<T> node = new Node<T>(item);
}
public void append_end(T item) {
// appends to tail of list:
if (current == null) {
Node<T> node = new Node<T>(item);
} else {
while (current.next != null) {
current = current.next;
}
Node<T> node = new Node<T>(item);
current.next = node;
}
}
public boolean isEmpty() {
}
public T pop_front() {
return temp.data;
}
public T pop_end() {
while (temp.next != null) {
prev = temp;
temp = temp.next;
}
prev.next = null;
return temp.data;
}
}


What would be a better name for this class?

What is the Big O of appending?

What is the Big O of popping?

How could you make this class better?

Consider the method search for the Game class:

public boolean search(String start, String end) {
Place current = places.get(start);
boolean found = false;
HashSet<String> visited = new HashSet<String>();
queue.append(current);

while (!queue.isEmpty()) {
current = queue.pop_front();
System.out.println("Visiting: " + current.name + "...");
if (current.name.equals(end)) {
System.out.println("Path exists!");
found = true;
break;
}
if (! visited.contains(current.name)) {
System.out.println("   expanding: " + current.name + "...");
// expand:
for (Action action: current.actions.values()) {
Place toplace = places.get(action.toplace);
queue.append_front(toplace);
}
}
}
if (!found) {
System.out.println("ERROR: No path exists!");
}
return found;
}


How is this code different from that given in chapter 10. How?

Which kind of search does this perform?

• depth-first