Adjacency List

This is a rather simple component which will not be changing much over the semester. There are many ways to implement an adjacency list, not just an array or arrays or a simple matrix like you may have learned in the lower levels! You can do a skiplist of skiplists, or a TreeMap, or maybe even an Arraylist of Arraylists-any number of various objects which provide the right traversal capabilities, meaning that searching for an element in the adjacency list needs to be in $O(\log n)$ where $n$ is the number of vertices.

Regardless of the specific implementation of the adjacency list, its purpose is to provide us with a quick and easy way to perform shortest path calculations so we will be able to produce MeeshQuest functionality. Combined with the spatial data structure and a simple Java GUI library called Canvas Plus which we will be providing for you, you will not only be able to print out detailed instructions of how to get to your destination, but you will also be able to generate a colored map which highlights the route you have calculated on a map. We will not grade it explicitly, but you might prefer to keep an adjacency list representation of the edges that are inserted into the PM quadtree than to derive it on the fly.