Here's how the patent law works: all it does is gives you the right to sue someone who violates your patent. Nothing else. Since you don't have a patent, you don't have to worry about suing.
It is the other party's responsibility to sue YOU if they feel you have violated their patent. Protecting a patent is expensive, tricky, and there are no guarantees that they'll win. Maybe you'll get lucky and they won't go through the bother. If they don't take you to court, they lose their protection on that patent.
Usually, getting a patent is the easy part.
IANAL but I do have a bunch of patents. And a good patent attorney in my particular field - this is the important part. A good lawyer knows how to write a patent so that it'll win if it goes to court. The patent biz is weird.
To answer your question, no it is not illegal to build and distribute your idea. It only becomes a problem if the patent holder makes a big deal out of it. Here's a discussion on the subject
http://www.patentexpress.com/free-legal-advice/private-use-software-patent-infringement_298966.html
From there,
patent infringement is not a crime. You don't go to jail (except for perhaps contempt of court if you violate an injunction). You only pay money. And the amount of money is a reasonable royalty -- or maybe triple that.
Not 100 per cent accurate, but it gives you the idea. Of course, there's still the expense of your legal defense.
The field of software protection (patents etc) is fascinating. There are many people who argue that you cannot patent software. Also, there are several ways to protect your software. You can patent it - that is, patent the process, patent what the software does. You can copyright the code - which can be better protection, because patents have to be disclosed. You can also copyright the "look and feel" of your program. Copyright is easy and quick - all you do is put the c in a circle on your stuff. Patents take years. Copyrights have to be defended just like patents. It just gives you the right to sue somebody. You also have things like trade secret protection.
Best.