Здравствуйте, kapezc.
Примерно так. Сделала отдельно пункты "сортировка" и "вставка в сортированный", если что, Вы всегда можете поменять структуру меню сами.
Чтобы продемонстрировать двусвязность списка, сделала ссылку не только на первый, а и на последний элемент.
Про работу со списками и примеры на Си можно посмотреть в этой книге, там очень неплохо всё описано.
Проверено на Visual Studio 2005. Надеюсь, я не вставила ничего С++-ного, я обычно на чистом Си не пишу.
Будут вопросы - обращайтесь.
Удачи!

Приложение:
#include "stdlib.h"
#include "conio.h"

struct human { //структура
char surname [16]; //фамилия
unsigned int year; //год рождения
human* next; //ссылка на следующий
human* back; //ссылка на предыдущий
};


void NewRecord (human* &first, human* &last) //добавление новой записи (без учёта сортировки)
{
char sn_buf [16]; //ввод данных
unsigned int y_buf;
printf ("Input surname (15 symbols max):\n");
scanf ("%s", sn_buf);
printf ("Input birth year:\n");
scanf ("%d", &y_buf);
if (first==NULL) { //если список пуст
first = new human; //создаём первый элемент
first->year = y_buf;
strcpy (first->surname, sn_buf);
first->next = NULL; //других элементов нет - ссылки на нули
first->back = NULL;
last = first; //ссылка на последний тоже ссылается на первый
} else { //элементы уже есть
human* tmp = new human; //создаём новый объект
tmp->year = y_buf;
strcpy (tmp->surname, sn_buf);
tmp->next = NULL; //он будет последним - дальше 0
tmp->back = last; //предыдущий - бывший последний
last->next = tmp; //у бывшего последнего настраиваем ссылку на следующий
last = tmp; //сохраняем ссылку на последний
}
printf ("\nSuccessfully added\n");
}

void PrintList (human* first) //распечатка списка
{
printf ("\nList:\n");
human* cur = first; //начинаем с первого
while (cur!=NULL) { //пока есть элемент
printf ("%17s %d\n", cur->surname, cur->year); //выводим его
cur = cur->next; //переходим на следующий
}
}

void ExchangeElements (human* &el1, human* &el2) //обмен элементов списка
{
human* b_el1 = el1->back; //сохраним предыдущий и следующие элементы в списке относительно двух обмениваемых
human* b_el2 = el2->back;
human* n_el1 = el1->next;
human* n_el2 = el2->next;
//нужно переставить ссылки так, чтобы элемент el2 указывал на элементы перед и после el1 вместо el2 и наоборот
//только в условии надо учесть, что если будут обмениваться соседние элементы в списке, то нельзя просто
//перекопировать ссылки друг у друга (элемент будет указывать сам на себя и список зациклится)
if (b_el2!=el1) el1->back = b_el2;
else el1->back = el2;
if (n_el2!=el1) el1->next = n_el2;
else el1->next = el2;
if (b_el1!=el2) el2->back = b_el1;
else el2->back = el1;
if (n_el1!=el2) el2->next = n_el1;
else el2->next = el1;
//когда мы выправляем ссылки для элементов, окружающих обмениваемые, надо проверить существование этих элементов
//во избежание ошибки (например, у первого элемента списка не будет предыдущего, а у последнего - следующего)
if (b_el1!=NULL && b_el1!=el2) b_el1->next = el2;
if (b_el2!=NULL && b_el2!=el1) b_el2->next = el1;
if (n_el1!=NULL && n_el1!=el2) n_el1->back = el2;
if (n_el2!=NULL && n_el2!=el1) n_el2->back = el1;
}

void SortList (human* &first, human* &last) //сортировка списка
{
human *cur_i, *cur_j, *min, *cur;
//сортировка методом прямого выбора
for (cur_i=first; cur_i->next!=NULL;) { //идём от первого до предпоследнего
min = cur_i; cur = cur_i; //берём текущий за минимальный, сохраняем текущий
for (cur_j = cur_i->next; cur_j!=NULL; cur_j = cur_j->next) //идём от следующего до конца
if (cur_j->year < min->year) min = cur_j; //ищем минимальный из оставшихся
cur_i = cur_i->next; //переводим ссылку внешнего цикла во избежание её потери
if (cur->year!=min->year) { //если элементы менять надо
if (cur->back==NULL) first = min; //проверяем, не первый ли это
if (min->next==NULL) last = cur; //и не последний ли
ExchangeElements (cur, min); //меняем местами, т.е. ставим меньший наверх
}
}
}

void InsertIntoSorted (human* &first, human* &last) //вставка элемента в сортированный список
{
char sn_buf [16]; //ввод
unsigned int y_buf;
printf ("Input surname (15 symbols max):\n");
scanf ("%s", sn_buf);
printf ("Input birth year:\n");
scanf ("%d", &y_buf);
human* new_rec = new human; //выделение памяти
strcpy (new_rec->surname, sn_buf);
new_rec->year = y_buf;
human* cur = first; //ищем элемент, больший вставляемого
while (cur!=NULL && cur->year<new_rec->year) cur = cur->next;
if (cur==NULL) { //если прошли весь список, то вставляем в конец
last->next = new_rec;
new_rec->back = last;
new_rec->next = NULL;
last = new_rec;
} else if (cur==first) { //если остались вначале, то вставляем на место первого
first->back = new_rec;
new_rec->next = first;
new_rec->back = NULL;
first = new_rec;
} else { //иначе вставляем в середину, где нашли место
new_rec->next = cur;
new_rec->back = cur->back;
cur->back->next = new_rec;
cur->back = new_rec;
}
}

void ClearList (human* &first) //освобождение памяти
{
if (first==NULL) return; //если список пуст - выходим
human* cur = first; //начинаем с первого
while (cur->next!=NULL) { //пока не дойдём до последнего
cur = cur->next; //переходим на следующий
delete cur->back; //удаляем текущий
cur->back = NULL; //обнуляем
}
delete cur; //удаляем последний
first = NULL; //обнуляем ссылку на первый
}

void main()
{
human* first; //ссылка на первый
human* last; //ссылка на последний
first = NULL;
last = NULL;
int ch; //выбор пункта меню
while (true) {
system ("cls"); //очистка экрана
printf ("1. Creation of list\n");
printf ("2. View of list\n");
printf ("3. Add new struct to end of list\n");
printf ("4. Sorting of list\n");
printf ("5. Add new element in sorted list\n");
printf ("6. Exit\n");
printf ("Press key with number of item: ");
scanf ("%i", &ch);
if (ch==6) break; //выход
switch (ch) { //выполнение остальных пунктов
case 1:
system ("cls");
if (first!=NULL) ClearList (first);
printf ("Input the first record\n");
NewRecord (first, last);
break;
case 2:
system ("cls");
PrintList (first);
printf ("Press any key...\n");
getch ();
break;
case 3:
system ("cls");
printf ("Input new record\n");
NewRecord (first, last);
break;
case 4:
SortList (first, last);
system ("cls");
PrintList (first);
printf ("Press any key...\n");
getch ();
break;
case 5:
system ("cls");
printf ("Input new record\n");
InsertIntoSorted (first, last);
break;
}
}
ClearList (first); //перед выходом очищаем список
}