In many applications of graphs, the edges of the graph are weighted in some way. For example, in applications pertaining to transportation, the edges might be weighted by highway distance in miles between the pair of endpoints. Thus far, our implementation of the graph class has only considered unweighted graphs. This lab asks you to extend the myListGraph class to a weighted graph class.

To do this you can modify the adjacency list representation in a simple way so as to store edge weights as well. Suppose that edge {u, v} has weight w and further suppose that i and j are respectively the indices of vertices u and v. Recall that edge {u, v} is represented by u appearing in the linked list at Edges[j] and v appearing in the linked list at Edges[i]. To represent the weight w of this edge, we should store the pair (u, w) in the linked list at Edges[j] and the pair (v, w) in the linked list at Edges[i]. Thus each Link object now contains, not just a String but a double as well.

Problem: Modify the StringLink class and the StringLinkList class so that we can define a linked list in which each link contains a String as well as a double. Call the new classes EdgeLink and EdgeLinkList. The methods in the EdgeLinkList class that add new links (e.g., insertFirst, addLast) should take a double argument, in addition to the String argument. The String field in the link should be treated as the key and so all methods that search based on a key (e.g., find and delete) should take just a String argument (as before).

Once the EdgeLinkList class has been defined, we can change the definition of Edges in myListGraph.java from StringLinkList[] to EdgeLinkList[] in order to represent a weighted graph.