A linked-list implementation
I was never a fan of a "fake first element"-approach. And here is why:

Begin...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 17
Inserting 17...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 3
Enter value: 0
Locating 0...
Value 0 in list!


So, if you're going to do that approach, be careful not to "locate" it or do anything else with it.

My second complaint is that you traverse your list using recursions. This is both slow and memory consuming on large lists. Just imagine a list with 1000 elements. Your insert_node will have 1000 recursive calls, each with its variables node and value on stack, which takes time to create there, and - when done - remove from there. I suggest you do all the list traversing using for or while loops. For example:

int locate_node(struct Link_Data *node, int value) {

    node = node-&gt;next; /* skipping the fake first node */

    while (node &amp;&amp; node-&gt;value != value) node = node-&gt;next;

    if (node) {
        printf ("Value %d in the list!\n", value);
        return 1;
    } else {
        printf ("Value %d not in the list!\n", value);
        return 0;
    }
}


Another thing I have added here is the return value. You should either have void functions or make their return values meaningful. I've used 1 as "there is an element in the list" and 0 as "there is no such element in the list".

I'd also suggest removing output from such functions. They should get the job done (delete, insert, locate) and return a meaningful value, while any user output should be done outside of them.

Last, you create a doubly-linked list, but you don't seem to use prev anywhere except when deleting (which can be done without it), and even there you do not use it properly:

Begin...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 17
Inserting 17...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 19
Inserting 19...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 2
Enter value: 23
Inserting 23...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 1
Enter value: 19
Deleting 19...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 1
Enter value: 23
Deleting 23...
Enter 1 to delete, 2 to insert, 3 to locate, 4 to print_all, or 0 to quit: 3
Segmentation fault


The problem is that you do not fix your prev field of a node after the deleted one, so when you delete two consecutive nodes, the second delete works with a prev that was already freed.

I suggest you make a completely new, recursion-less program, using an ordinary singly-linked list, and without a fake header, and then open a new review request. This seems like a decent tutorial for the lists in C.

One final comment: a print_list function (and the option) would really make it easier for you to test your program.