How to improve my list's speed
If I understand correctly, you wish to maintain a list of places, and record only the shortest route to each place. This means that each time you need to find any duplicate entry, and choose which to keep.

For this task, an unordered list is pretty much the worst choice you could use. Your algorithm is O(n2) (that is, O(n) for adding each of n elements), and while that isn't important for 10 destinations, it's pretty critical for 3 million!

Given that ordering is not critical here, a hash table is really the correct implementation to use. This will get you O(1) insert and lookup, and the added programming complexity and memory use is appropriate for that number of elements. If that's not possible somehow, then second best would be some kind of self-balancing tree. 

Finally, it makes no sense to count the length of a large list by iterating the elements. Just increment a counter every time you add an element. A reduction from O(n) to O(1). (In theory, if you add and destroy a lot of elements very frequently, but only query the size once in a blue moon, then my statement is untrue, but I doubt that's the case here.)

As far as your existing implementation goes, it's a bad plan to create the new node and then not use it. Maybe in your implementation a garbage collector will sort it out, but otherwise it'll be a huge memory leak, not to mention wasted effort.