I also struggle a bit in getting the exact meaning of your question.
I understand your question like this: "I have various pages of node listing generated by my view, I would like to have on top of each of these pages a link that allows me to create a new node of the type listed in the views. How do I do it?".
If I got your question right, a possible method is to insert the link in the template for your view. In fact the link to create a new node of that type will be a static URL of the type
http://example.com/node/add/mynodetype
so you can safely put in your template file something like:
<?php print(l('Create a new mynodetype article!', 'node/add/mynodetype')) ?>
EDIT: This is substantially equivalent to what Henrik proposed (+1) by modifying the header of your view. What method you choose will probably depend on if you consider this link more of a core feature of your view or more of a theming element. If you add it to the view, you will have it in all your themes (=feature). If you put it in the template, you will only have it for the theme the template is used by (=theming element). Of course - even if it is a theme element - it makes more sense to include it to the view if you use a standard template file, so you will not have to crate an entire template file just for a link.
EDIT II: From your comment below it seems that you are not already using a template for your view, and therefore - unless you need it - you could go with Henrik's suggestion of adding the information in the header of the view. I however prepared screenshots to illustrate both methods:
Adding to the header:
You have to click on "header", then insert the code in the textfield and set the input filter to "PHP" (Otherwise your code will be escaped and displayed instead of being run).
Creating a template:
You have to click on "information: theme" and then you will have a list of possible template names. The one in bold is the one currently used. You then have then to copy the file with the bold name (from the views directory) to your theme directory, and rename it in one of the proposed ways. Then you can enter the file and edit it adding the PHP code you need.
As stated before: if you do not need a template for anything else, then creating a theme only for this is overshooting, IMO.
HTH!