Visualization of the Traveling Salesmen Problem

I am working on a little project to visualize the algorithm for the Traveling Salesman Problem. I have cities, which are movable objects painted with AWT and Swing. Also I can make a connection between two cities in the form of a undirected edge. Each city should have at least one connection between another city.

In my current solution every city has an ArrayList of the connected city. But I am afraid that this is not the optimal solution.
I would like to hear some comments about my code in general and improvements for my explained solution.

PS: I know that there are lots of external libraries, but I want to solve that problem without using any external libraries.

The City Panel

```
public class CityPanel extends JPanel implements MouseListener, MouseMotionListener {

public final static int UNIT = 16;
public final static int GRIDWIDTH = 3 * UNIT;
public final static int PANELWIDTH = 12 * GRIDWIDTH;
public final static int PANELHEIGHT = 12 * GRIDWIDTH;

private boolean connect;
private boolean connectClick;
private Mediator mediator;
private CityList cityList = new CityList();
private CityList bestTrail = new CityList();
private City marked;
private boolean move;
private int pressX;
private int pressY;

private Graphics2D g2;

public CityPanel(Mediator mediator) {
this.setPreferredSize(new Dimension(PANELWIDTH, PANELHEIGHT));
this.setBorder(BorderFactory.createLineBorder(Color.BLACK));
this.mediator = mediator;
this.mediator.registerCityPanel(this);
this.addMouseListener(this);
this.addMouseMotionListener(this);
}

//Painting methods

private void paintGrid() {
g2.setColor(Color.LIGHT_GRAY);
for(int i = 0; i maxWidth || e.getX() maxHeight || e.getY() < minHeight ||
this.cityList.isOccupied(new Pos(e.getX(), e.getY()), marked) ||
!move)
return;
this.marked.setPos(n

You might change from ArrayList to HashMap. That will give you better performance for large numbers of cities (for small numbers of cities, the overhead of using a HashMap can be more than what you gain over using the ArrayList).

I would also suggest adding a new variable to your CityList - a new HashMap that is indexed by Pos. Then your isOccupied function becomes:

public boolean isOccupied(Pos pos, City marked) {
    //returns true only if there is a Pos p in the map so p.equals(marked.getPos()) is true.
    return posMap.containsKey(marked.getPos());
}

Why?

In CityPanel, paintCities needs to iterate across all cities
paintConnections needs to iterate across all connections, i.e. doubly iterate across your cities (this will be O(n^2) in the best case).
paintDescriptions will be the same.
addCities calls add() once for each city being generated. So it's O(n * complexity of add())

In City, addConnection calls contains() and add() - this will be O(n) because of contains()
removeConnection calls remove() on the list of connections.
contains is O(n) with an ArrayList.

CityList really only has a problem with isOccupied; it has to iterate through the entire list (so it's O(n)) in order to give an answer.
add relies on isOccupied
remove calls removeConnection() on every city in the list, i.e. O(n * cost of remove)

StackExchange Code Review Q#38120, answer score: 2